一种基于人工免疫网络的模糊c均值聚类算法

◆董 雪



一种基于人工免疫网络的模糊c均值聚类算法

◆董 雪

（四川大学计算机学院 四川 610065）

传统模糊c均值聚类算法（FCM）需要对整个数据集进行复杂地迭代计算，当数据量增大时，算法变得耗时。为减少参与FCM迭代计算的数据量，提出一种基于人工免疫网络的模糊c均值聚类算法。首先利用人工免疫网络对原始数据集进行预处理，产生考虑了原始数据密度信息的代表性样本，然后用样本数据代替原始数据参与FCM的迭代计算，最后将聚类信息扩展到原始数据集并调整聚类中心。实验结果显示，相较于传统FCM算法，新算法在保持相近聚类准确度的情况下，有效地降低了聚类时间。

模糊c均值聚类算法; 模糊聚类; 人工免疫网络

0 引言

模糊c均值算法（FCM）是一类代表性的模糊聚类算法，它能够定量地描述每个数据点对各个聚类中心的隶属度，相较于硬聚类算法，更好地贴合人类的思维模式。FCM算法通过最小化一个目标函数来得到聚类结果，巧妙地将模糊聚类问题转化为最优化问题，目前FCM算法及其改进算法已被广泛应用于图像分割、模式识别、网络安全等领域[1-3]。

然而，传统的FCM算法使用整个数据集参与复杂的迭代运算，当处理大量数据的聚类问题时，变得相对耗时。如果我们能够找到少量的代表性样本数据，代替原始数据参与迭代计算获得近似的聚类结果，将会大幅降低聚类时间。这个问题可以通过一个数据压缩过程来实现。

人工免疫网络算法因其在数据压缩、优化等领域的卓越表现已得到广泛关注[4-5]。它受生物免疫系统中选择和记忆机制的启发，由Jerne率先提出的免疫网络理论[6]发展而来，随后一系列人工免疫网络模型被相继提出[7-8]。目前，由De Castro提出的aiNet免疫网络模型[7]被研究和应用得相对较广，它能通过模拟生物体内抗体学习抗原的过程，对原始数据集进行学习，生成一个精简的代表性样本数据集。在aiNet模型的基础上，Bezzera等人提出了适应性半径免疫网络算法（ARIA）[9]。该算法考虑了抗原数据中呈现的密度信息，与aiNet算法相比，ARIA学习到的抗体数据集能够更好地代表抗原数据集的分布特点。

基于此，本文提出一种基于人工免疫网络的模糊c均值聚类算法ARAIN-FCM，减少参与FCM迭代计算的数据量。经实验验证，在数据量足够的情况下，该算法能够在保持传统FCM算法聚类准确度的情况下，有效地提高FCM算法的聚类时间效率。

1 模糊c均值算法

模糊c均值聚类算法（FCM）[10]定义了一个目标函数，如公式（1）。通过最小化目标函数，获得聚类结果。

2 ARAIN-FCM算法

本文提出的基于人工免疫网络的模糊c均值聚类算法ARAIN-FCM基本思想如下：首先，利用基于人工免疫网络的数据压缩算法得到数量较少的样本数据，这些样本数据能够很好地代表原始数据在特征空间中的分布情况。然后一个来自标准FCM算法的聚类过程被应用到这些代表性样本数据上，获得一组初始聚类中心。接着，通过评估每个原始数据点对于这些初始数据中心的隶属度，将聚类划分信息扩展到整个数据集，建立隶属度矩阵。最后，通过获得的隶属度矩阵再次更新聚类中心，如图1。

图1 ARAIN-FCM算法示例

从原始数据集获取代表性样本集的预处理过程，可以减少后期参与聚类迭代计算的数据量，从而显著地减少了聚类的时间开销。与此同时，在学习代表性样本集的过程中，原始数据中呈现的结构特征和密度信息都被较好地保留，使获得的样本数据能够较好地代表原始数据。所以，通过对样本数据集进行聚类所获得的初始聚类中心，在一定程度上反映了真实情况，再加上最后一阶段的调整，最终得到较准确的聚类信息。

算法包含如下四个阶段，如图2：

图2 ARAIN-FCM算法四个阶段

表1 Aria(AIN)

2.1获得代表性样本集

这一预处理过程可以借助适应性半径免疫算法（ARIA）[9]来实现。原始数据被视为抗原，样本数据作为抗体，三个基本步骤重复执行：首先，抗体识别抗原，计算各个抗体与抗原之间的亲和力，具有较高亲和力的抗体被保留。然后，被保留的抗体经过增殖和变异产生新的后代。最后，抗体之间进行相互抑制作用，删除冗余抗体。其中，亲和力的高低与抗体抗原之间的距离成反比，亲和力越高表示两者越相似。每一个抗体具有位置和压缩半径两个属性，抗体的压缩半径根据抗体周围抗原的密度适应性地调整，密度越大，半径越小。在抑制阶段，如果两个抗体之间的距离小于其中一个抗体的压缩半径，则具有较大半径的抗体将被清除。基于此，抗原密度越高的地方，抗体将被较多的保留。表1展示了这个过程。

抗体与抗原间的距离越小，其亲和力（相似度）越大，如公式（3）。这里用欧式距公式作为距离评估标准。

抗体的克隆变异同时完成，如公式（4）：

抗体重复地进行增殖、变异和相互抑制的过程。最后，对抗原具有较高亲和力（相似度）的记忆抗体被保留下来，保留下来的记忆抗体（代表性样本集）能够较好地代表原始数据集在特征空间中的分布。

2.2生成初始聚类中心

保留下来的少量代表性样本数据将代替原始数据参与FCM算法中的迭代运算，以获得初始的聚类中心，如表2所示。

表2 Sample-Cluster(FCM)

为了获得聚类中心，需要最小化公式（1）中的目标函数。

这通过迭代地更新聚类中心和模糊隶属度矩阵来完成，如公式（5）（6）。当目标函数值的变化小于一个给定阈值的时候，循环终止。

2.3建立原始数据集的隶属度矩阵

本阶段的目标在于将基于样本数据所得到的聚类信息扩展到原始数据集。通过评估每一个原始数据与由样本数据所产生的初始聚类中心的相似度，建立隶属度矩阵。算法如表3。

表3 Membership

2.4更新聚类中心

我们利用2.3中得到的隶属度矩阵，依照公式（5）更新初始的聚类中心，得到最终的结果。这最后的一步用于获得更加精准的聚类信息。

3 实验结果与分析

运行时间(Run-time)和调整兰德系数(Adjusted rand index)[11]被作为评估算法性能的指标参数。运行时间指两种算法分别用于聚类时迭代计算所消耗的实际时间。ARAIN-FCM算法后期将数据划分信息扩展到原始数据集并调整聚类中心，这部分时间没有纳入运行时间的计算，因为与迭代计算相比，该部分的时间开销很少，可忽略不计。调整兰德系数（ARI）通过计算聚类结果与真实类别情况的相似度评估聚类质量。ARI值越高表示算法的聚类准确度越高。计算ARI时，我们将数据点硬性地归为其具有最大隶属度值的聚类。

五组不同数据量大小的合成数据集被用来测试，分别包含100,500,1000,1500,2000个数据，每组数据按五个高斯分布，高斯分布如下：

ARAIN-FCM算法和标准FCM算法被用来对这些数据聚类，图3、图4展示了两种算法分别对不同大小数据集聚类的运行时间和聚类准确度。

由图3可见，标准FCM算法和ARAIN-FCM算法（不同抽样比例）的聚类时间都随数据量大小的增加而增加。当数据量仅仅只有100时，两种算法时间开销的差异并不明显，这是因为此时FCM算法的聚类时间已经很小（<0.005），很难再被压缩。除此以外，在数据量大小从500变化到2000时，ARAIN-FCM算法与FCM算法相比，明显花费更少的聚类时间，当抽样比例为50%、20%和10%时，聚类时间分别降低为标准FCM算法的52.3%、25%和14.7%。

图4 Adjusted Rand Index vs data size

由图4可见，当数据量只有100时，ARAIN-FCM算法较小程度地损失了部分聚类准确度，这是因为当数据量太少时，数据冗余程度低，在数据压缩过程中被压缩的数据将带走更多的有用信息。当数据量达到500及以上时，ARAIN-FCM算法保持了较高的聚类准确度（>0.92）。而且，此时无论ARAIN-FCM算法所抽样的比例如何，其聚类准确度都与标准FCM算法保持相当水平。

4 结束语

本文提出了一种基于人工免疫网络的模糊c均值聚类算法ARAIN-FCM，利用人工免疫网络算法从原始数据集中学习得到更加精简的样本数据集来参与聚类，以减少传统FCM算法中参与复杂迭代计算的数据量，从而提高其聚类时间效率。实验结果显示，相较于传统FCM聚类算法，本文提出的算法有效降低了聚类时间，并能够保持与其相近的聚类准确度。

[1]周文刚, 孙挺, 朱海.一种基于自适应空间信息改进FCM的图像分割算法[J].计算机应用研究，2015.

[2]Polat K. Intelligent recognition of diabetes disease via FCM based attribute weighting[J]. World Acad Sci Eng Technol Int J Comput Electr Autom Control Inform Eng，2016.

[3]刘绪崇, 陆绍飞, 赵薇等.基于改进模糊 C 均值聚类算法的云计算入侵检测方法[J].中南大学学报:自然科学版，2016.

[4]Stibor T, Timmis J. An investigation on the compression quality of aiNet[C]. Foundations of Computational Intelligence, 2007. FOCI 2007. IEEE Symposium on. IEEE，2007.

[5]Dasgupta D, Yu S, Nino F. Recent advances in artificial immune systems: models and applications[J]. Applied Soft Computing，2011.

[6]Jerne N K. Towards a network theory of the immune system[C]//Annales d'immunologie，1974.

[7]de Castro L N, Von Zuben F J. aiNet: an artificial immune network for data analysis[J]. Data mining: a heuristic approach，2001.

[8]Timmis J, Neal M. A resource limited artificial immune system for data analysis[J]. Knowledge-Based Systems，2001.

[9]Bezerra G B, Barra T V, de Castro L N, et al. Adaptive radius immune algorithm for data clustering[M]//Artificial Immune Systems. Springer Berlin Heidelberg，2005.

[10]Bezdek J C, Ehrlich R, Full W. FCM: The fuzzy c-means clustering algorithm[J]. Computers & Geosciences，1984.

[11]Hubert and P.Arabie, “Comparing partitions,” J. Class，1985.

国家重点研发计划（2016yfb0800604,2016yfb0800605），国家自然科学基金项目（61572334）。