自动三支决策聚类研究及拓展

姚家旸 刘畅 李健行

在本文中，定义了两个新的聚类有效性指数，通过组合类内紧凑性和考虑近邻的类间分离来确定聚类的数量。本文的紧凑性度量不仅考虑了对象与类中心之间的距离，还考虑了类中对象的数量和类中对象的分布，可以更好地测量类中对象的紧凑性。分离度量考虑了对象和近邻的分布以及类中对象的数量，它们可以测量类之间的分离。本文还分析了类中对象的形成，并研究了传统聚类算法中对象的局限性，这种算法只能属于唯一类。通过三个决策思想，进一步区分三支决策思想对类中的对象，得到丰富而有针对性的信息。因此，本文提出了一种自动三分支决策聚类方法。

1 引言

传统的聚类算法是二支决策聚类的结果，即对象属于某一类或不属于某一类，不能很好地处理具有不确定场景的聚类任务，如社交网络、生物信息处理和投资管理。这三个决策是近年来提出的一种基于人类认知的决策模型。主要思想是将整体划分为三个部分，并对未使用的部分采用不同的策略和方法。这三种决策思路为不确定性聚类提供了新的思路和策略。为此，我们在聚类分析中引入了三种决策思想，并提出了三种决策聚类方法来处理具有不确定情景的聚类任务。实际上，二支决策聚类是三分支聚类的特例。三个决策集群中的对象和类之间的关系不再属于该类，或者不属于该类，但是确定一个对象是否属于一个类。

2 自动三支决策聚类算法描述

对象和类之间的关系

考察对象x和类C，，Xj∈Neigq（X）。其中对象x和类C，存在如下关系：

（1）如果，Xj∈C那么X∈CM;

（2）如果，那么X∈CR。

在聚类分析中，我们可以从两个方面考虑一个类的组成：一方面，考虑类和类之间的关系，如果类中的对象只与一个类紧密相关，则对象是确定属于这个类，属于L类域：如果一个对象和多个类之间的关系在一定程度上紧密，那么这个对象可能同时属于这些类，是类中的一个非典型对象，并且应该同时属于类中的M域。另一方面，考虑到类中对象之间的关系，类中的大多数对象密切相关，形成类的核心部分，属于类的L域，少部分对象和类中大部分对象之间的联系相对较弱，是类的关键部分，属于该类的M域。

综合以上考虑，受我们在文献中提出的差值排序法的启发，文中采用类中对象到类中心距离的差值，对类中对象进一步区分。考查对象x和类C，依次计算对象到类中心的距离，并按数值从小到大排列，得到呈升序排列的序列d（X1，V）、d（X2，V）、d（X3，V）、d（Xn-1，V）、…、d（Xn，V）。然后，依次计算这些距离的差值d（X1，V）- d（X2，V）、d（X2，V）- d（X3，V）、、d（Xn-1，V）- d（Xn，V），能够找到第一个距离差值最大的对象对，Xi-1和Xi，并把对象X1，X2…Xi-1划分到类C的L域，把x和以后的对象划分到类C的M域中。

3 近邻q的确定

选择合适的近邻q值很关键。通过上文的分析可知，Ci和Cm还可以细分为和个部分。考察Ci中每个对象的个近邻和Cm的关系，得到Ci和Cm之间联系的紧密程度;考察Cm中每个对象的个近邻和Ci的关系，得到Ci和Cm之間联系的紧密程度。另外，考虑类Ci和Cm中对象数目之间的关系，防止类中数目多的对象的过度影响，类中数目少的类，近邻q的值取两者之间的最小值，即：

Q=min

为了防止得到不符合事实的聚类结果，近邻q的值取和中的最小值。需要指出，文中三支决策聚类算法，不采用统一的q值，而是由每两个类中数目的多少，来确定类之间q值的选取，这样得到的结果比采取全局统一的q值更合理。

3.1时间复杂度分析

因此，分离性指数计算的时间复杂度近似为O（kNlogN+k2q2）。所以，一次有效性指数CVIDN的计算复杂度近似为O（kNlongN+k2q2）。

为了寻找最佳的聚类数目，聚类数目K从2递增至，计算的复杂度O（2NT+，…，+kNT， …，+ NT），即O（N2T）。每一次聚类数目K都会计算CVIDN的值，计算复杂度近似为

O（（2NlogN+22q2）+（3NlogN+32q2）），

…，+（ NlogN+Nq2）。即O（N2llogN+q2N）。综上所述，寻找最佳聚类数目时间的复杂度为

O（N2logN+N2T+q2N））

3.2算法描述：

输入：数据集U、近邻数q。

输出：

Step1：初始化为k=2。

Step2：随机选取k个聚类中心V1，V2，…VK。

Step3：对于类中每个对象Xi，计算到每个聚类中心VK的距离，划分到距离最小的类。

Step4：不断更新聚类中心V=。

Step5：如果聚类中心不发生变化，转自Step6;否则转至Step3。

Step6：计算CVI（CS），如果，那么K=K+1， 转至Step2; 否则转至Step7。

Step7：kopt=argminCVI（CS）。

Step8：考察对象x和类C、、.那么， 那么。

Step9：对于类中剩余非M域中的对象，根据排序法，找到第一个距离差值最大的对象，Xi-1和Xi，把Xi及其后的对象划分到CM。

Step10：算法结束，会输出结果：

。

3.3算法时间复杂度的分析

本小节主要分析聚类数目的时间，以及把二支决策聚类转换为三支决策聚类的时间。

4 实验结果分析

4.1类间近邻q的确定

三支决策聚类算法在考虑不同类中对象的关系时，需要确定近邻q的值，不同的q值会得到不同的聚类结果。文中给出了一种自动确定近邻q的方法，结果如图：

5.结论

实验结果表明，三支决策聚类算法不仅可以找到类之间的重叠部分，而且可以进一步细分类中的对象，获得更丰富的信息。本文提出的三支决策聚类算法与比较算法相比，与传统的二支决策聚类算法相比，能够有效提高聚类精度。

指导老师：白斌

（作者单位：华北理工大学）