选择性模糊聚类分析算法

1、人工智能与模式识别专委会报告人工智能与模式识别专委会报告人工智能与模式识别专委会报告人工智能与模式识别专委会报告人工智能与模式识别专委会报告人工智能与模式识别专委会报告方以类聚，物以群分方以类聚，物以群分战国策战国策 齐策三齐策三周易周易 系辞上系辞上 齐宣王即位之初，好色、好味、好马而独不好士。淳于髡急，齐宣王即位之初，好色、好味、好马而独不好士。淳于髡急，“一日而见七人于宣王一日而见七人于宣王”。 宣王问：宣王问：“今一朝而见七士，则士不亦多乎？今一朝而见七士，则士不亦多乎？” 淳于髡曰：淳于髡曰：“不然。不然。夫鸟同翼者而聚居，兽同足者而俱行。夫鸟同翼者而聚居，兽同足者而俱行。今求柴胡、

2、桔梗于沮泽，则累世不得一焉；及之睾黍、梁父之阴，今求柴胡、桔梗于沮泽，则累世不得一焉；及之睾黍、梁父之阴，则郄车而载耳。夫物各有畴；今髡，贤者之畴也。王求士于髡，譬则郄车而载耳。夫物各有畴；今髡，贤者之畴也。王求士于髡，譬若挹水于河，而取火于燧也。髡将复见之，岂特七士也？若挹水于河，而取火于燧也。髡将复见之，岂特七士也？” 聚类分析聚类分析就是按照一定的规律和要求对事物进行区分和就是按照一定的规律和要求对事物进行区分和分类的过程，在这一过程中没有任何关于类分的分类的过程，在这一过程中没有任何关于类分的先验知识先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的准则。没有教师指导，仅靠事物间

3、的相似性作为类属划分的准则。 聚类属于聚类属于无监督机器学习无监督机器学习的范畴的范畴。 聚类分析聚类分析是一个古老的问题，它伴随着人类社会的产生是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物间的相似性（何清并认识事物间的相似性（何清98）。snRxxxX,21sTkskkkRxxxx,21ciXXXckiXXXXXXiikic1,1,21 cinkikikikcnhcinkkiRUM11,0;, 1;,1 , 0cinkikikikcnfcinkkiRUM11,0;, 1;,1 , 0

4、XxXxxkikkXiki01)(fccinkikmikmMUtspxDPUJ. .),(),(min112hccinkikikMUtspxDPUJ. .),(),(min1121fccinkikikMUtspxDPUJ. .),(),(min112221112)()()(cjmbjkbikbikddcixpnkmbiknkkmbikbi, 2 , 1for,1)(1)()1(FCM算法应用于数据挖掘中存在的问题：算法应用于数据挖掘中存在的问题：FCM-type算法在进行聚类分析时认为每维特征的贡献是均匀的，算法在进行聚类分析时认为每维特征的贡献是均匀的，并不进行特征的选择；并不进行特征的选择

5、；在实际应用中，很多聚类结构是存在于特征空间的子空间中的；在实际应用中，很多聚类结构是存在于特征空间的子空间中的；为了挖掘这样的聚类结构，就必须能够找到张成该子空间的变量，为了挖掘这样的聚类结构，就必须能够找到张成该子空间的变量，即进行特征选择。即进行特征选择。fccinksjijkjjmikwMUtspxdwPUJ. .),(),(min111fccinkikmikmMUtspxDPUJ. .),(),(min112RjXXhxjihitdiff1)min()max(_)(1)min()max()(1)(_iljiixclasslRjXXmxxclassPlPmissdiffRmissdif

6、fRhitdiffww_nkkfccinkikmikkmwMUtspxDwPUJ11121,. .),(),(min11)1(2),(),(crmrkikikpxDpxDnkmikknkkmikkiwxwv11 集成学习（集成学习（Ensemble）是一种机器学习范式，它使用多）是一种机器学习范式，它使用多个（通常是同质的）学习器来解决同一个问题。个（通常是同质的）学习器来解决同一个问题。 问题 . . 问题集成学习中使用的多个学习器称为个体学习器集成学习中使用的多个学习器称为个体学习器当个体学习器均为决策树时，称为当个体学习器均为决策树时，称为“决策树集成决策树集成”当个体学习器均为神经网络

7、时，称为当个体学习器均为神经网络时，称为“神经网络集成神经网络集成”当个体学习器均为聚类算法时，称为当个体学习器均为聚类算法时，称为“聚类算法集成聚类算法集成” l由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际权威国际机器学习界的研究热点，并被国际权威 T.G. Dietterich 称为当前机称为当前机器学习四大研究方向之首。器学习四大研究方向之首。T.G. Dietterich, AIMag97问题：问题：对对2020维超立方体空间中的维超立方体空间中的区域分类区域分类从上到下的四条

8、线分别表示：从上到下的四条线分别表示： 平均神经网络错误率平均神经网络错误率 最好神经网络错误率最好神经网络错误率 两种神经网络集成的错误率两种神经网络集成的错误率令人惊奇的是，集成的错误率比令人惊奇的是，集成的错误率比最好的个体还低最好的个体还低 L.K. Hansen & P. Salamon, TPAMI90期望结果个体1 (精度33.3%)个体2 (精度33.3%)个体3 (精度33.3%)集成(精度33.3%)投票个体必须有差异期望结果个体1 (精度33.3%)个体2 (精度33.3%)个体3 (精度33.3%)集成 (精度0%)投票个体精度不能太低个体学习器越精确、差异越大

9、，集成越好EEAA. Krogh & J. Vedelsby, NIPS94既然多个个体的集成比单个个体更好，那么是既然多个个体的集成比单个个体更好，那么是不是个体越多越好不是个体越多越好? ?更多的个体意味着：更多的个体意味着： 在预测时需要更大的计算开销，因为要计算更多的个体预测在预测时需要更大的计算开销，因为要计算更多的个体预测 更大的存储开销，因为有更多的个体需要保存更大的存储开销，因为有更多的个体需要保存个体的增加将使得个体间的差异越来越难以获得个体的增加将使得个体间的差异越来越难以获得Many Could be Better Than All：在有一组个体学习器：在有一组个

10、体学习器可用时，从中选择一部分进行集成，可能比用所有个可用时，从中选择一部分进行集成，可能比用所有个体学习器进行集成更好。体学习器进行集成更好。Z.-H. Zhou et al., AIJ02Breiman L. Bagging predicators. Machine Learning, 1996,24(2):123140.Breiman L. Bagging predicators. Machine Learning, 1996,24(2):123140.集成学习一般包含两个阶段：集成学习一般包含两个阶段：个体生成阶段：个体生成阶段：通过不同的个体生成方式产生不同的个体标记向量。通过不同的

11、个体生成方式产生不同的个体标记向量。个体学习器结合阶段：个体学习器结合阶段：可以采用投票等方式将个体标记向量进行结合。可以采用投票等方式将个体标记向量进行结合。聚类分析集成学习：聚类分析集成学习：个体生成阶段：个体生成阶段：（1）采用类似采用类似Bagging 算法中产生个体训练集的方式产生用于聚类的训算法中产生个体训练集的方式产生用于聚类的训 练集，即通过可重复取样技术从原向量集中产生若干训练集；练集，即通过可重复取样技术从原向量集中产生若干训练集；（2）对每个训练集用）对每个训练集用FCM算法进行分析，获得聚类中心；算法进行分析，获得聚类中心；（3）利用所得到的聚类中心对原向量集分别进行标

12、记，获得标记向量。）利用所得到的聚类中心对原向量集分别进行标记，获得标记向量。唐伟，周志华，基于唐伟，周志华，基于Bagging的选择性聚类集成，软件学报，的选择性聚类集成，软件学报，16(4): 496-502, 2005注意：注意：得到的标记向量由于缺乏先验的类别信息，并不能直接用于下一得到的标记向量由于缺乏先验的类别信息，并不能直接用于下一 阶段的结论合成。阶段的结论合成。 例如：例如：1，2，2，1，1，3，3，2，3，3，2，2，1，1为了对聚类结果进行结合，个体标记向量必须经过匹配建立相互之间的对为了对聚类结果进行结合，个体标记向量必须经过匹配建立相互之间的对应关系。应关系。个体学习器结合阶段：个体学习器结合阶段：基于权值的选择性投票策略基于权值的选择性投票策略聚类标记向量间的互信息在某种程度上能够刻画聚类个体间的紧密程度，聚类标记向量间