摘  要： 在数据采集过程中结合网格聚类算法提高计算效率，为了保存采样数据的分布特点引入权值。根据类别中心密度高、权值大的特征采用寻找连通分量的方法初步确定聚类中心，在此基础上结合自适应免疫算法，动态地确定聚类中心及其类别数。进而使FCM算法跳出局部最优，最大可能地得到全局最优解。
关键词： 聚类；权值合理性；自适应免疫算法；连通分量

　FCM算法是当前最受关注的聚类方法之一。本质上，FCM算法是一种初始化数据与聚类结果之间的映射方法，其求解过程采用一种爬山技术进行迭代来寻找局部最优解。当初始化完成后，相应的聚类结果就已经确定了。所以FCM算法对初始化数据比较敏感，有可能陷入局部最优解，无法得到全局最优解。
　针对此问题目前主要的解决方法有两种：（1）在聚类的过程中进行全局随机搜索[1]，Xinchao等人采用模拟退火算法。对当前聚类所获得的结果采用退火计划进行扰动，并以一定的概率接受扰动后的结果为当前最优解，进而跳出局部最优解。此算法要求足够多的扰动次数，配以严密的扰动计划来获取全局最优解，即此算法要求大量的计算。（2）改善FCM算法的初始化条件，选择合适的聚类中心[2]。在初始化问题上，本文受第二种方法启发，把网格划分加权[3]、寻找连通分量、自适应免疫算法[2]相结合。对原始数据进行初始化处理，动态寻找初始类别数和相应的聚类中心。进而跳出局部最优，最大程度地找到全局最优解。本文将原始的FCM算法和改进的FCM算法进行对比分析。实验表明，该改进方法能够有效地降低时耗，提高聚类收敛速率。

2 改进的FCM算法
2.1 确定初始化聚类中心及类别数
　（1）引入网格加权
　将FCM算法与网格聚类的方法相结合，目的是引入网格聚类的优点：在处理数据时与数据对象的数目无关，只与每维空间所划分的单元数目有关，保证聚类方法的高效性。在FCM算法中引入权重，对于网格密度大的空间，可以赋予相应大的权重，如定义3。最大程度保存原始数据分布特点，保证聚类结果的有效性。
　（2）利用权值寻找连通分量法，确定初始化聚类中心
　类别中的数据在一定范围内是密集的，即相应的网格数据之间连通，并且相应的密度权值从最高密度中心向外递减，密度权值最大的网格肯定包含于某一类别。步骤如下：
　①找到权值最大的网格，递归寻找所有与之连通的网格。递归结束需满足以下条件：没有与之相连通的有数据的网格；虽然存在与之连通的网格，但是该网格的权值大于当前网格的权值。
　②把步骤①中找到的连通网格看成一个初始类，并删除选中的节点。然后重复上面的步骤，直到所有的数据网格都被处理完为止。
　（3）对初始化聚类中心，与自适应免疫算法[2]进行结合。把聚类中心点看成是抗体，把相应的数据点看成是抗原。该抗体能够识别周围一定范围内的抗原。其中?着，?滓是预先确定的门限值。具体步骤如下：
　①对中心进行加权，权值以此中心所识别的抗原个数为依据。
　②遍历所有抗原计算其对于各抗体的亲和度，并根据式（3）进行相应的变异。
　变异率与抗原与抗体之间的距离成正比，与抗原的权值成反比，与亲和力成反比，根据式（4）进行计算。
　③把抗体之间的距离小于?着的抗原进行合并，形成记忆细胞。
　④重复②、③直到无满足条件的操作为止。
    ⑤去除不同记忆细胞中距离小于?滓的个体，即对其进行合并。所形成的新记忆细胞就是最后的初始化聚类中心，记忆细胞的个数就是初始化的类别数。

　（1）在改进的FCM算法中，计算过程只迭代了31次出结果。而原始的FCM算法迭代了74次，才出结果。在时间效率上，改进的FCM算法有明显的提高。
　（2）改进的FCM算法在迭代过程中比较平稳，并且收敛的速度也比较快。然而未改进的FCM算法虽然总的趋势也是收敛的，可是收敛的速度存在一定的波动。
　本文针对FCM算法中存在的计算时耗高，对初始化数据敏感，容易陷入局部最优的问题，引入网格聚类，加权计算，寻找连通分量，自适应免疫算法等方法并采用初始化预处理的方法，对其进行一定的改进。在试验中采集局域网中的数据包使实验数据随机分布，存在局部最优解。与原始的FCM算法进行对比试验，结果表明，改进的FCM算法在时间效率和收敛速度上都有明显的提高，改进的FCM算法是有效的。
参考文献
[1] XINCHAO Z. Simulated annealing algorithm with adaptive neighborhood[J]. Applied Soft Computing， 2011，11（2）：1827-1836.
[2] SZABO A， CASTRO L N D， DELGADO M R. FaiNet： An immune algorithm for fuzzy clustering[C]. in Fuzzy Systems （FUZZ-IEEE）. 2012 IEEE International Conference on. 2012.
[3] HATHAWAY R J， HU Y. Density-weighted fuzzy c-means clustering[J]. IEEE Transactions on Fuzzy Systems， 2009. 17（1）： 243-252.
[4] XING W， ZHAO Y， LI T. Research on the defense against ARP spoofing attacks based on Winpcap[C]. in Education Technology and Computer Science（ETCS）， 2010 Second International Workshop on， 2010.