基于动态代价敏感的数据挖掘算法探讨

　　1 引言
　　目前，数据作为信息的载体其重要性愈加突出，对数据的分析研究可及时发现问题，为决策的可行性评估提供客观依据。计算机技术的发展使得人们对传统的确定性数据的管理水平得到了极大的提高，数据库技术已成为建设信息化社会的重要支撑。在传统的数据库中，数据有着固有的存在性和精确性，而在现实生活中，传感器网络、数据集成、Web应用等多个领域中广泛存在着不确定性数据，随着技术的进步及人们对数据管理的进一步理解，不确定数据挖掘成为相关领域内研究的热点，研究者们针对不确定数据挖掘提出了各种模型、算法，为实际工作中不确定数据的数据做出了一定的贡献，但现有不确定性数据挖掘模型在应用中存在着只有在特殊情况下才具有合理性、数据挖掘费用高等不足。代价敏感学习方法一种新的机器学习方法，其目标是代价敏感的、追求代价的最小化，将其应用于不确定数据挖掘中可较好地降低总代价。
　　2 不确定数据
　　不确定数据是相对传统的确定数据而言的，是近年来在传感器网络（WSN）、无线射频识别（RFID）、隐私保护、基于位置的服务（LBS）等现实应用中涌现出的一种数据，在金融、军事、电信等多个领域内数据的不确定性普遍存在，其特点是每个数据的对象不是单个数据，而是按照概率在多个数据上出现。
　　不确定数据产生的原因较为复杂，不同应用领域内的误差或认为因素均可造成数据的不确定性，其中既有可能是因数据采集方式的技术限制，导致原始数据不准确或采用了粗粒度数据集合而带来数据的不确定性，也有可能是为了满足特殊应用的目的，或是经过处理缺失值或数据集成生成的。在数据的产生、收集，存储和传输过程中有大量随机性。例如测量手段的限制、网络传输的延迟、数据来源的失效、抽样误差等，甚至可能由于人为因素导致，使得数据的不确定性普遍存在于现实世界各个领域中。同时，很多数据本身的特点也决定其具有不确定性。而所有这些数据的不确定特征会导致数据挖掘结果不可靠甚至出现导致误导的结果。
　　不确定数据的主要表现形式分为实例存在不确定性，属性不确定性和语义映射不确定性。实例存在不确定性是指一个实例在数据库中是否存在的一个不确定值，通常表示为一个概率值。这种不确定性又分为实例之间存在相互依赖关系和实例之间相互独立这两种情况。属性不确定是指一个属性的取值存在不确定性，通常用概率密度公式或统计值（如方差）等来描述属性的不确定信息，这种不确定性又可以根据属性的不同具体分为数值不确定性和非数值不确定性。语义映射不确定性是指数据源和中介源之间的映射关系往往是不确定的。
　　在数据挖掘研究领域内，不确定数据的表现形式主要有存在不确定性和属性不确定性两种，前者也称为元祖不确定性，后者又称为值不确定性。
　　3 不确定性数据挖掘方法
　　由于不确定数据的特殊性，传统的针对确定数据的处理方法不能满足现实应用的需求，从上世纪80年代末，人们就开始对不确定数据的管理和不确定数据的挖掘进行研究，不确定数据挖掘研究的内容有聚类、分类、频繁项集挖掘和孤立点检测等。
　　3.1 聚类分析法
　　聚类是指对象的集合分成由类似的对象组成的多个类，聚类分析也称为群分析，是研究分类问题的一种统计分析方法，传统的聚类分析计算方法有划分方法（Partitioning Methods）、层次方法（Hierarchical Methods）、基于密度的方法（Density-based Methods）、基于网格的方法（Grid-based Methods）、基于模型的方法（Model-based Methods）及直接聚类法、布尔矩阵法（Boole Methods）等。将聚类应用于不确定数据挖掘中的普遍思路，是将传统的聚类方法推广法不确定数据，主要研究方向有扩展基于划分的聚类算法和扩展基于密度的聚类算法。
　　3.2 分类分析法
　　传统的面向确定数据的分类算法常用的有决策树（Decision Tree）分类算法、基于规则的分类算法（Rule Classification Algorithm）、支持向量机法（Support Vector Machine，SVM）、贝叶斯（Bayesian）算法、基于神经网络的算法（Artificial Neural Networks，ANNs）、最近邻法（Nearest Neighbor algorithm）等，目前针对不确定数据挖掘的分类研究主要是基于支持向量机的不确定数据分类法和扩展的贝叶斯分类法。
　3.3 频繁项集挖掘
　　不确定数据的频繁项集挖掘是不确定数据挖掘中研究的重点之一，传统的频繁数据挖掘算法主要有基于先验的（Apriori-based）Apriori算法和基于树结构的FP-tree（Frequent Pattem Tree）算法。不确定数据的频繁项集挖掘的思路主要有两种，一种是在传统的Apriori算法上改进，一种是拓展基于FP-tree的算法；前者主要有基于LGS-trimming（Local Trimming，Global Pruning and Single-Paa Patch Up）技术的U-Apriori算法和针对U-Apriori算法缺陷改进的基于交替递减枝技术的DP（Decremental Pruning）算法，后者有UF-growth算法，此算法比U-Apriori算法的效率高，但比起传统的FP-tree算法，其需要更大的内存，为解决这一问题，研究者们又提出了期望支持度值取整法和只对单例模式的映射数据集建立UF-tree的改进策略。在证据数据库领域，针对不确定数据，有研究者提出了BIT方法（Belief Item Set Tree），随后又有人提出新的数据结构RidListse（Record Identifier Lists），针对BIT方法的不足还有改进的FIM方法。
　　3.4 孤立点检测
　　孤立点（Acnode）是指在数据散布图中，远离其他数据点的、数量虽少但可能扭曲原本均值和标准差或改变聚类算法产生的簇集合的异常对象，目前统计学、计算机学习、数据挖掘等领域内对孤立点检测的应用已十分广泛。面对确定数据的孤立点检测方法主要有基于模型的技术、基于详细性的技术和基于谜底的技术，在不确定数据中，有些数据对象因其不确定性可能会被当做孤立点处理，这样不仅会掩盖数据集中真正的孤立点，还有可能扭曲整体的数据分布，因此不确定数据孤立点检测比确定数据孤立点检测的难度更大。
　　4 基于动态代价敏感的数据挖掘模型
　　4.1 代价敏感
　　代价敏感性（Cost Sensitive）是指在分类问题中错误地把某一类A分为类B，就会造成巨大的损失，代价敏感学习（Cost- Sensitive Learning，CSL）是一种以误分类代价最小为衡量 标准的机器学习领域内的新方法，其最早被应用于解决医疗诊断系统中，在医疗机构中，对于一个不能确诊的病人在诊断时可能发生两种错误，一是将健康人误诊为病人，一是将病人误诊为健康人，前者在CSL中被称为FP（False Positive），后者称为FN（False Negative），在现实中两种错误的代价不同，CSL主要考虑在分类中，当不同的分类错误会导致不同惩罚力度时如何训练分类器。
　　根据不同问题解决方法的不同，对代价敏感学习的研究可分为直接根据不同的分类器构建一个代价敏感的学习模型，按照传统学习方法建立模型后，以贝叶斯风险理论对结果进行调整的代价敏感学习方法和通过改变原始训练数据分布对传统学习模型进行训练得到代价敏感的模型三类，其中直接建立代价敏感学习模型根据不同的分类其主要包括代价敏感决策树、代价敏感的支持向量机算法、基于神经网络分类算法的代价敏感学习方法和代价敏感的Boosting算法。由于重新设计分类器无法确定最好的误分代价系数，得到的模型可能偏向某一类样本，而决策树法有着较好的分类预测能力，能够方便地提取决策规则，是数据挖掘中最常用的一种方法，本文即介绍一种基于决策树算法的代价敏感不确定数据挖掘算法（CSDTU）。
　　4.2 建树算法
　　采用代价敏感决策树分类器处理不确定数据时，可以代价来代替熵，分裂属性选择具有最大正代价下降量的属性，原始数据集总代价与测试属性分裂后总代的差为属性选择标准PCR（Probabilistic Cost Reduction），末分裂原数据集D上的代价为ECM（D），则属性选择标准用公式可表示为：
　　式中Aj——数据集中第j个用例属性； Si——第j个用例属性分裂后的第i个子数据集；TestCost（D，Aj）——数据集D上所有用例对第j个用例属性总测试代价。
　　误分类代价在不确定数据上需要使用PC，计算时，以不确定离散属性Aucj第k个取值Ujk为例，概率使PC可用公式表示为：
　　在实际应用中，针对不确定数据的代价敏感决策树可简化为只考虑包含FN和FP 的两个类别，同时只考虑离散属性，则原数据集总误分类代价EMC（D）用公式表示为：
　　PC（P）、PC（N）分别为数据集D上所有正例和负例总概率势； Prn·MN、Prp·MP可能被错误分类为正类别的负例的潜在误分类总代价和相对应的正例潜在总代价。
　　4.3 实验分析
　　从UCI数据集中选择Bank、Breast-W、Credit-a、Car、Diabetes、Ecoli、Hepatitis、Heart-statlog、Sonar、Vote 10个二类别数据集共10，000个用例数，类别属性分正、负两个值，采用十重交叉验证法进行训练和测试，使用FP/FN分别为1000/1000、1000/2000、600/1000的三种误分类代价比例，数据不确定性从0～0.5，每次实验增加10%，得出实验结果，其部分实验结果如表1所示。
　　据实验结果分析可知此算法可减少节点个数，计算复杂度虽有所增加，但幅度很小，有效地提升了分类器效果，降低了总代价。
　　5 结束语
　　本文针对不确定数据的挖掘，介绍了一种基于代价敏感的决策树算法，并通过实验，验证了这一算法能够有效地降低总代价，算法较为简单，可节省不确定数据挖掘的费用，同时在不确定数据集的不确定较高时，仍能保持良好的挖掘效果，证实了这一算法的合理可行。
　　参考文献
　　[1] 孟光胜.基于关联度和代价敏感学习的决策树生成法[J].科学技术与工程，2013，（5）.
　　[2] 李华雄，周献中，黄兵等.决策粗糙集与代价敏感分类[J].计算机科学与探索，2013，（2）.
　　[3] 刘明建，张阳，王勇.代价敏感不确定决策树的不确定单批测试算法研究[J].工程数学学报，2012，（4）.
　　[4] 江彤，唐明珠，阳春华.基于不确定性采样的自训练代价敏感支持向量机研究[J].中南大学学报：自然科学版，2012，（2）：561-566.
　　[5] 史小伍，陶红，阚今中等.组合代价敏感支持向量机及其应用[J].计算机技术与发展，2012，（5）.
　　[6] 缪林松.基于代价敏感神经网络算法的软件缺陷预测[J].电子科技，2012，（6）.
　　[7] 赵士伟，卓力，王素玉等.一种基于NNIA多目标优化的代价敏感决策树构建方法[J].电子学报，2011，（10）.
　　[8] 陈晓林.基于动态代价敏感的机器学习研究[D].武汉：华中科技大学，2010.
　　[9] 李雪.不确定数据聚类研究[J].大连：大连理工大学，2009.
　　作者简介：
　　岑巍（1974-），男，浙江余姚人，中国人民大学硕士研究生毕业，现任职于上海浦东发展银行科技开发部，工程师；工作业绩：中间业务产品开发；主要研究方向和关注领域：商业银行中间业务产品研发和数据库优化、云计算等。