摘  要： 在數(shù)據(jù)采集過程中結(jié)合網(wǎng)格聚類算法提高計(jì)算效率，為了保存采樣數(shù)據(jù)的分布特點(diǎn)引入權(quán)值。根據(jù)類別中心密度高、權(quán)值大的特征采用尋找連通分量的方法初步確定聚類中心，在此基礎(chǔ)上結(jié)合自適應(yīng)免疫算法，動(dòng)態(tài)地確定聚類中心及其類別數(shù)。進(jìn)而使FCM算法跳出局部最優(yōu)，最大可能地得到全局最優(yōu)解。
關(guān)鍵詞： 聚類；權(quán)值合理性；自適應(yīng)免疫算法；連通分量

　FCM算法是當(dāng)前最受關(guān)注的聚類方法之一。本質(zhì)上，F(xiàn)CM算法是一種初始化數(shù)據(jù)與聚類結(jié)果之間的映射方法，其求解過程采用一種爬山技術(shù)進(jìn)行迭代來尋找局部最優(yōu)解。當(dāng)初始化完成后，相應(yīng)的聚類結(jié)果就已經(jīng)確定了。所以FCM算法對(duì)初始化數(shù)據(jù)比較敏感，有可能陷入局部最優(yōu)解，無法得到全局最優(yōu)解。
　針對(duì)此問題目前主要的解決方法有兩種：（1）在聚類的過程中進(jìn)行全局隨機(jī)搜索[1]，Xinchao等人采用模擬退火算法。對(duì)當(dāng)前聚類所獲得的結(jié)果采用退火計(jì)劃進(jìn)行擾動(dòng)，并以一定的概率接受擾動(dòng)后的結(jié)果為當(dāng)前最優(yōu)解，進(jìn)而跳出局部最優(yōu)解。此算法要求足夠多的擾動(dòng)次數(shù)，配以嚴(yán)密的擾動(dòng)計(jì)劃來獲取全局最優(yōu)解，即此算法要求大量的計(jì)算。（2）改善FCM算法的初始化條件，選擇合適的聚類中心[2]。在初始化問題上，本文受第二種方法啟發(fā)，把網(wǎng)格劃分加權(quán)[3]、尋找連通分量、自適應(yīng)免疫算法[2]相結(jié)合。對(duì)原始數(shù)據(jù)進(jìn)行初始化處理，動(dòng)態(tài)尋找初始類別數(shù)和相應(yīng)的聚類中心。進(jìn)而跳出局部最優(yōu)，最大程度地找到全局最優(yōu)解。本文將原始的FCM算法和改進(jìn)的FCM算法進(jìn)行對(duì)比分析。實(shí)驗(yàn)表明，該改進(jìn)方法能夠有效地降低時(shí)耗，提高聚類收斂速率。

2 改進(jìn)的FCM算法
2.1 確定初始化聚類中心及類別數(shù)
　（1）引入網(wǎng)格加權(quán)
　將FCM算法與網(wǎng)格聚類的方法相結(jié)合，目的是引入網(wǎng)格聚類的優(yōu)點(diǎn)：在處理數(shù)據(jù)時(shí)與數(shù)據(jù)對(duì)象的數(shù)目無關(guān)，只與每維空間所劃分的單元數(shù)目有關(guān)，保證聚類方法的高效性。在FCM算法中引入權(quán)重，對(duì)于網(wǎng)格密度大的空間，可以賦予相應(yīng)大的權(quán)重，如定義3。最大程度保存原始數(shù)據(jù)分布特點(diǎn)，保證聚類結(jié)果的有效性。
?。?）利用權(quán)值尋找連通分量法，確定初始化聚類中心
　類別中的數(shù)據(jù)在一定范圍內(nèi)是密集的，即相應(yīng)的網(wǎng)格數(shù)據(jù)之間連通，并且相應(yīng)的密度權(quán)值從最高密度中心向外遞減，密度權(quán)值最大的網(wǎng)格肯定包含于某一類別。步驟如下：
　①找到權(quán)值最大的網(wǎng)格，遞歸尋找所有與之連通的網(wǎng)格。遞歸結(jié)束需滿足以下條件：沒有與之相連通的有數(shù)據(jù)的網(wǎng)格；雖然存在與之連通的網(wǎng)格，但是該網(wǎng)格的權(quán)值大于當(dāng)前網(wǎng)格的權(quán)值。
?、诎巡襟E①中找到的連通網(wǎng)格看成一個(gè)初始類，并刪除選中的節(jié)點(diǎn)。然后重復(fù)上面的步驟，直到所有的數(shù)據(jù)網(wǎng)格都被處理完為止。
　（3）對(duì)初始化聚類中心，與自適應(yīng)免疫算法[2]進(jìn)行結(jié)合。把聚類中心點(diǎn)看成是抗體，把相應(yīng)的數(shù)據(jù)點(diǎn)看成是抗原。該抗體能夠識(shí)別周圍一定范圍內(nèi)的抗原。其中?著，?滓是預(yù)先確定的門限值。具體步驟如下：
?、賹?duì)中心進(jìn)行加權(quán)，權(quán)值以此中心所識(shí)別的抗原個(gè)數(shù)為依據(jù)。
?、诒闅v所有抗原計(jì)算其對(duì)于各抗體的親和度，并根據(jù)式（3）進(jìn)行相應(yīng)的變異。
　變異率與抗原與抗體之間的距離成正比，與抗原的權(quán)值成反比，與親和力成反比，根據(jù)式（4）進(jìn)行計(jì)算。
　③把抗體之間的距離小于?著的抗原進(jìn)行合并，形成記憶細(xì)胞。
?、苤貜?fù)②、③直到無滿足條件的操作為止。
    ⑤去除不同記憶細(xì)胞中距離小于?滓的個(gè)體，即對(duì)其進(jìn)行合并。所形成的新記憶細(xì)胞就是最后的初始化聚類中心，記憶細(xì)胞的個(gè)數(shù)就是初始化的類別數(shù)。

　（1）在改進(jìn)的FCM算法中，計(jì)算過程只迭代了31次出結(jié)果。而原始的FCM算法迭代了74次，才出結(jié)果。在時(shí)間效率上，改進(jìn)的FCM算法有明顯的提高。
?。?）改進(jìn)的FCM算法在迭代過程中比較平穩(wěn)，并且收斂的速度也比較快。然而未改進(jìn)的FCM算法雖然總的趨勢(shì)也是收斂的，可是收斂的速度存在一定的波動(dòng)。
　本文針對(duì)FCM算法中存在的計(jì)算時(shí)耗高，對(duì)初始化數(shù)據(jù)敏感，容易陷入局部最優(yōu)的問題，引入網(wǎng)格聚類，加權(quán)計(jì)算，尋找連通分量，自適應(yīng)免疫算法等方法并采用初始化預(yù)處理的方法，對(duì)其進(jìn)行一定的改進(jìn)。在試驗(yàn)中采集局域網(wǎng)中的數(shù)據(jù)包使實(shí)驗(yàn)數(shù)據(jù)隨機(jī)分布，存在局部最優(yōu)解。與原始的FCM算法進(jìn)行對(duì)比試驗(yàn)，結(jié)果表明，改進(jìn)的FCM算法在時(shí)間效率和收斂速度上都有明顯的提高，改進(jìn)的FCM算法是有效的。
參考文獻(xiàn)
[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.