1、选择性模糊聚类分析算法 高新波（Xinbo Gao）西安电子科技大学电子工程学院http:/ University, Xian, China 2006,人工智能与模式识别专委会报告,OUTLINE,OUTLINE,方以类聚，物以群分战国策 齐策三周易 系辞上,齐宣王即位之初，好色、好味、好马而独不好士。淳于髡急，“一日而见七人于宣王”。 宣王问：“今一朝而见七士，则士不亦多乎？” 淳于髡曰：“不然。夫鸟同翼者而聚居，兽同足者而俱行。今求柴胡、桔梗于沮泽，则累世不得一焉；及之睾黍、梁父之阴，则郄车而载耳。夫物各有畴；今髡，贤者之畴也。王求士于髡，譬若挹水于河，而取火于燧也。髡将复见之，岂特七士也
2、？”,引子,聚类分析就是按照一定的规律和要求对事物进行区分和分类的过程，在这一过程中没有任何关于类分的先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的准则。 聚类属于无监督机器学习的范畴。,何为聚类分析,聚类分析是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物间的相似性（何清98）。,聚类分析的数学描述,聚类结果的数学描述,数据集的C划分,Crisp c-Partition,Fuzzy c-Partition,聚类：数据集的划分,无标记的样本集,空间划分,空间覆盖,OUTLINE,聚类分析目标函数,硬聚类的 目标函数：,模糊聚类的
3、目标函数：,FCM算法交替优化,隶属函数更新公式：,聚类原型更新公式：,FCM算法交替优化,FCM算法的迭代过程,FCM算法的优点,FCM算法的目标函数与Rs的希尔伯特空间结构（正交投影和均方逼 近理论）有密切的关系，因此具有深厚的数学基础； 以FCM算法为基础，人们又提出基于其它原型的模糊聚类算法，形 成了一大批FCM-type的算法； FCM类型的算法设计简单，可转化为优化问题，可借助最优化理论 的研究成果； 算法复杂度低，在许多领域获得了非常成功的应用。,FCM算法的研究方向,聚类趋势研究数据的可分性研究基于抽样的假设检验方法聚类分析研究传统优化算法智能计算的方法与核函数的结合与流形学习
4、的结合聚类有效性研究加权指数的优选聚类类别数的自动确定,面向应用的聚类分析方法 特征选择性聚类 样本选择性聚类 聚类算法的选择性集成,OUTLINE,特征选择性FCM算法,FCM算法应用于数据挖掘中存在的问题：FCM-type算法在进行聚类分析时认为每维特征的贡献是均匀的，并不进行特征的选择；在实际应用中，很多聚类结构是存在于特征空间的子空间中的；为了挖掘这样的聚类结构，就必须能够找到张成该子空间的变量，即进行特征选择。,特征选择性FCM算法,FCM目标函数：,基于特征加权的FCM目标函数：,Jie Li, Xinbo Gao, Licheng Jiao, “A novel feature w
5、eighted fuzzy clustering algorithm”, D. Slezak et al. (Eds.): RSFDGrC2005, LNAI 3641, pp.412-420, 2005, Springer-Verlag Berlin Heidelberg 2005,ReliefF算法,Relief算法是Kira和Rendell在1992年提出的，限于解 决两类的分类问题的特征选择； 1994年Kononenko扩展了Relief算法，使得ReliefF可 以解决多类问题的特征选择； ReliefF算法是给特征集中每一特征赋予一定的权重。,Kira K., Rendell L
6、 A., A practical approach to feature selection, Proceedings of the 9th International Workshop on Machine Leaning, San Francisco, CA: Morgan Kaufmann, 1992, 249-256,ReliefF算法,同类样本间的差异：,异类样本间的差异：,特征权值更新公式：,实验结果,IRIS数据由四维空间中的150个样本点组成，每一个样本的4个分量分别表示IRIS的Petal Length，Petal Width，Sepal Length和Sepal Width
7、。包含了3个IRIS种类Setosa，Versicolor和Virginica，每类各有50个样本。其中Setosa与其它两类间较好地分离，而Versicolor和Virginica之间存在交迭。,W-k-Means Algorithm,Joshua Zhexue Huang，Michael K. Ng, Hongqiang Rong, and Zichen Li, Automated Variable Weighting in k-Means Type Clustering, IEEE Trans. on PAMI, 27(5): 657-668, 2005,W-k-Means Algori
8、thm,Joshua Zhexue Huang，Michael K. Ng, Hongqiang Rong, and Zichen Li, Automated Variable Weighting in k-Means Type Clustering, IEEE Trans. on PAMI, 27(5): 657-668, 2005,OUTLINE,Sample selective FCM,目标函数：,迭代公式,Application,基于直方图加权的图像分割 (FCM),原图像 1DH加权 2DH加权,高新波，李洁，“基于加权FCM与统计检验指导的多阈值图像自动分割算法”，电子学报， 32
9、(4): 661-664, 2004,FCM for Large Data Set,Jie Li, Xinbo Gao, Licheng Jiao, “A Novel Typical-Sample-Weighted Clustering Algorithm for Large Data Sets ”, Lecture Notes in Artificial Intelligence, LNAI3801: 696-703, 2005,原子聚类典型样本样本加权,FCM for Large Data Set,对聚类中心的影响,算法的可扩展性,Jie Li, Xinbo Gao, Licheng Ji
10、ao, “A Novel Typical-Sample-Weighted Clustering Algorithm for Large Data Sets ”, Lecture Notes in Artificial Intelligence, LNAI3801: 696-703, 2005,OUTLINE,PAC学习模型与Boosting,PAC模型：Probably Approximately Correction强可学习性：若存在一个多项式级的学习算法来识别一组概念，并且识别正确率很高弱可学习性：而如果学习算法识别一组概念的正确率仅比随机猜测略好等价性问题：Kearns和Valiant提
11、出了弱学习算法与强学习算法的等价性问题，即是否可以将弱学习算法提升成强学习算法,因此，只需要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法。Boosting算法：Schapire (1990)通过一个构造性方法对该问题作出了肯定的证明 AdaBoosting算法：Freund,集成学习,集成学习（Ensemble）是一种机器学习范式，它使用多个（通常是同质的）学习器来解决同一个问题。,集成学习中使用的多个学习器称为个体学习器当个体学习器均为决策树时，称为“决策树集成”当个体学习器均为神经网络时，称为“神经网络集成”当个体学习器均为聚类算法时，称为“聚类算法集成” ,集成学习的重
12、要性,由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际权威 T.G. Dietterich 称为当前机器学习四大研究方向之首。T.G. Dietterich, AIMag97,问题：对20维超立方体空间中的区域分类从上到下的四条线分别表示： 平均神经网络错误率 最好神经网络错误率 两种神经网络集成的错误率令人惊奇的是，集成的错误率比最好的个体还低,L.K. Hansen & P. Salamon, TPAMI90,如何构造好的集成,选择性集成,既然多个个体的集成比单个个体更好，那么是不是个体越多越好?,更多的个体意味着： 在预测时需要更大的计算开销
13、，因为要计算更多的个体预测 更大的存储开销，因为有更多的个体需要保存,个体的增加将使得个体间的差异越来越难以获得,Many Could be Better Than All：在有一组个体学习器可用时，从中选择一部分进行集成，可能比用所有个体学习器进行集成更好。Z.-H. Zhou et al., AIJ02,Bagging算法,Breiman L. Bagging predicators. Machine Learning, 1996,24(2):123140.,集成学习算法Bagging：在训练阶段，各学习器的训练集由原始训练集利用可重复取样(bootstrap sampling)技术获得，
14、训练集的规模通常与原始训练集相当。这样，原始训练集中某些示例可能在新的训练集中出现多次，而另外一些示例则可能一次也不出现。 研究表明，Bagging 可以显著提高不稳定的基学习器的泛化能力。,Bagging 算法和其他大多数的集成学习算法都是为监督学习而设计的，对聚类这样的非监督学习来说，由于训练样本缺乏类别标记，聚类结果之间没有直接的对应关系，这将使得对个体学习器的结合难以直接进行。,选择性聚类集成,Breiman L. Bagging predicators. Machine Learning, 1996,24(2):123140.,集成学习一般包含两个阶段：个体生成阶段：通过不同的个体生
15、成方式产生不同的个体标记向量。个体学习器结合阶段：可以采用投票等方式将个体标记向量进行结合。,聚类分析集成学习：个体生成阶段：（1）采用类似Bagging 算法中产生个体训练集的方式产生用于聚类的训 练集，即通过可重复取样技术从原向量集中产生若干训练集；（2）对每个训练集用FCM算法进行分析，获得聚类中心；（3）利用所得到的聚类中心对原向量集分别进行标记，获得标记向量。,选择性聚类集成,唐伟，周志华，基于Bagging的选择性聚类集成，软件学报，16(4): 496-502, 2005,注意：得到的标记向量由于缺乏先验的类别信息，并不能直接用于下一 阶段的结论合成。 例如：1，2，2，1，1，
16、3，3，2，3，3，2，2，1，1为了对聚类结果进行结合，个体标记向量必须经过匹配建立相互之间的对应关系。,个体学习器结合阶段：基于权值的选择性投票策略聚类标记向量间的互信息在某种程度上能够刻画聚类个体间的紧密程度，利用互信息来表示个体标记向量的权值将有助于得到更好的集成结论。,OUTLINE,Concluding Remarks,FCM算法具有完善的理论基础和广泛的应用前景； 对其加以适当的改造和修正将进一步扩展其应用范围； FCM聚类分析的选择性研究：特征、样本、算法集成； 从FCM算法选择性研究中获得的启示： 应用驱动理论研究 放宽算法的基本假设会带来更多的创新成果 它山之石可以攻玉,O
17、UTLINE,References,Jie Li, Xinbo Gao, Licheng Jiao, A novel feature weighted fuzzy clustering algorithm, D. Slezak et al. (Eds.): RSFDGrC2005, LNAI 3641, pp.412-420, 2005, Springer-Verlag Berlin Heidelberg 2005 Kira K., Rendell L A., A practical approach to feature selection, Proceedings of the 9th I
18、nternational Workshop on Machine Leaning, San Francisco, CA: Morgan Kaufmann, 1992, 249-256Joshua ZhexueHuang，Michael K. Ng, Hongqiang Rong, and Zichen Li, Automated Variable Weighting in k-Means Type Clustering, IEEE Trans. on PAMI, 27(5): 657-668, 2005高新波，李洁，“基于加权FCM与统计检验指导的多阈值图像自动分割算法”，电子学报，32(4)
19、: 661-664, 2004Jie Li, Xinbo Gao, Licheng Jiao, A Novel Typical-Sample-Weighted Clustering Algorithm for Large Data Sets, CIS2005Breiman L. Bagging predicators. Machine Learning, 1996, 24(2):123140.唐伟，周志华，基于Bagging的选择性聚类集成，软件学报，16(4): 496-502, 2005,THANK YOU,Xinbo GaoSchool of Electronic EngineeringXidian UniversityXian 710071P.R.ChinaxbgaoIEEE.orghttp:/ University, Xian, China 2006,
