李凯，王亮，周宇飞

（河北大学数学与计算机学院，河北保定 071002）

基于偶对约束和马氏距离的半监督模糊聚类算法

李凯，王亮，周宇飞

（河北大学数学与计算机学院，河北保定 071002）

研究了基于偶对约束的半监督模糊聚类，将马氏距离引入到半监督模糊聚类SCAPC（semi-supervised fuzzy clustering algorithm with pairwise constraints）中，获得了一种新的半监督模糊聚类目标函数，通过求解优化问题，提出了一种基于偶对约束和马氏距离的半监督模糊聚类算法M-SCAPC（Modified-SCAPC）.针对选择的标准数据集和人工数据集，对提出的算法M-SCAPC进行了实验研究，并与FCM（fuzzy C-means）、AFCC（active fuzzy constrained clustering）和SCAPC算法的聚类性能进行了比较，表明了提出的算法M-SCAPC在收敛速度和正确率方面的有效性.

半监督聚类；偶对约束；度量学习；马氏距离

1 引入马氏距离的半监督聚类算法M-SCAPC

给定一个具有N个样本的数据集X＝｛xi｜i∈｛1，…，N｝｝，假设集合X中的样本点被分为c个簇S1，S2，…，Sc，并记vk（k∈｛1，…，c｝）表示c个聚类中心，uik表示样本点xi属于簇Sk的隶属度，V和U分别表示由聚类中心构成的集合与由隶属度构成的矩阵.

欧氏距离较适用于球形数据，然而该度量受样本间的相关性影响较大，在处理非球形数据或高维数据时聚类效果较差，同时聚类速度也较慢，而马氏距离在处理相关性较大的数据集时具有较好的效果［6］.针对这种情况，研究了使用马氏距离的半监督聚类，获得了如下的目标函数：

下面给出算法M-SCAPC的描述：

1）初始化最大簇数Cmax，设置簇的阈值e和ε，并初始化簇中心和隶属度；

2）计算协方差矩阵Ck和马氏距离；

3）利用式（3）和（4）分别计算参数β和参数α；

4）计算各簇的势，如果簇的势小于阈值e，则删除该簇，并减少相应簇的数目；……