2018, Vol. 35
谱聚类，是机器学习中重要的无监督学习方法[1]，能够较好地聚类非块状、非凸球形分布特性的数据，并收敛于全局最优[2-3]，在模式识别、图像分割、数据挖掘等领域有着广泛的应用[4-6]. 核模糊谱聚类算法是以模糊核代替高斯核的新型谱聚类算法[7].
核模糊谱聚类算法以模糊数学中隶属矩阵的列向量之间的夹角来度量数据之间的相似性[8]，可以让算法更好地适配真实数据的软划分属性，所以核模糊谱聚类相比传统谱聚类有着更好的聚类性能[9]. 但算法对初始聚类中心选择较为敏感，易受噪声点和异常点干扰，从而造成算法的波动. 因此，核模糊谱聚类算法需要进一步提高稳定性.
本文从分析异常点对现有聚类算法造成的干扰开始，引入局部异常因子(Local Outlier Factor，LOF)算法[10]，提出基于数据局部分布特性的改进的核模糊谱聚类算法——基于LOF降噪的核模糊谱聚类算法(Kernel Fuzzy Spectral Clustering based on Local Outlier Factor，LOF-KFSC). 算法有效性实验证明了修正的相似性度量的有效性，算法稳定性实验则验证了本文算法对于处理复杂数据集的稳定性和鲁棒性.
1 相关工作谱聚类建立在谱图划分理论基础上，把聚类问题转化为图的最优划分问题，聚类的过程就是使得划分的子图之间相似性最小，子图内部相似性最大的过程. Ng等[2]提出的利用连续松弛形式，把NP难的图划分问题转化为求解Laplacian矩阵谱分解问题的NJW(Ng Jordan Weiss)算法代表了经典的谱聚类算法. 但由于经典谱聚类算法对尺度参数很敏感，为了得到较优的聚类结果，使用者往往需要耗费大量的时间调参才能找到合适的参数区间.
Zhao等[8]通过研究模糊C均值(Fuzzy C-means，FCM)发现，计算隶属矩阵列向量之间内积的大小可以量化相应样本点之间的相似性，从而提出核模糊相似性度量. 但由于该相似性度量极值会随着数据对象的绝对大小而变动，故在算法应用于实际时不好比较聚类的性能. Yang[7]在Zhao等的基础上，设计了一个新的函数使得相似性介于[0，1]之间，并引入t最近邻方法[11]以减轻稠密相似性矩阵的存储问题，得到核模糊谱聚类算法(Kernel Fuzzy Spectral Clustering，KFSC). Li[9]和Goyal[12]的研究中均表明，基于模糊相似性度量的谱聚类算法在对复杂数据集进行聚类时，相比传统谱聚类有较好的聚类准确率. 但核模糊谱聚类算法隐性假设了输入数据集为无噪声数据集，对于野点和噪声数据对初始聚类中心和最终聚类结果造成的影响没有予以充分考虑，造成算法在处理复杂数据的时候性能下降和波动.
在异常检测领域，Breunig提出的局部异常因子算法(LOF)[10]解决的是密度分布相差很大的簇的异常点识别问题. Akoglu等[13]研究发现，LOF算法可以很好地分离开数据簇中密度差异比较大的数据对象. Celebi[14]在研究k-means聚类算法时指出，对于需要选取初始聚类中心的聚类算法，随机性造成了算法性能波动较大，并提出一种改进建议：如果能够优化初始聚类中心点的选取，将对算法的稳定性有较大提升.
因此，本文从优化核模糊谱聚类稳定性的方向出发，采用Breunig等的研究成果，以局部异常因子为基础，定义了聚类中心候选对象的概念，过滤数据集，使得初始聚类中心的选取范围限定在正常数据点的范围之内；同时构建局部过滤因子，以该因子作为权值因子，放大正常对象之间的权值，缩小正常对象和异常对象之间的权值，修正核模糊谱聚类相似性度量得到本文算法——LOF-KFSC. 有效性实验和稳定性实验表明本文提出的方法相比改进前的KFSC算法更为稳定和鲁棒.
2 基于LOF过滤的核模糊谱聚类(LOF-KFSC)算法本文在核模糊谱聚类(KFSC)基础上，引入局部异常因子(LOF)算法，得到改进的KFSC算法——LOF-KFSC算法.
对象p的局部异常因子[10]，如式(1)所示
| ${L_k}\left( p \right) = \frac{{\displaystyle\mathop \sum \nolimits_{o \in {N_k}\left( p \right)} {\rho _k}\left( o \right)}}{{\left| {{N_k}\left( p \right)} \right|{\rho _k}\left( p \right)}}.$ | (1) |
其中，ρk(p)表示对象p的局部可达密度，Nk(p)表示对象p的k-距离邻域，k表示对象p的k-距离参数. Lk(p)量化了一个对象的离群尺度：如果这个比值接近1，说明p的密度和其邻域点密度差不多，p很可能和邻域同属一簇；如果这个比值小于1，说明p的密度高于其邻域点密度，p处于一个相对密集的区域，并与其领域点同属一簇；如果这个比值远大于1，说明p的密度远小于其邻域点密度，p越可能是异常点.
2.1 改进的初始聚类中心点选择算法设有密度分布相差很大的两类C1和C2，如图1所示.
|
图 1 密度分布相差很大的两类C1和C2 Figure 1 Two datasets C1 and C2 who have big disparity density distribution |
C1为密度较小的簇，C2为密度较大的簇，两簇的密度差异很大. 而o1、o2两点是异常点. 用现有谱聚类算法聚类图示类型数据集，会发现o1、o2点会被错误归类为正常点，参与后续的初始聚类中心发现和相似性度量构建的重要步骤中，使得算法对异常点很敏感，并影响聚类准确率.
本文优化的思路是：找到一种局部判断方法，使得对于密度差别很大的两簇，可以发现相对于本簇应被视为“异常”的点，并过滤掉这些点，从而使得后续的重要步骤免受异常点影响. 本文从LOF算法中找到实现这种思路的一种方法.
给定数据集X={x1，x2，∙∙∙，xN}，由式(1)计算X中每个对象的局部异常因子，则把局部异常因子值小于X中平均局部异常因子值的对象称之为聚类中心候选对象. X的平均局部异常因子值由下式给出
| ${E_k}\left( {X} \right) = \frac{{\displaystyle\mathop \sum \nolimits_i^N {L_k}\left( i \right)}}{N}.$ | (2) |
由于异常点数目比较少，聚类中心候选对象大幅度排除了异常点. 基于聚类中心候选对象概念，本文提出改进的初始聚类中心选择算法，算法流程如下：
输入：待聚类数据集X={x1，x2，∙∙∙，xN}，聚类数目C，k-距离参数K.
输出：初始聚类中心点集V={v1，v2，∙∙∙，vC}.
Step 1：初始化V为空集；
Step 2：利用式(1)和式(2)找出X中的聚类中心候选对象，加入聚类中心候选对象集合M中；
Step 3：以M作为初始聚类中心候选集，用随机算法，从M中找出初始聚类中心点集V={v1，v2，∙∙∙，vC}.
2.2 改进的相似性度量文献[10]同时指出，Lk(p)衡量的是一个对象的离群尺度. 关于对象p的局部异常因子值Lk(p)，有如下3点性质：(1) 正常点的L值均比异常点的L值要小，并且离群程度越大，L值也越大；(2) L值大小是基于局部的，不随簇的绝对密度而改变；(3) L值约等于1，说明p的密度和其邻域点密度一样，p跟其邻域点属于同一簇.
回到KFSC算法的相似性度量的构建方法：隶属矩阵U的列向量μi跟μj的分布越相似，即μi与μj对应位置的元素大小越接近，则第i样本点和第j样本点的相似性就越大. 这个构建方法对于第i样本点和第j样本点均为正常数据点来说是完全可行的，但是当第i样本点、第j样本点其一或两者均为异常点的时候，就给相似性度量引入了不稳定因素，造成最终的聚类结果准确率下降和算法稳定性的降低.
基于此，本文定义一个局部过滤因子ωij，以之作为第i样本点与第j样本点相似性的权值，修正相似性度量，即
| ${\omega _{ij}} = \frac{2}{{{L_k}\left( i \right) + {L_k}\left( j \right)}}.$ | (3) |
分3种情况讨论：
(1) i与j均为正常点：Lk(i)和Lk(j)之和约为2，ωij约为1，i与j的相似性几乎没有调整；
(2) i、j其一为异常点：Lk(i)和Lk(j)之和大于2，ωij小于1，i与j的相似性作小调整；
(3) i与j均为异常点：Lk(i)和Lk(j)之和远大于2，ωij远小于1，i与j的相似性作大调整.
以ωij作为权值因子，修正KFSC的相似性度量，得到LOF-KFSC的相似性度量，即
| ${{{S}}_{ij}} ={\rm{exp}}\left[{{\rm{ln}}2\cdot \omega_{ij}({{{\mu}} _i} \cdot {{{\mu}} _j})}\right] - 1.$ | (4) |
由于Lk(p)是基于对象p的局部密度计算而不是全局密度计算的，所以修正的相似性度量很好地适应了复杂数据集的局部一致性特点，同时ωij能根据对象是否是异常点动态调整对象间相似性，故S可以降低对异常点和噪声点的敏感度，使得修正的聚类算法更为稳定和鲁棒.
2.3 LOF-KFSC算法根据对KFSC算法初始聚类中心选取和相似性度量的改进，得到基于LOF过滤的核模糊谱聚类算法(LOF-KFSC).
算法具体流程如下：
输入：待聚类数据集X={x1，x2，∙∙∙，xN}，聚类数目Q，k-距离参数K，t最近邻参数t.
输出：数据聚类划分.
Step 1：根据改进的初始聚类中心选择算法，计算初始聚类中心点集；
Step 2：根据式(4)计算相似性，并采用t最近邻方法构造稀疏相似性矩阵；
Step 3：构建规范化Laplacian矩阵
| ${{L}} = {{{D}}^{ - \frac{1}{2}}}{{S}}{{{D}}^{ - \frac{1}{2}}},$ | (5) |
其中，度矩阵
Step 4：计算Laplacian矩阵的前Q个最大特征值所对应的特征向量z1，∙∙∙，zQ，构造矩阵Z=[z1，∙∙∙，zQ]∈RN×Q；
Step 5：归一化矩阵Z的行向量，得到矩阵Y，即
| ${{{Y}}_{ij}} = \frac{{{{{Z}}_{ij}}}}{{\sqrt {\displaystyle\mathop \sum \nolimits_j {{Z}}_{ij}^2} }};$ | (6) |
Step 6：对矩阵Y的每一行看作是Rk空间中的一个点，对其使用标准k均值算法进行聚类，并将数据点xi划分到聚类j中，当且仅当Y的第i行被划分到聚类j中.
3 实验及分析本文首先用人工数据集进行算法有效性实验，以验证本文算法的正确性；然后用UCI数据集进行算法稳定性验证，以验证本文算法的实际应用能力. 实验环境如表1所示.
|
表 1 实验环境 Table 1 Experimental environment |
为了验证本文提出的算法的有效性，需要验证修正的相似性度量的有效性.
Melia[15]指出，相似性度量的块对角分布效应可以证明相似性度量的有效性. 规范化的Laplacian矩阵对数据进行聚类时，呈现出的块状分布结构越清晰明显，相似性度量就越有效;当矩阵为理想的块对角矩阵的时候，谱聚类算法能找到完全正确的聚类.
图2为计算机随机产生的密度分布相差较大的3个簇在受到噪声干扰时的原始数据分布情况. 由于数据集混入了噪声，在用传统核模糊谱聚类(KFSC)去聚类数据只会把噪声数据也划分到某一簇中，导致聚类准确率和算法稳定性下降. 而本文提出的基于LOF过滤的核模糊谱聚类算法却能很好地处理这种数据集.
|
图 2 密度差异比较大的3个簇 Figure 2 Three datasets who have big disparity density distribution |
对样本数据按照类属重新排序后(这一顺序对算法是未知的)，用改进前的KFSC相似性度量和基于LOF过滤的相似性度量计算出的相似性矩阵分别如图3(a)、(b)所示.
|
图 3 相似性矩阵 Figure 3 Affinity matrix |
可知，基于LOF过滤的相似性矩阵更接近于理想的块对角矩阵，这得益于本文提出的LOF-KFSC算法能够自动修正相似性度量受到的噪声扰动. 因此本文提出的基于局部过滤因子改进的相似性度量有效性得到了验证，LOF-KFSC具有更强的抗干扰能力.
3.2 算法稳定性实验为了验证算法稳定性，本文选用国际通用的具有真实数据含义的UCI基准数据集，测试本文算法的聚类准确性和鲁棒性.
实验选用UCI数据集中的New-thyroid、Acd、Ionesphere数据集对NJW、KFSC、LOF-KFSC算法做对比实验. 测试数据集的基本信息如表2所示.
|
|
表 2 测试数据集基本信息 Table 2 Basic information of data set |
为了比较不同算法的性能，本文采用Wu[16]提出的评价标准作为聚类算法性能的准确率，即
| $A = \frac{{\displaystyle\mathop \sum \nolimits_{i = 1}^n \delta \left( {{y_i},{\rm{map}}\left( {{c_i}} \right)} \right)}}{n}.$ | (7) |
其中，n是样本点的个数，yi和ci分别表示第i个样本点的真实标签和聚类算法类别索引，如果y=c，则δ(y，c)=1，否则δ(y，c)=0. map(∙)表示聚类算法类别索引到类别标签的映射. A越高，表示聚类算法的性能越好.
参数设置方面，对于NJW算法，参数σ以0.01步长在区间[0.05，1.0]之间变化；对于KFSC和LOF-KFSC算法，为不失一般性，最近邻参数t以相同方式设置，即以步长2在区间[1，50]之间变化. 其中LOF-KFSC算法中的k-距离参数K设置为5. 3种算法按照各自参数设置在区间内运行10次，每次运行取出最大聚类准确率，然后取平均值得到平均最大聚类准确率，如表3所示.
|
|
表 3 平均最大聚类准确率 Table 3 Average maximum accuracy rate |
由表可知，本文提出的LOF-KFSC算法在3个数据集上均比NJW、KFSC算法有更高的聚类准确率，证明了本文提出算法的聚类准确性. 注意到同一个算法在3个数据集上的聚类准确率有些差距. 分析表3可知，New-thyroid数据集维数和样本数均较小，故3个算法对其聚类均得到比较好的准确率；由表2可知，Acd和Ionesphere这两个数据集均比New-thyroid数据集有更高的样本数和维数. 这从侧面反映出谱聚类算法随着维数和样本数上升有聚类性能下降的共同问题.
对每一个步长位置，取10次运行的平均值，作聚类准确率曲线，图4~6分别给出了NJW、KFSC、LOF-KFSC算法在3个数据集上聚类准确率曲线图的对比.
|
图 4 3种算法在New-thyroid数据集上的聚类准确率曲线比较 Figure 4 Clustering quality comparison for NJW, KFSC and LOF-KFSC on the New-thyroid dataset |
|
图 5 3种算法在Acd数据集上的聚类准确率曲线比较 Figure 5 Clustering quality comparison for NJW, KFSC and LOF-KFSC on the Acd dataset |
图4~6表明，NJW算法在3个数据集上波动都很大，只有很小的参数区间能取得较优聚类，表明NJW算法对分析尺度的选择非常敏感. 而KFSC算法和LOF-KFSC算法在样本数不多、维数不高的New-thyroid数据集上能有相近的稳定性，在很大的参数区间内都能取得较优聚类. 而当KFSC算法对样本数较多的Acd数据集和维数较高的Ionephere数据集进行聚类时，产生了不小的波动，在Ionephere数据集上甚至大大收窄了较优聚类的参数区间. 而本文提出的LOF-KFSC算法无论是对样本数较多的Acd数据集，还是对维数较高的Ionephere数据集进行聚类时，均保持很平稳的聚类准确率. 这得益于本文算法对初始聚类中心和相似性度量两方面的优化：改进的初始聚类中心算法使得算法一开始就排除掉大部分异常点作为初始聚类中心；而改进的基于局部过滤因子修正的相似性度量，定量刻画了数据对象的离群尺度，使得算法就算面对复杂多样的数据的时候也能有效抑制异常点的干扰，大幅度提高了算法的鲁棒性. 本实验充分证明了本文算法的聚类准确性和鲁棒性.
|
图 6 3种算法在Ionephere数据集上的聚类准确率曲线比较 Figure 6 Clustering quality comparison for NJW, KFSC and LOF-KFSC on the Ionephere dataset |
本文为解决核模糊相似性度量谱聚类算法的样本点降噪问题，通过引入局部异常因子，提出聚类中心候选对象概念，过滤数据集异常点，让初始聚类中心的选择限制在正常数据范围之内；同时定义局部过滤因子，以此作为权值因子修正核模糊谱聚类算法的相似性度量，放大正常点之间的相似性，缩小正常点与异常点之间的相似性. 实验表明，改进的核模糊谱聚类算法有效并稳定. 未来将进行把本文方法应用于快速谱聚类方面的研究.
| [1] |
SHAH M, NAIR S. A survey of data mining clustering algorithms[J].
International Journal of Computer Applications, 2015, 128(1): 1-5.
DOI: 10.5120/ijca2015906404. |
| [2] |
NG A Y, JORDAN M I, WEISS Y. On spectral clustering: Analysis and an algorithm[C]//14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Vancouver: MIT Press, 2002: 849-856.
|
| [3] |
VONLUXBURG U. A tutorial on spectral clustering[J].
Statistics and Computing, 2007, 17(4): 395-416.
DOI: 10.1007/s11222-007-9033-z. |
| [4] |
滕少华, 吴昊, 李日贵, 等. 可调多趟聚类挖掘在电信数据分析中的应用[J].
广东工业大学学报, 2014, 31(3): 1-7.
TENG S H, WU H, LI R G, et al. The application of the adjustable multi-times clustering algorithm in telecom data[J]. Journal of Guangdong University of Technology, 2014, 31(3): 1-7. DOI: 10.3969/j.issn.1007-7162.2014.03.001. |
| [5] |
HAN J, PEI J, KAMBER M. Data mining: concepts and techniques[M].[S.l.]: Elsevier, 2011.
|
| [6] |
张巍, 黄健华, 刘冬宁, 等. 一种改进的结合评分和评论信息的推荐方法[J].
广东工业大学学报, 2017, 34(6): 27-31.
ZHANG W, HUANG J H, LIU D N, et al. An improved recommendation method using rating and review information[J]. Journal of Guangdong University of Technology, 2017, 34(6): 27-31. DOI: 10.12052/gdutxb.170014. |
| [7] |
YANG Y, WANG Y, CHEUNG Y. Kernel fuzzy similarity measure-based spectral clustering for image segmentation[C]//International Conference on Human-Computer Interaction. Berlin, Heidelberg: Springer, 2013: 246-253.
|
| [8] |
ZHAO F, LIU H, JIAO L. Spectral clustering with fuzzy similarity measure[J].
Digital Signal Processing, 2011, 21(6): 701-709.
DOI: 10.1016/j.dsp.2011.07.002. |
| [9] |
LI Q, REN Y, LI L, et al. Fuzzy based affinity learning for spectral clustering[J].
Pattern Recognition, 2016, 60: 531-542.
DOI: 10.1016/j.patcog.2016.06.011. |
| [10] |
BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF: identifying density-based local outliers[C]// ACM SIGMOD International Conference on Management of Data. Dallas: ACM, 2000, 29(2): 93-104.
|
| [11] |
CHEN W Y, SONG Y, BAI H, et al. Parallel spectral clustering in distributed systems[J].
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3): 568-586.
DOI: 10.1109/TPAMI.2010.88. |
| [12] |
GOYAL S, KUMAR S, ZAVERI M A, et al. Fuzzy similarity measure based spectral clustering framework for noisy image segmentation[J].
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2017, 25(4): 649-673.
DOI: 10.1142/S0218488517500283. |
| [13] |
AKOGLU L, TONG H, KOUTRA D. Graph based anomaly detection and description: a survey[J].
Data Mining and Knowledge Discovery, 2015, 29(3): 626-688.
DOI: 10.1007/s10618-014-0365-y. |
| [14] |
CELEBI M E, KINGRAVI H A, VELA P A. A comparative study of efficient initialization methods for the k-means clustering algorithm[J].
Expert Systems with Applications, 2013, 40(1): 200-210.
DOI: 10.1016/j.eswa.2012.07.021. |
| [15] |
MEILA M, SHI J. Learning segmentation by random walks[C]//Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2001: 873-879.
|
| [16] |
WU M, SCHOLKOPF B. A local learning approach for clustering[C]//Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2007: 1529-1536.
|