选择性模糊聚类算法

选择性模糊聚类分析算法高新波（XinboGao）西安电子科技大学电子工程学院’an,China©2006人工智能与模式识别专委会报告OUTLINEIntroductionFuzzyc-MeansAlgorithm(FCM)FeatureSelectedFCMAlgorithmSampleSelectedFCMAlgorithmFCMAlgorithmSelectiveEnsembleConcludingRemarksReferencesOUTLINEIntroductionFuzzyc-MeansAlgorithm(FCM)FeatureSelectedFCMAlgorithmSampleSelectedFCMAlgorithmFCMAlgorithmSelectiveEnsembleConcludingRemarksReferences方以类聚，物以群分——《战国策·齐策三》《周易·系辞上》齐宣王即位之初，好色、好味、好马而独不好士。淳于髡急，“一日而见七人于宣王”。宣王问：“今一朝而见七士，则士不亦多乎？”淳于髡曰：“不然。夫鸟同翼者而聚居，兽同足者而俱行。今求柴胡、桔梗于沮泽，则累世不得一焉；及之睾黍、梁父之阴，则郄车而载耳。夫物各有畴；今髡，贤者之畴也。王求士于髡，譬若挹水于河，而取火于燧也。髡将复见之，岂特七士也？”引子聚类分析就是按照一定的规律和要求对事物进行区分和分类的过程，在这一过程中没有任何关于类分的先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的准则。聚类属于无监督机器学习的范畴。何为聚类分析聚类分析是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物间的相似性（何清98）。聚类分析的数学描述snRxxxX,,,21sTkskkkRxxxx,,21待聚类分析的样本集描述样本的特征向量ciXXXckiXXXXXXiikic1,,1,21聚类结果的数学描述数据集的C划分cinkikikikcnhcinkkiRUM11,0;,1;,,1,0Crispc-PartitioncinkikikikcnfcinkkiRUM11,0;,1;,,1,0Fuzzyc-PartitionXxXxxkikkXiki01)(聚类：数据集的划分无标记的样本集空间划分空间覆盖OUTLINEIntroductionFuzzyc-MeansAlgorithm(FCM)FeatureSelectedFCMAlgorithmSampleSelectedFCMAlgorithmFCMAlgorithmSelectiveEnsembleConcludingRemarksReferences聚类分析目标函数fccinkikmikmMUtspxDPUJ..),(),(min112hccinkikikMUtspxDPUJ..),(),(min1121硬聚类的目标函数：fccinkikikMUtspxDPUJ..),(),(min11222模糊聚类的目标函数：FCM算法—交替优化隶属函数更新公式：1112)()()(cjmbjkbikbikddcixpnkmbiknkkmbikbi,,2,1for,1)(1)()1(聚类原型更新公式：FCM算法—交替优化FCM算法的迭代过程FCM算法的优点FCM算法的目标函数与Rs的希尔伯特空间结构（正交投影和均方逼近理论）有密切的关系，因此具有深厚的数学基础；以FCM算法为基础，人们又提出基于其它原型的模糊聚类算法，形成了一大批FCM-type的算法；FCM类型的算法设计简单，可转化为优化问题，可借助最优化理论的研究成果；算法复杂度低，在许多领域获得了非常成功的应用。FCM算法的研究方向聚类趋势研究数据的可分性研究基于抽样的假设检验方法聚类分析研究传统优化算法智能计算的方法与核函数的结合与流形学习的结合聚类有效性研究加权指数的优选聚类类别数的自动确定面向应用的聚类分析方法特征选择性聚类样本选择性聚类聚类算法的选择性集成OUTLINEIntroductionFuzzyc-MeansAlgorithm(FCM)FeatureSelectedFCMAlgorithmSampleSelectedFCMAlgorithmFCMAlgorithmSelectiveEnsembleConcludingRemarksReferences特征选择性FCM算法FCM算法应用于数据挖掘中存在的问题：FCM-type算法在进行聚类分析时认为每维特征的贡献是均匀的，并不进行特征的选择；在实际应用中，很多聚类结构是存在于特征空间的子空间中的；为了挖掘这样的聚类结构，就必须能够找到张成该子空间的变量，即进行特征选择。特征选择性FCM算法fccinksjijkjjmikwMUtspxdwPUJ..),(),(min111fccinkikmikmMUtspxDPUJ..),(),(min112FCM目标函数：基于特征加权的FCM目标函数：JieLi,XinboGao,LichengJiao,“Anovelfeatureweightedfuzzyclusteringalgorithm”,D.Slezaketal.(Eds.):RSFDGrC2005,LNAI3641,pp.412-420,2005,Springer-VerlagBerlinHeidelberg2005ReliefF算法Relief算法是Kira和Rendell在1992年提出的，限于解决两类的分类问题的特征选择；1994年Kononenko扩展了Relief算法，使得ReliefF可以解决多类问题的特征选择；ReliefF算法是给特征集中每一特征赋予一定的权重。KiraK.,RendellLA.,Apracticalapproachtofeatureselection,Proceedingsofthe9thInternationalWorkshoponMachineLeaning,SanFrancisco,CA:MorganKaufmann,1992,249-256ReliefF算法RjXXhxjihitdiff1)min()max(_)(1)min()max())((1)(_iljiixclasslRjXXmxxclassPlPmissdiffRmissdiffRhitdiffww__同类样本间的差异：异类样本间的差异：特征权值更新公式：实验结果IRIS数据由四维空间中的150个样本点组成，每一个样本的4个分量分别表示IRIS的PetalLength，PetalWidth，SepalLength和SepalWidth。包含了3个IRIS种类Setosa，Versicolor和Virginica，每类各有50个样本。其中Setosa与其它两类间较好地分离，而Versicolor和Virginica之间存在交迭。W-k-MeansAlgorithmJoshuaZhexueHuang，MichaelK.Ng,HongqiangRong,andZichenLi,AutomatedVariableWeightingink-MeansTypeClustering,IEEETrans.onPAMI,27(5):657-668,2005W-k-MeansAlgorithmJoshuaZhexueHuang，MichaelK.Ng,HongqiangRong,andZichenLi,AutomatedVariableWeightingink-MeansTypeClustering,IEEETrans.onPAMI,27(5):657-668,2005OUTLINEIntroductionFuzzyc-MeansAlgorithm(FCM)FeatureSelectedFCMAlgorithmSampleSelectedFCMAlgorithmFCMAlgorithmSelectiveEnsembleConcludingRemarksReferencesSampleselectiveFCMnkkfccinkikmikkmwMUtspxDwPUJ11121,..),(),(min目标函数：11)1(2),(),(crmrkikikpxDpxDnkmikknkkmikkiwxwv11迭代公式Application基于直方图加权的图像分割(FCM)原图像1DH加权2DH加权高新波，李洁，“基于加权FCM与统计检验指导的多阈值图像自动分割算法”，电子学报，32(4):661-664,2004FCMforLargeDataSetJieLi,XinboGao,LichengJiao,“ANovelTypical-Sample-WeightedClusteringAlgorithmforLargeDataSets”,LectureNotesinArtificialIntelligence,LNAI3801:696-703,2005原子聚类典型样本样本加权FCMforLargeDataSet对聚类中心的影响算法的可扩展性JieLi,XinboGao,LichengJiao,“ANovelTypical-Sample-WeightedClusteringAlgorithmforLargeDataSets”,LectureNotesinArtificialIntelligence,LNAI3801:696-703,2005OUTLINEIntroductionFuzzyc-MeansAlgorithm(FCM)FeatureSelectedFCMAlgorithmSampleSelectedFCMAlgorithmFCMAlgorithmSelectiveEnsembleConcludingRemarksReferencesPAC学习模型与BoostingPAC模型：ProbablyApproximatelyCorrection强可学习性：若存在一个多项式级的学习算法来识别一组概念，并且识别正确率很高弱可学习性：而如果学习算法识别一组概念的正确率仅比随机猜测略好等价性问题：Kearns和Valiant提出了弱学习算法与强学习算法的等价性问题，即是否可以将弱学习算法提升成强学习算法因此，只需要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法。Boosting算法：Schapire(1990)通过一个构造性方法对该问题作出了肯定的证明AdaBoosting算法：Freund集成学习集成学习（Ensemble）是一种机器学习范式，它使用多个（通常是同质的）学习器来解决同一个问题。问题…...…...问题集成学习中使用的多个学习器称为个体学习器当个体学习器均为决策树时，称为“决策树集成”当个体学习器均为神经网络时，称为“神经网络集成”当个体学习器均为聚类算法时，称为“聚类算法集成”…………集成学习的重要性由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际权威T.G.Dietterich称为当前机器学习四大研究方向之首。[T.G.Dietterich,AIMag97]问题：对20维超立方体空间中的区域分类从上到下的四条线分别表示：平均神经网