梁吉业-面向大数据的高效特征选择与聚类算法(CRSSC-CWI-CGrC-2013)

面向大数据的高效特征选择与聚类算法CRSSC-CWI-CGrC2013报告人：梁吉业太原师范学院山西大学计算智能与中文信息处理教育部重点实验室ShanxiUniversity主要内容第一部分：大数据处理背景第二部分：高效特征选择算法第三部分：高维复杂数据聚类算法基于样本表征整体的特征选择算法基于批增量的特征选择算法第四部分：大数据处理展望符号数据K-Modes型算法及其收敛性混合数据的有效聚类算法非平衡数据的有效聚类算法ShanxiUniversity第一部分：大数据处理背景3ShanxiUniversity什么是大数据？维基百科：大数据是指一个超大的、难以用现有常规的数据库管理技术和工具处理的数据集。大数据=“海量数据”+“复杂类型的数据”4EBShanxiUniversity大数据4V特征5ShanxiUniversity大数据存在于各行各业中电子商务金融日志分析国土安全交通控制机械制造社交网络移动互联网智慧医疗科学研究交易分析视频监控6ShanxiUniversity需要对多源、异构、多模态数据建立起智能计算的理论和方法图像分享网站社交网站论坛微博其他传感器…监控视频视频分享网站互联网网页大数据时代所面向的处理数据7ShanxiUniversity8大数据研究基本途径ShanxiUniversity第二部分：高效特征选择算法9ShanxiUniversity特征选择是模式识别、机器学习、图像处理与数据挖掘等领域的一个挑战性问题。它致力于保持原始特征的某种表达能力。高效的特征选择算法对于大规模的复杂数据处理来说是非常重要的。大数据的高效特征选择算法基于样本表征整体的特征选择算法基于批增量的特征选择算法特征选择10ShanxiUniversity（1）基于样本表征整体的特征选择算法问题提出传统的特征选择方法都是在整个样本集上进行统一分析和处理，尽管它能一次性地获得整体数据集的特征选择结果，但是很难适应大数据背景下的决策分析。该方法立足于统计学原理，基于样本表征整体思想，通过拆分原始大数据集为多个样本子集，求解各样本子集的特征选择结果，并将其融合为总体的特征选择结果，大大提高了计算效率。11ShanxiUniversity基本思想融合所有降维结果在子样本集上降维高效特征选择算法抽样12ShanxiUniversity遍历性：原始大数据集上的所有样本都被抽样取到。传递性：多个样本子集之间有部分相同的对象，即保证样本子集之间信息的可传递性。样本子集规模与抽样原则一致性：样本子集上决策属性值的比率与原始大数据表的决策属性值的比率相同。222ZMEσ×=确定抽样规模抽样原则有部分相同的对象样本子集S1样本子集S2样本子集Sj……13ShanxiUniversity样本子集特征选择YuhuaQian,JiyeLiang,WitoldPedrycz,ChuangyinDang.Positiveapproximation:anacceleratorforattributereductioninroughsettheory,ArtificialIntelligence,2010,174:597-618.研究者也可根据需要选择使用其它的特征降维算法。这里选择上述四种度量和加速算法主要是为了与前期工作进行结合和比较。加速特征降维算法属性依赖度Shannon熵互补熵组合熵基于以下四种度量，使用加速特征降维算法求解样本子集上的降维结果。14ShanxiUniversity融合各样本子集降维结果1212{',',,',',',,'}kkknRaaaaaa++=11(1)2kjinjnnwk=−++=∑(1)(1)2innwni+=−+第i个属性的权重特征排序：对每个赋权特征求其权重和，根据权重的和从大到小对特征排序，用户可根据需求选取所需的特征个数。•为各样本子集降维结果中的每个特征指派权重•基于权重的和对特征排序主要思想：ShanxiUniversityDatasetsFSPAE-FSATicdata20002,5,9,18,31,37,40,43,44,45,47,48,49,54,55,57,58,59,61,63,64,68,80,832,5,7,9,15,18,26,27,43,44,45,47,48,49,52,54,55,57,59,61,62,64,68,83Nursery1,2,3,4,5,6,7,81,2,3,4,5,6,7,8Letter2,3,4,8,9,10,11,12,13,14,15,161,2,3,4,5,6,8,9,10,11,12,13,15Adult1,2,3,4,7,8,11,131,2,3,4,6,7,11,13Shuttle1,2,3,51,2,3,5Connect1,2,3,4,5,7,8,9,10,11,13,14,15,16,17,19,20,21,22,23,25,26,27,28,30,31,32,33,34,35,37,38,39,411,2,3,4,5,7,8,9,10,11,13,14,15,16,17,19,20,21,22,23,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41实验分析基于Shannon熵的特征降维结果比较16ShanxiUniversity•两个较大规模的数据集被选取来进一步验证算法的高效性•使用加速算法在PC机上100小时内未得到数据集的降维结果。基于样本表征整体的特征降维算法的实验结果处理大规模数据集17ShanxiUniversity科学意义JiyeLiang,FengWang,ChuangyinDang,YuhuaQian.Anefficientroughfeatureselectionalgorithmwithamulti-granulationview,InternationalJournalofApproximateReasoning,2012,53:912-926.提出的样本表征整体策略为大规模数据背景下的数据分析提供了新途径。18ShanxiUniversity（2）基于批增量的特征选择算法在诸如金融、电信、证券、大型仓储超市等行业的管理中，决策分析的时效性尤为关键。而这些领域的数据的实时更新、动态累积特点更加突出，这就要求发展高效的增长性数据特征选择技术，以适应在线决策分析的要求。针对这一问题，目前的单增量特征选择方法显然不能满足决策的实时性需求。为此，提出了基于批增量的增长性数据特征选择方法。问题提出19ShanxiUniversity数据集U增量数据集UX信息熵用来度量特征的重要度。U和UX上会有一部分对象的取值是相同的，即划分块是可合并的。U和UX中属性取值相同的对象集信息熵的批增量机制20ShanxiUniversity通过分析增加一组数据后样本集上数据分布的变化，来确定信息熵的增量机制。Δ的计算主要由U和UX中属性取值相同的样本集来确定由于U上的信息熵通常是已知的。因此，在新增加数据集UX后，新的论域上的熵只需计算UX上的熵和Δ即可。21ShanxiUniversity三种信息熵的批增量机制互补熵组合熵Shannon熵22ShanxiUniversity内部重要度：外部重要度：确定特征重要度上述三种熵的一个统一表示由于熵的计算主要用来确定特征选择过程中的特征重要度。因此，为避免重复计算原始数据而产生大量的冗余，这里使用信息熵的增量机制来确定特征的重要度。23ShanxiUniversity信息熵的增量机制原有降维结果上确定新的降维基于批增量的特征降维方法24ShanxiUniversity实验结果批增量与单增量特征降维方法计算时间比较25ShanxiUniversity科学意义JiyeLiang,FengWang,ChuangyinDang,YuhuaQian.Agroupincrementalapproachtofeatureselectionapplyingroughsettechnique,IEEETransactionsonKnowledgeandDataEngineering,DOI：10.1109/TKDE.2012.146提出的信息熵批增量递推计算可用于多个数据集信息熵的融合，为增长性数据的分析与处理、多源信息融合提供了新思路。26ShanxiUniversity第三部分：高维复杂数据的聚类算法27ShanxiUniversity聚类分析因能在无先验信息的条件下，探测数据在特征空间中的分布或类别结构，从而提供潜在有价值的信息。然而，大数据具有表示的混合性、分布的非均衡性等特点以及海量性特征。因此，无论从理论、算法还是实践层面，针对大数据进行聚类仍有很多极具挑战性的问题亟待解决。聚类算法28高维复杂数据聚类算法符号数据K-Modes型算法及其收敛性混合数据的有效聚类算法非平衡数据的有效聚类算法ShanxiUniversity(1)符号数据K-Modes型算法与收敛性分析问题提出在聚类分析的众多算法中，K-Means算法因其简单、高效得到了非常广泛的应用。但它仅仅局限于数值数据。然而现实投资决策领域中存在大量符号数据,因此,符号数据聚类已成为一个重要研究课题。为了解决这一问题，香港大学JoshuaZhexueHuang教授在保持K-Means算法优点的前提下，发展了面向符号数据的K-Modes聚类算法并证明了算法的收敛性。近年来，许多学者为了提高了K-Modes算法的有效性，发展了一系列新的算法。29ShanxiUniversity已有的改进K-Modes型聚类算法He和Ng等人利用属性值在类内出现的频率来反映Modes对类的代表能力，并将其应用于K-Modes聚类算法中。[ProceedingsofInternationalConferenceComputationalIntelligence&Security,2005]San等人提出一种基于频率的类表示方法，一个类是由每个属性中的所有属性值来表示，并通过属性值在类内的出现频率作为权值反映它对该类的代表能力，并将该方法应用于K-Modes聚类算法中。[InternationalJournalofAppliedMathematics&ComputerScience,2004]Kim等人提出一种基于频率的模糊Mode，并将其用于模糊K-Modes聚类算法中。[PatternRecognition,2005]Lee等人提出一种泛化的K-Modes类型聚类算法，该算法在每个属性上选择拥有最大频率的前P个属性值来代表该类，其中P是一个参数。[FuzzySets&Systems,2009]30ShanxiUniversity上述改进算法虽然提高了算法的有效性，但是收敛性问题一直没有得到解决。课题组在K-Modes算法框架下发展了两种新的迭代更新策略。不仅从理论上证明了基于这两种策略的K-Modes算法的收敛性，而且在实验上对算法的有效性进行了验证。策略一：调整目标函数策略二：调整相异性测度两种新策略31ShanxiUniversity策略一：调整目标函数目标函数：用于反映类内差异总和,希望最小化这部分。用于激励更多的属性值为类的识别做出应有的贡献，这部分越小，越多地属性值被用于表示类。用于平衡目标函数中前后两个部分对聚类过程的贡献大小。相异性测度：32ShanxiUniversity策略二：调整相异性测度目标函数：相异性测度：33ShanxiUniversity实验分析(以BreastCancer数据集为例)发展的两种迭代更新策略能够使得算法收敛到局部最优解。上述改进算法不能保证收敛到局部最优解。34ShanxiUniversityLiangBai,JiyeLiang,ChuangyinDang,FuyuanCao.TheimpactofclusterrepresentativesontheconvergenceoftheK-Mode