一种基于密度峰值的针对模糊混合数据的聚类算法*

陈奕延 ，李 晔,李存金

(1.北京理工大学管理与经济学院，北京 100081;2.中国管理科学研究院学术委员会,北京 100036; 3.中国社会科学院大学(研究生院)，北京 102488)

1 引言

聚类分析是按照某个特定标准把数据对象划分成子集的过程，每个子集表示一个簇。聚类分析是一种无监督学习过程，其目的是使得簇中的对象彼此相似，但与其它簇对象不相似[1,2]。目前，聚类分析广泛应用于商务智能、生物安全、Web检索、评价与决策等领域。按照陈彩棠[3]的观点，聚类分析算法可以分为6类，包括基于划分[4 - 6]、层次[7 - 9]、密度[10]、网格[11,12]、概率模型[13]以及基于约束[14]的聚类算法。这种划分方式并不一定涵盖所有的聚类算法，譬如基于图论[15]的聚类算法，但不论何种算法皆有其各自的特点。

2 相关工作

Rodriguez等[16]于2014年提出了快速搜索和发现密度峰值的聚类CFSFDP(Clustering by Fast Search and Find of Density Peaks)算法，这是一种基于密度、可自动获得簇的正确个数，并能够解决数据空间分布呈非球形簇的聚类算法。许多学者在CFSFDP算法的基础上进行了改进：Wan等[17]对CFSFDP算法中寻找簇中心的决策图方法提出了质疑，提出了一种Fuzzy CFSFDP算法，并利用基于流形距离和基于标准差的截断距离对其进行优化；Zhang等[18]在无线传感网络中将CFSFDP算法与层次协议相结合，提出了一种考虑剩余能量的改进型CFSFDP-E算法；Qin等[19]把太赫兹时域光谱与CFSFDP算法结合，提出了PCA-CFSFDP算法；李晔等[20]提出了针对混合型数据集的MAO-CFSFDP算法，并使用该算法解决了实际问题[21]，从而验证了该算法的可靠性。

虽然MAO-CFSFDP算法拓展了数据类型，但它与CFSFDP算法及其它改进算法都是建立在经典集合上的聚类算法，而现实生活中的许多对象是不具备严格属性的，无法用“非此即彼”的二值逻辑解释，参考Zadeh[22]提出的模糊集理论，这些对象是具有模糊概念的事物。目前常用的PCM[23]、FCM[24]、PFCM[25]等算法依赖统计不确定性理论(概率分布、贝叶斯模型等)，将聚类对象与簇之间的隶属关系不确定化，但仍定义在经典集合上，无法解决模糊数据的距离问题。

因此，本文在模糊集理论的基础上，提出了针对由连续型模糊集与离散型模糊集组成的模糊混合数据的聚类算法FMD-CFSFDP(Fuzzy Mixed Data-Clustering algorithm by Fast Search and Find of Density Peaks)。该算法可满足含有模糊混合数据的样本的聚类需求，继承了CFSFDP算法的优点，并且具备3项创新：

(1)从理论上将CFSFDP算法从经典集扩展到了模糊集上，提出模糊混合数据的概念；

(2)利用连续型模糊集和离散型模糊集，构建了模糊集上针对模糊混合数据的聚类算法；

(3)改进了模糊集上的传统欧氏距离，分别定义了模糊集上针对连续型模糊集和离散型模糊集的改进型欧氏距离，使之相较前者误差减少，令聚类的度量更为合理。

3 模糊混合数据的数学定义

记连续型模糊集为连续型模糊数据，离散型模糊集为离散型模糊数据，假设存在数据集Θ，若Θ中存在N1个连续型模糊数据组成的数据子集Θ1，以及N2个离散型模糊数据组成的数据子集Θ2，满足：Θ1∩Θ2=∅，Θ1∪Θ2=Θ，则称数据集Θ为模糊混合数据集，简称模糊混合数据。模糊混合数据是由数据形式为连续型模糊数据(连续型模糊集)与离散型模糊数据(离散型模糊集)混合组成的数据集。

4 FMD-CFSFDP算法步骤

4.1 计算聚类的度量

(1)

(2)

(3)

(4)

或

(5)

则式(1)的系统误差为：

(6)

(7)

(8)

L(r,t)=LC(r,t)+LD(r,t)

(9)

4.2 其余聚类步骤

Figure 1 Flow chart of FMD-CFSFDP algorithm图1 FMD-CFSFDP算法流程图

FMD-CFSFDP算法是顺序结构，所以其最大时间复杂度是O(N·M2)，而CFSFDP算法的复杂度是O(M2)[27]，显然，由于数据形式和度量都变得复杂，所以FMD-CFSFDP算法的复杂度要高于CFSFDP算法的。

5 随机模拟实验

(10)

其中，K表示该样本集真实的簇的个数,corr_ci表示第i个簇中被正确聚类的模糊样本个数,|D|为模糊样本个数。corr_ci越大，则说明聚类效果越好。计算第1组随机模拟实验的聚类正确率和最优阈值L*,如表1所示。平均聚类正确率MC=63.38%，聚类正确率的标准差SD=6.3628。

Table 1 25 results of the 1st random simulation 表1 第1组随机模拟25次的实验结果

Figure 2 Clustering effect diagram of the 17th experiment in the 1st random simulation图2 第1组第17次实验的聚类效果图

Table 2 25 results of the 2nd random simulation 表2 第2组随机模拟25次实验结果

Figure 3 Clustering effect diagram of the 6th experiment of the 2nd random simulation图3 第2组第6次实验的聚类效果图

显然，从彩图[29]可以看出，代表3个簇的彩色团块中夹杂着不同的颜色，说明第2组的聚类的效果不如第1组第17次实验理想。另外，将表1与表2中的聚类正确率与参考文献[16，20]比较，显然可以发现FMD-CFSFDP算法的聚类正确率没有CFSFDP和MAO-CFSFDP的高。这是因为样本每一个指标下的模糊集中对应的每种状态(元素)都被当成数值参与运算，对于任意连续型模糊集而言则均有无数个元素参与运算，故聚类正确率会较前2者偏低。分别画出第1组随机模拟中第17次实验，以及第2组随机模拟中第6次实验下γ值降序排列后的决策图，如图4所示，由于非簇中心的γ会比较平滑，故可以利用跳跃点判断簇中心个数，γ值的计算和含义沿用CFSFDP算法。

Figure 4 The descending γ decision diagram in two different experiments图4 2次不同实验的降序γ值决策图

由γ的情况以及聚类结果可知，第1组模拟的第17次实验中，人工划分的簇数是2个，根据图4a中所示，其拥有2个跳跃点，故自动识别出的簇数也是2个；而第2组模拟的第6次实验中，人工划分的簇数是3个，但从图4b中可以看出，其自动识别出的簇数为6。显然，FMD-CFSFDP算法利用γ值的跳跃点来自动识别簇数是不稳定的。因为不论连续型模糊集还是离散型模糊集，计算其相应的改进型欧氏距离中使用的隶属度的取值是在[0,1]，因此算出的改进型欧氏距离较小，导致整体距离L、最优阈值L*、密度ρ、特殊距离δ与综合考量值γ也较小，反映在图像中的区分度较低，因此单纯通过视觉识别γ值跳跃点就变得比较困难。

6 结束语

FMD-CFSFDP算法可满足模糊混合数据的聚类需求，在模糊集上继承了CFSFDP算法的大多数优点，本文的主要创新之处在于FMD-CFSFDP算法把CFSFDP算法从经典集扩展到了模糊集上，同时也吸收了MAO-CFSFDP算法的优势，赋予“模糊混合数据”数学涵义，改进了作为度量的传统模糊欧氏距离，使改进后的改进型欧氏距离具有更小的误差，可以提高聚类精度。

然而，纵有上述创新，FMD-CFSFDP算法仍存在以下3个缺点：

(1)FMD-CFSFDP算法中的模糊样本涵盖的信息是模糊集，但模糊样本与簇之间的隶属关系依然使用了硬划分而未能考虑模糊的特性，虽然模糊数学上的许多计算，包括模糊贴近度、模糊度、模糊距离等都是把模糊量转化为经典量，最终计算结果也都是经典数值，这在模糊数学上是合理的。但是，从模糊集到经典集的转化过程中往往会损失一些信息，特别是对于模糊样本的划分，如果采用硬划分则会造成聚类正确率在一定程度上的下降。

(2)虽然使用了误差较传统欧氏距离更小的改进型欧氏距离，并利用权值对其进行了加权处理，从而得到整体距离，但由于其权值是固定的，无法自适应调整，这无疑会削弱整体距离的区分度，从而导致聚类正确率相比CFSFDP算法有所下降。

(3)FMD-CFSFDP算法未能解决CFSFDP算法中利用视觉识别跳跃点寻找簇数的方法的缺陷，这在一定程度上是由于度量的计算使用了隶属度，从而导致最后综合考量值的区分度过低，无法利用视觉有效地寻找跳跃点。

针对上述缺点，未来可对FMD-CFSFDP算法做如下拓展改进：

(1)将模糊样本与簇之间的隶属关系也定义在模糊集上，从而使样本信息和隶属关系均建立在模糊集上，这或许可以减少聚类划分造成的信息损失，提高聚类正确率；

(2)放弃使用隶属度进行计算的模糊距离及其相关一切改进，寻找新的可以体现模糊数据属性的计算公式作为度量；

(3)放弃利用视觉识别几何图像中γ值的特征寻找簇数的方式，可以研究一套量化的数学模型来自动寻找簇的个数，这样即便发生前述缺点(2)和(3)中的情况，微小的差异也可以被数学模型轻易识别出来，从而提高了聚类的区分度。

综上，FMD-CFSFDP算法虽然存在不足之处，但它的提出可为进一步研究模糊集上的聚类算法提供参考。