论文部分内容阅读
[摘 要] 传统的数据挖掘研究开展的前提是数据对象各个属性拥有确定值，而在一般的高维数据研究中，人们所能收集到的数据往往是不完全的，即存在缺失数据。现有主要方法大多是将缺失数据填补问题扩展为对象之间的相似度计算问题。其中，分类属性有别于数值属性，难以直接进行数学计算衡量相似度。 CSRimpute算法引入稀疏表示理论完成对分类属性缺失数据的填补，其在分类属性数据集上相比其他传统方法具有一定的优势。文章重点分析了CSRimpute算法在4个数据集中的缺失数据填补效果是如何受到l1范数和l2范数正则化项的影响，实验结果表明CSRimpute算法对正则化参数的选择并不十分敏感。
[关键词] 稀疏表示；缺失数据填补；分类属性
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 23. 084
[中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194（2016）23- 0159- 04
1 引 言
稀疏表示理论[1]是机器学习领域近几年出现的新方法，其应用最小化l1范数[2]的优化方法获得基于过完备字典特征表示的稀疏向量，是获取、表示数据的有效工具。在现有的分类研究应用中，稀疏表示获得了比传统方法更好的分类性能，已成功应用于人脸识别、语音识别等信号和图像识别领域[3]。另一方面，传统的数据挖掘理论研究需要数据完整而确定，但在实际应用中，由于数据测量误差、获取限制、存储介质故障等原因，人们所能收集到的数据往往存在缺失现象。应对数据缺失现象的常规做法是寻求合适的算法进行缺失数据填补。相较于能够直接进行数值计算的数值型属性，在处理分类属性时，由于其不具备直接进行数值计算的原理，需要进行相应处理后方可进行填补[4]。
基于上述情况，Shao，et.al提出了基于K最近邻局部约束稀疏表示的分类属性缺失数据填补方法CSRimpute（Categorical Sparse Representation imputation）[5]。该方法针对分类属性缺失数据的特点，利用完整数据设计字典，在保留局部结构特征的同时改善分类属性缺失数据的填补效果。
2 CSRimpute算法介绍
CSRimpute算法是在局部约束稀疏表示的基础上，结合K最近邻算法设计字典，力图解决缺失数据的填补问题。 该算法可以适用于包含一个缺失值或被推广到包含多个缺失值的数据对象上。为了方便说明，需要定义一些概念如下：
X=[x1，x2，…，xi，…，xn]∈Cm×n表示一个包含n个数据对象的分类属性数据集。
列向量xi∈Cm×1表示第个数据对象：
xi=[xi1，x12，…，xim]T∈Cm
第i个数据对象在第j个属性上的缺失值成为缺失属性值，记做：X（j，i）=xi（j）=xij =“*”。分类数据集共有m个属性行，每个属性行分别有cj种取值，且c1 c2 … cm=M。
该算法的具体过程如下：
输入：含有缺失数据对象的数据矩阵X=[x1，x2，…，xi，…， xn]∈Cm×n；正则化约束参数λ1，λ2>0；字典包含原子数据对象数量k；
输出，填补后的完整数据集X；
过程：
（1）将原始数据集X转化为二进制矩阵A。在xi的第j个分类属性行所对应的cj行中，仅在代表其取值的属性行取值为1，其他取值为0；若属性缺失，则cj行取值均为0；
（2）将A划分为A=[AC AM] 两部分，其中完整数据集AC =[a1，a2，…，ac，…，anc]∈Cm×nc，缺失数据集AM =[anc 1，anc 2，…， am，…，anc nm]∈Cm×nm，假设A中前nc个数据对象都是完整的；
（3）应用K最近邻作为字典构造方法，针对AM中的每个缺失数据对象am分别构造字典AN（m）=[aN（1），…，aN（k），…，aN（K）]∈ CM×K，重复步骤4至步骤7；
（4）将am和AN（m）在所有am非缺失属性上进行投影得到am*和AN（m）*，即去除am中的所有的缺失属性并在AN（m）中移除相应的属性；
（5）计算am*和AN（m）*中每个数据对象的欧几里得距离，根据公式，
（8）算法结束，输出填补后的数据矩阵X。
3 实验分析
本实验从UCI机器学习数据库中选择了4个经典的分类属性数据集（Soybean，ZOO，SPECT Heart，Chess）。为了将原始数据值和填补估计值进行对比，针对每个数据集，首先删除其中包含缺失属性值的数据对象，得到完整数据集。然后，随机选取数据集中的部分数据对象构成缺失对象数据集，对于每个被选取的数据对象，从中随机选择一定数量的属性值，人为地将这些属性值设定为缺失属性值。
设计本试验的目的是测试正则化参数l1和l2的敏感性。为了便于操作，将缺失属性比率和缺失数据集的比率均设定为20%。对于设定的正则化参数，分别选取它们的2n倍计算缺失填补正确率，结果如表1、表5所示。
从前3张表中可以看出，在4个数据集中，无论如何变化，算法的填补正确率相对都比较平稳，没有出现大幅度增加或减少的情况。两个正则化参数 λ1和λ2的变化使得CSRimpute的填补效果略有浮动，但浮动的范围较小，并未过度偏离最优结果。最后的统计表显示，Soybean和Chess数据集的极差和标准差较小，而ZOO和SPECT Heart数据集的极差和标准差相对较大。这在一定程度上说明正则化参数 λ1和λ2对填补效果的影响在较大数据集的情况下反而较小，这是因为在较大数据集中能够更容易找到与目标数据对象更相似的数据，从而能够得到更加理想的稀疏表示。 4 结 论
本文针对CSRimpute算法中的正则化参数该如何选择的角度出发，通过4个数据集验证分析了 λ1和λ2对算法填补效果的影响。实验结果表明，缺失数据的填补效果随着正则化参数在最优值附近较为平稳的变化，即CSRimpute算法受正则化参数 λ1和λ2变化的影响并不明显，在实际应用中能够比较容易确定。
主要参考文献
[1]Wright J， Yang A Y， Ganesh A， et al. Robust Face Recognition via Sparse Representation[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2009， 31（2）： 210-227.
[2]Candès E J， Romberg J， Tao T. Robust Uncertainty Principles： Exact Signal Reconstruction from Highly Incomplete Frequency Information[J]. Information Theory， IEEE Transactions on，2006，52（2）：489-509.
[3]Duan C H， Chiang C K， Lai S H. Face Verification with Local Sparse Representation[J]. Signal Processing Letters， IEEE，2013，20（2）： 177-180.
[4]Shekhar S， Patel V M， Nasrabadi N M， et al. Joint Sparse Representation for Robust Multimodal Biometrics Recognition[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on，2014，36（1）：113-126.
[5]Shao X， Wu S， Feng X， et al. Categorical Missing Data Imputation Approach via Sparse Representation[J]. International Journal of Services Technology and Management，2016，22（1）.
[关键词] 稀疏表示；缺失数据填补；分类属性
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 23. 084
[中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194（2016）23- 0159- 04
1 引 言
稀疏表示理论[1]是机器学习领域近几年出现的新方法，其应用最小化l1范数[2]的优化方法获得基于过完备字典特征表示的稀疏向量，是获取、表示数据的有效工具。在现有的分类研究应用中，稀疏表示获得了比传统方法更好的分类性能，已成功应用于人脸识别、语音识别等信号和图像识别领域[3]。另一方面，传统的数据挖掘理论研究需要数据完整而确定，但在实际应用中，由于数据测量误差、获取限制、存储介质故障等原因，人们所能收集到的数据往往存在缺失现象。应对数据缺失现象的常规做法是寻求合适的算法进行缺失数据填补。相较于能够直接进行数值计算的数值型属性，在处理分类属性时，由于其不具备直接进行数值计算的原理，需要进行相应处理后方可进行填补[4]。
基于上述情况，Shao，et.al提出了基于K最近邻局部约束稀疏表示的分类属性缺失数据填补方法CSRimpute（Categorical Sparse Representation imputation）[5]。该方法针对分类属性缺失数据的特点，利用完整数据设计字典，在保留局部结构特征的同时改善分类属性缺失数据的填补效果。
2 CSRimpute算法介绍
CSRimpute算法是在局部约束稀疏表示的基础上，结合K最近邻算法设计字典，力图解决缺失数据的填补问题。 该算法可以适用于包含一个缺失值或被推广到包含多个缺失值的数据对象上。为了方便说明，需要定义一些概念如下：
X=[x1，x2，…，xi，…，xn]∈Cm×n表示一个包含n个数据对象的分类属性数据集。
列向量xi∈Cm×1表示第个数据对象：
xi=[xi1，x12，…，xim]T∈Cm
第i个数据对象在第j个属性上的缺失值成为缺失属性值，记做：X（j，i）=xi（j）=xij =“*”。分类数据集共有m个属性行，每个属性行分别有cj种取值，且c1 c2 … cm=M。
该算法的具体过程如下：
输入：含有缺失数据对象的数据矩阵X=[x1，x2，…，xi，…， xn]∈Cm×n；正则化约束参数λ1，λ2>0；字典包含原子数据对象数量k；
输出，填补后的完整数据集X；
过程：
（1）将原始数据集X转化为二进制矩阵A。在xi的第j个分类属性行所对应的cj行中，仅在代表其取值的属性行取值为1，其他取值为0；若属性缺失，则cj行取值均为0；
（2）将A划分为A=[AC AM] 两部分，其中完整数据集AC =[a1，a2，…，ac，…，anc]∈Cm×nc，缺失数据集AM =[anc 1，anc 2，…， am，…，anc nm]∈Cm×nm，假设A中前nc个数据对象都是完整的；
（3）应用K最近邻作为字典构造方法，针对AM中的每个缺失数据对象am分别构造字典AN（m）=[aN（1），…，aN（k），…，aN（K）]∈ CM×K，重复步骤4至步骤7；
（4）将am和AN（m）在所有am非缺失属性上进行投影得到am*和AN（m）*，即去除am中的所有的缺失属性并在AN（m）中移除相应的属性；
（5）计算am*和AN（m）*中每个数据对象的欧几里得距离，根据公式，
（8）算法结束，输出填补后的数据矩阵X。
3 实验分析
本实验从UCI机器学习数据库中选择了4个经典的分类属性数据集（Soybean，ZOO，SPECT Heart，Chess）。为了将原始数据值和填补估计值进行对比，针对每个数据集，首先删除其中包含缺失属性值的数据对象，得到完整数据集。然后，随机选取数据集中的部分数据对象构成缺失对象数据集，对于每个被选取的数据对象，从中随机选择一定数量的属性值，人为地将这些属性值设定为缺失属性值。
设计本试验的目的是测试正则化参数l1和l2的敏感性。为了便于操作，将缺失属性比率和缺失数据集的比率均设定为20%。对于设定的正则化参数，分别选取它们的2n倍计算缺失填补正确率，结果如表1、表5所示。
从前3张表中可以看出，在4个数据集中，无论如何变化，算法的填补正确率相对都比较平稳，没有出现大幅度增加或减少的情况。两个正则化参数 λ1和λ2的变化使得CSRimpute的填补效果略有浮动，但浮动的范围较小，并未过度偏离最优结果。最后的统计表显示，Soybean和Chess数据集的极差和标准差较小，而ZOO和SPECT Heart数据集的极差和标准差相对较大。这在一定程度上说明正则化参数 λ1和λ2对填补效果的影响在较大数据集的情况下反而较小，这是因为在较大数据集中能够更容易找到与目标数据对象更相似的数据，从而能够得到更加理想的稀疏表示。 4 结 论
本文针对CSRimpute算法中的正则化参数该如何选择的角度出发，通过4个数据集验证分析了 λ1和λ2对算法填补效果的影响。实验结果表明，缺失数据的填补效果随着正则化参数在最优值附近较为平稳的变化，即CSRimpute算法受正则化参数 λ1和λ2变化的影响并不明显，在实际应用中能够比较容易确定。
主要参考文献
[1]Wright J， Yang A Y， Ganesh A， et al. Robust Face Recognition via Sparse Representation[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2009， 31（2）： 210-227.
[2]Candès E J， Romberg J， Tao T. Robust Uncertainty Principles： Exact Signal Reconstruction from Highly Incomplete Frequency Information[J]. Information Theory， IEEE Transactions on，2006，52（2）：489-509.
[3]Duan C H， Chiang C K， Lai S H. Face Verification with Local Sparse Representation[J]. Signal Processing Letters， IEEE，2013，20（2）： 177-180.
[4]Shekhar S， Patel V M， Nasrabadi N M， et al. Joint Sparse Representation for Robust Multimodal Biometrics Recognition[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on，2014，36（1）：113-126.
[5]Shao X， Wu S， Feng X， et al. Categorical Missing Data Imputation Approach via Sparse Representation[J]. International Journal of Services Technology and Management，2016，22（1）.