一种基于相关系数加权的离散型数据填补算法与分析

来源:用户上传      作者:

　　摘  要： 为解决具有关联性数据的缺失值问题，提出一种结合相关系数与相似性匹配作用于离散型数据填补缺失值的方法。首先，在非缺失数据源中挖掘频繁项集并计算数据属性间的相关性，计算出挖掘项的项内整体的相关性;然后，根据缺失数据所在项的非缺失前项与完整数据挖掘项的相似度选择填补项;填补项相似性一致则利用加权置信度进一步选取填补规则，一方面提高了Apriori挖掘规则集合的数量及质量，另一方面也保证了规则匹配的可靠性。经实验与相关方法比较，该方法提高了缺失数据填补的准确率与时间效率。
　　关键词： 离散数据填补; 加权支持度; 相关系数加权; 缺失值填补; 频繁项集挖掘; 填补规则选取
　　中图分类号： TN911.1?34                         文献标识码： A                        文章编号： 1004?373X（2020）09?0109?04
　　Analysis on discrete data filling algorithm based on correlation coefficient weighting
　　WANG Zhigang1， TIAN Liqin2， MAO Yaqiong1
　　（1. Qinghai Normal University， Xining 810008， China;
　　2. North China Institute of Science and Technology， Beijing 101601， China）
　　Abstract： In order to solve the problem of missing values of correlation data， a method combining correlation coefficient and similarity matching is proposed to fill the missing values of discrete data. The frequent item sets are mined in non?missing data sources and the correlation between the data attributes is calculated to get the overall inter?item correlation. Then， the items under filling are selected according to the similarity between the non?missing previous item in the item of missing data and the complete data mining item. If the similarity of the items under filling is similar， filling rules are further selected by weighted confidence， so as to improve the quantity and quality of Apriori mining rule sets and guarantee the reliability of rule matching. Contrastive experiments were performed between the proposed method and other related methods. The experimental results verify that the proposed method can improve the accuracy and time efficiency of missing data filling.
　　Keywords： discrete value filling; weighted support; correlation coefficient weighting; missing value filling; frequent item set mining; filling rule selection
　　0  引  言
　　數据分析的前提是要求数据本身具有较高的可用性，删除相关数据或不作处理都将降低源数据库的利用价值，而采用恰当的填补缺失的方法处理数据能够提高数据质量，可靠的数据输出能为精准的数据分析结果奠定基础[1]。缺失数据的填补技术是指采用设计的方法策略将不完备的数据填补成完整的数据集，进而满足数据分析的基本需求，提供完整可靠的数据集。缺失数据填补方法主要包括两大类：一类是传统的统计学方法[2]，该方法研究最为广泛，包括均值替代法、最大期望值法、随机回归填充、马尔科夫链蒙特卡洛法、热卡填补方法等;另一类填补方法则基于数据挖掘，具体方法包含基于决策树填补[3]、基于贝叶斯网络填补[4]、基于中心聚类填补[5]、基于神经网络填补[6?7]、基于支持向量机填补方法[8]以及关联规则填补算法。将本文方法与经典Apriori填补算法以及长度优先选择算法L?Apriori[9]在准确率、填补率及实时性方面进行比较。
　　统计学方法时间效率高，但准确率相对数据挖掘方法较低。在数据挖掘方法中，大多对连续型数值型数据精度高于离散数据。因此，本文提出一种将统计方法中的相关性（Correlation）计算与Apriori相结合的方法，针对离散型缺失数据填补方法进行研究。在关联规则挖掘方法Apriori上改进支持度来挖掘频繁项集，并采用余弦相似性度量选择填补规则，弥补了对数据库的缺失数据采用元组相似度填补数据[10]，时间效率相对较低的问题。本文方法与经典Apriori填补算法以及长度优先选择算法L?Apriori[9]进行效率对比。 　　1  Apriori算法的概念及原理
　　1.1  基本概念
　　关联规则定义是满足给定的支持度（Support）与置信度（Confidence）阈值的规则。
　　假设DB为事物数据源采集组成的数据库，属性[A]（Attribute）集合[A={a1，a2，…，am}]是数据库中[m]个事物属性数据的集合。[T={t1，t2，…，tN}]为所有[N]个记录条目的集合，数据库中基于时间索引的记录[ti∈T]，每个[ti]由[A]中任意个数元素构成，因此，可以得到[ti?A]。
　　定义1：定义频繁项集，若[A]的任何单个子集[I]称为项，[k]个属性组成的集合称为[k]?项集，满足支持度阈值的项目集称为频繁[k]?项集。
　　定义2：记录包含项的表示方法定义记为[ρ（I）]，在数据库DB中，含有项集[I]所有记录的集合公式表示为：
　　[ρ（I）={tiI?ti，ti?T，T∈DB}] （1）
　　同理，将数据库DB中，部分含有缺失项（Missing item）记录的集合记为MI（[I]），那么：
　　[MI（I）={ti?ai?ti，ti?T，T∈DB}] （2）
　　定义3：某一项集[I]，基于缺失值的支持度记为[σ（I）]，[?]表示集合中所含事务数目：
　　[σ（I）=ρ（I）DB-MI（I）=事物集I的次数数据库DB非缺失次数] （3）
　　定义4：若对于某两个数目分别为[p]和[q]的项集赋值：[X={a1∶x1，a2∶x2，…，ap∶xp}]，[Y={b1∶x1，b2∶x2，…，][bp∶xq}]，则挖掘关联规则[X→Y]的置信度记为[θ（X→Y）]：
　　[θ（X→Y）=ρ（X?Y）ρ（X）=σ（X?Y）σ（X）] （4）
　　式中：[X]表示规则的前项;[Y]表示后项;关联规则的置信度是[ρ]与[σ]的比值。
　　频繁项通常必须满足给定最小支持度即支持度阈值，标记为[σ?min]，同时最小置信度为[θ?min]。
　　1.2  Apriori算法步骤
　　频繁项目集挖掘算法Apriori根据项集的先验知识，采用迭代的方法逐层挖掘出满足条件的频繁项集，再根据最小置信度与支持度的条件来产生关联规则，过程如下：
　　1） 设置最小支持度[σ?min]，扫描数据库DB，单项候选集[C1]记录次数与该支持度比较，找出所有满足条件，得到频繁1?项集[L1];
　　2） 根据[L1]的挖掘结果组成候选项集[C2]，根据支持度阈值的条件，自连接为长度为2的项集频繁2?项集[L2];
　　3） 为得到最终的[Lk]，循环由单项至[k]项，逐一使用前挖掘频繁项[Ck-1]产生的候选项集连接为[Lk]，直到不再产生新的项集为止。
　　2  加权的Apriori缺失填补算法
　　通过频繁项集的挖掘，Apriori算法对系统的要求较高，算法耗费资源较多。因此，利用挖掘出的规则来计算缺失数据等应用的效率就会降低，除此之外，挖掘出的规则并没有权衡每个属性元素的重要性，导致挖掘出的规则也不具有较高的利用价值。为此，本文对Apriori的算法进行改进，提高挖掘出规则的可利用性和数量较多的高质量规则，提出了基于属性间相关性的加权规则挖掘算法，即C?Apriori算法。
　　2.1  填补规则选择
　　利用皮尔森相关系数计算属性的相关性，经验证该算法对具有正态分布的数据有良好的适用性。利用皮尔森相关系数作为规则支持度加权，从而提高规则质量，采用如下定义：
　　定义5：设[T]是所有事务的集合，则[T={t1，t2，…，tN}]为记录[N]个事务的集合，数据库DB属性相关系数矩阵见表1。[P=（pij）n×n]，式中，当[i≠j]时，[pij]表示标记的当前记录[t]的值域中，归属[a]的第[i]个属性与第[j]个属性的相关性度量值。
　　定义6：設数据库中某条记录[ti={ip，iq，…，ix，…，ir}]，[ti]中值[ix]的属性为[ax]，那么定义该记录的支持提升度为：
　　[p（ti）=i=1，j=1i=C2ti，j=C2tipijC2ti=i=1，j=1i=C2ti，j=C2tip（ai，aj）C2ti，    i<j，ix∈ax] （5）
　　计算上界为组成二元相关总个数，其中，[pij]与[p（ai，aj）]表示两两相关性。
　　定义7：项集的加权支持度[p-σ（ti）=p（ti）*σ（ti）]，其中，[σ（I）]为定义3的支持度。任意的[X]与[Y]集合，项集的条件支持度可记为：
　　[p-σ（X→Y）=P（X?Y）*σ（X?Y）] （6）
　　定义8：加权关联规则的置信度根据定义4可得：
　　[p-θ（X→Y）=p-σ（X?Y）p-σ（X）] （7）
　　那么，假设[Ic]是在完整数据库挖掘出的关联规则，[Im]（[Im?Ic]）表示包含缺失属性值的规则，且所含缺失项[Iai]包含在如定义4中[Y]所在规则的后项事务中，设含有缺失数据的记录为[tm]，完整数据规则与缺失记录的项集中不包含缺失项的部分用[Ic（Ai）]与[Im（Aj）]表示，则余弦相似度CS（Cosine Similarity）可表示为：
　　[CS（Ic（Ai），Im（Aj））=Ic（Ai）?Im（Aj）Ic（Ai）×Im（Aj）] （8）
　　式中[·]与定义3相同，作为公式中项的数目计算。利用相似度公式的计算，相似度区间为（0，1），若不存在缺失值为1。由于会出现相似度相同，根据定义8，基于缺失数据相关性优化的加权置信度计算，按置信度的降序排列选择置信度最高的规则填补。 　　2.2  算法流程
　　根据上文定义加权规则的算法，本文对缺失数据填补的策略主要步骤如下：
　　1） 将源数据DB分为非缺失数据部分与缺失部分，计算皮尔森相关系数，得到系数相关矩阵[P];
　　2） 结合Apriori挖掘算法，采用相对提升支持度的加权支持度计算方法挖掘频繁项集;
　　3） 利用缺失数据项的非缺失部分，与完整数据集挖掘的规则计算余弦相似度CS，取相似度高者来填补数据，当相似度相同时，进一步利用加权置信度选择填补规则;
　　4） 得到填补后的数据集[DB]。
　　基于C?Apriori缺失值填补算法伪代码如下：
　　Input：源数据库DB，支持度阈值[σmin]
　　Output：填充后数据集[DB]
　　1.Select non?missing and missing data to DBnon and DBmiss;
　　//扫描源数据库DB，组成非缺失数据库DBnon与缺失数据库DBmiss
　　2.for [（i=1;ai∈A&&ai≠Null;i++）]
　　3.      for [（j=1;aj∈A&&aj≠Null;j++）]
　　4.         [fz]=（sum（[ai*aj]）-sum（[ai]）*sum（[aj]）） / length（[ai]）;
　　5.         [fm]= sqrt（（sum（[ai]^2）-（sum（[ai]））^2/length（[ai]））*（sum（[aj]^2）-（sum（[aj]））^2/length（[aj]）））;
　　6.         cor = fenzi/fenmu;
　　7.return  two?dimensional matrix array [P] from  DBnon;
　　//得到DBnon的相关系数矩阵[P]
　　8.[L1←{ll∈C1，σ（l）≥σmin}]
　　//1?项集不进行属性间相关性计算
　　9.for [（k=2;Lk-1≠Null;k++）]
　　10.     for each [ti∈T&&?item≠Null]
　　//定义对每条不为空记录的相关属性计算
　　11. [σ（Lk）←p（ti）*σ（ti）];
　　//由矩阵[P]得到的相关系数计算加权支持度
　　12.         [Ck-1←Lk];
　　13.return   [Lk←{ll∈I1，σ（l）≥σmin}];
　　//算法得到所有完整数据集挖掘出的频繁项集[Lk]
　　14.for each [ti?DBmiss]; //缺失数据的规则选择填补
　　15.     [Iai=MissItem（ti），Iai];
　　//[Iai]表示[ti]的缺失项作为规则的后项，[Iai]表示非缺失项
　　16.     [Iai （ti）k←max{CSm（Iai（Ai），Iai（Aj））}];
　　//计算相同后项的前项相似度
　　17.     [if CSk（ti）=CSk（ti）]
　　18.          [t′i←max{p-θ（Iai）}];
　　//相关性相同采用置信度高的填补
　　19.return [DB]
　　3  实验结果及分析
　　为了验证本文提出的C?Apriori算法的准确性与时效性，利用UCI数据集Vowel的871条包含6个属性的源数据对算法进行验证。本文从数据的填补准确率以及处理数據的时效性与传统Apriori算法以及长度优先L?Apriori算法填补数据结果进行分析。
　　3.1  准确率分析
　　数据准确率记为[A]（Accuracy），是用户衡量填补数据质量的重要参数。在算法中，带有缺失数据的数据库DB中缺失数据个数记为DBM（DB?miss），填补后正确的数据个数记为DBR（DB?right），用二者的比值作为填补的准确率计算公式：
　　[A=DBMDBR×100%] （9）
　　由上式可知，准确率在0～100[%]之间，越高表示填补准确度越高。
　　由图1可知，随着支持度阈值的增加，数据填补准确率总体呈现出急速下降趋势，但本文基于相关性的方法准确率相对较高且下降趋势较缓慢。而图2中随着数据缺失率的增加，本文算法填补准确率与稳定程度均高于其他两种算法，其中，基于传统Apriori填补方法整体填补准确率显著较低。
　　3.2  填补时效性
　　在图3中，随着缺失数据量的增多，会导致在挖掘过程中提供的学习数据量减少，而且需填补数据比重增大，因此，这三种方法填补平均时间都呈上升趋势。但本文方法在时间占用上稍优于对比方法，且较为稳定。
　　4  结  语
　　通过实验结果分析，针对离散型数据，基于相关系数优化支持度挖掘频繁项，能够在一定程度上提高有效项集的挖掘，从而提高数据填补的准确率。另一方面，规则使用源数据中非缺失数据挖掘项集与缺失项之间计算相似度，避免了置信度条件不足导致的无法填充的情况，使得在数据缺失率较高的情况下依然能够保持填充率及准确率。但由于本文选取的是适用关联规则的离散数据验证分析，若应用于数值型数据领域需进行专门的离散化计算与分析，在今后的研究中将进一步探索本文算法在连续数值型数据领域的应用效果。
　　参考文献
　　[1] 晔沙.数据缺失及其处理方法综述[J].电子测试，2017（18）：65?67.
　　[2] 张松兰，王鹏，徐子伟.基于统计相关的缺失值数据处理研究[J].统计与决策，2016（12）：13?16.
　　[3] 沈思倩，毛宇光，江冠儒.不完全数据集的差分隐私保护决策树研究[J].计算机科学，2017，44（6）：139?143.
　　[4] 王社会，杨俊安，尹海波.改进的贝叶斯矩阵修复方法[J].计算机应用，2014（z1）：127?130.
　　[5] 王妍，王凤桐，王俊陆，等.基于泛化中心聚类的不完备数据集填补方法[J].小型微型计算机系统，2017，38（9）：2017?2021.
　　[6] 李彦，刘军.面向大数据的多维数据缺失特征填补仿真研究[J].计算机仿真，2018，35（10）：432?435.
　　[7] 蒋丽丽，姜大庆.基于BP神经网络的农资库存数据插补技术[J].江苏农业科学，2018，46（20）：268?271.
　　[8] 张婵.一种基于支持向量机的缺失值填补算法[J].计算机应用与软件，2013，30（5）：226?228.
　　[9] WU J， SONG Q， SHEN J. An novel association rule mining based missing nominal data imputation method [C]// Eighth ACIS International Conference on Software Engineering， Artificial Intelligence， Networking， and Parallel/Distributed Compu?ting. Qingdao， China： IEEE， 2007： 244?249.
　　[10] 王俊陆，王玲，王妍，等.基于元组相似度的不完备数据填补方法研究[J].计算机科学，2017，44（2）：98?102.
转载注明来源:https://www.xzbu.com/8/view-15248568.htm