基于aiNet免疫網(wǎng)絡(luò)模型的K-means聚類算法

劉彥保，雷 珍，袁 倩，朱文婷

(延安大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西延安716000)

基于aiNet免疫網(wǎng)絡(luò)模型的K-means聚類算法

劉彥保，雷 珍，袁 倩，朱文婷

(延安大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西延安716000)

提出了一種基于aiNet免疫網(wǎng)絡(luò)模型的K-means聚類算法。該算法利用aiNet免疫網(wǎng)絡(luò)模型中抗體-抗原之間的親和力來計算聚類中心點，將數(shù)據(jù)分為若干子簇，之后再通過K-means聚類算法將這些子簇合并，得到最終的結(jié)果。該算法繼承了免疫算法速度快，效率高的優(yōu)點，同時也避免了K-means聚類算法容易陷入局部極小值的缺點，是一種高效的并行搜索算法。

K-means聚類算法；aiNet免疫網(wǎng)絡(luò)；親和力

人工免疫系統(tǒng)(AIS：Artificial Immune System)是根據(jù)生物免疫系統(tǒng)的相關(guān)特征原理，研究出來用于解決工程問題的一種計算機信息系統(tǒng)[1]，具有自適應(yīng)性動態(tài)的基本特征。其研究方向包括了數(shù)據(jù)控制、數(shù)據(jù)處理、圖像處理、優(yōu)化問題等諸多領(lǐng)域，已經(jīng)成為模糊邏輯理論和神經(jīng)網(wǎng)絡(luò)之后的又一個研究方向。目前人工神經(jīng)系統(tǒng)有很多種模型，aiNet免疫網(wǎng)絡(luò)模型就是其中很經(jīng)典的一種。

1 K-means聚類算法

聚類[2]就是將整體中具有相似特點的一些信息或者數(shù)據(jù)歸結(jié)為一個整體，記錄到一個子集中的一種數(shù)據(jù)分類方式。聚類的方法大致分為層次聚類、密度聚類和分割聚類三種。K-means聚類算法[3]就是分割聚類中的一種經(jīng)典算法。它是一種簡單的迭代型分割聚類算法，它是將給定的數(shù)據(jù)分給用戶指定的若干聚簇中，算法簡單，速度很快，也易于修改，所以K-means聚類算法在現(xiàn)實應(yīng)用中比較廣泛，它也是數(shù)據(jù)挖掘領(lǐng)域中最經(jīng)典的算法之一。

但是K-means聚類算法也有一定的局限性，它的K值取值存在局限性，很多時候，K值取值都是經(jīng)驗取值，取值不同，結(jié)果就不同，所以K的取值大大影響了算法結(jié)果的準確率。本文就是利用aiNet免疫網(wǎng)絡(luò)模型中抗體-抗原之間的親和力來計算確定K值，將數(shù)據(jù)分為若干子簇，之后再通過K-means聚類算法將這些子簇合并，得到最終的聚類結(jié)果。

2 aiNet免疫網(wǎng)絡(luò)模型

2.1 模型概述

aiNet網(wǎng)絡(luò)模型[4]是De Castro在2000年提出的一種免疫網(wǎng)絡(luò)模型，它使用的可塑性和動態(tài)性屬于進化策略控制網(wǎng)絡(luò)的典型特征。aiNet網(wǎng)絡(luò)模型包括了Ab-Ag的識別、計算親和力是否成熟、免疫克隆如何增值、以及網(wǎng)絡(luò)抑制四個過程。這個過程也就是aiNet網(wǎng)絡(luò)對抗原的刺激反應(yīng)過程。

aiNet免疫網(wǎng)絡(luò)模型實際上是一個邊界加權(quán)圖，它不需要將邊全部鏈接，因為它的每個節(jié)點對就是它的邊界。每個邊界都有自己獨立的連接強度與權(quán)值。它經(jīng)過不斷的自我調(diào)整與識別、最終輸出細胞親和力矩陣和最終的記憶細胞矩陣。如圖1所示，記憶細胞矩陣負責將映射數(shù)據(jù)集合中的數(shù)據(jù)，也就是抗原群體的網(wǎng)絡(luò)映像聚類到網(wǎng)絡(luò)聚類中。通過此項過程，aiNet隨機產(chǎn)生了一個網(wǎng)絡(luò)結(jié)構(gòu)，如圖2所示，Ag-Ab間親和力由節(jié)點間的距離表示。

圖1 網(wǎng)絡(luò)聚類圖

圖2 aiNet免疫網(wǎng)絡(luò)結(jié)構(gòu)模型圖

2.2 親和力計算

生物免疫系統(tǒng)為了保護生物個體免受細菌病毒等的侵害，所有免疫保護機制中首要步驟就是識別外來物質(zhì)(抗原)，識別方法的對象就是抗原與抗體。免疫網(wǎng)絡(luò)模型也是同樣的道理。因此免疫模型必須解決的首要問題就是如何生成能夠識別任何抗原的抗體指令系統(tǒng)。Forrest針對這個問題提出了一種新型編碼方式，他將抗體和抗原統(tǒng)一用定長為1的二進制字符串表示，通過位串的匹配來進行抗體抗原的識別。設(shè)實數(shù)坐標集合

M=，M∈SL?SL?SL，

其中S表示狀態(tài)空間，L表示維數(shù)。抗原Ab∈M，Ag∈M。

Ag-Ab之間的親和力[5]一般由抗體抗原之間的距離計算，如Manhattan距離：

2.3 模型的具體學(xué)習(xí)過程

i輸入數(shù)據(jù)，隨機產(chǎn)生抗體，作為初始節(jié)點。

ii計算親和力，將訓(xùn)練集合中的數(shù)據(jù)提供給網(wǎng)絡(luò)進行自主學(xué)習(xí)，每一個數(shù)據(jù)通過和網(wǎng)絡(luò)中的節(jié)點接觸并計算，得到親和力。

iii免疫克隆，選中親和力高的抗體并克隆，克隆數(shù)目與親和力成正比。親和力高，克隆數(shù)目就多，親和力越低，變異率就越高。在最終的克隆數(shù)據(jù)中，將親和力高的抗體加入到原來的網(wǎng)絡(luò)中，這些抗體也被成為記憶抗體。

iv調(diào)整網(wǎng)絡(luò)[6]，新的網(wǎng)絡(luò)還要進行進一步的調(diào)整，計算原抗原與新抗體之間的親和力，刪除親和力小于一定閾值的抗體數(shù)據(jù)，另外，在隨機加入新的抗體進入網(wǎng)絡(luò)，重復(fù)2-4步驟，直到不需要調(diào)整為止。

3 基于aiNet免疫網(wǎng)絡(luò)模型的K-means聚類算法

3.1 基于aiNet免疫網(wǎng)絡(luò)模型的k值選擇

i產(chǎn)生初始網(wǎng)絡(luò)，輸入e個抗原。隨機生成初始網(wǎng)絡(luò)，產(chǎn)生初始的c個抗體。

圖3 算法流程圖

ii識別抗原，分別計算每個抗原-抗體的親和力，依照抗原與網(wǎng)絡(luò)抗體庫中的親和力最大的值，對抗體親和力排序，顯示前n個結(jié)果。

iii用戶反饋，用戶根據(jù)顯示結(jié)果，指定反饋對象。

iv抗體選擇，由用戶反饋的對象特征，計算現(xiàn)有網(wǎng)絡(luò)抗體庫的親和力，將其按照從高到低的順序排列。

v抗體克隆與變異，將用戶反饋對象親和力最高的網(wǎng)絡(luò)抗體克隆，細胞親和力越大，克隆數(shù)越大。

vi抗體抑制，選擇克隆產(chǎn)生的網(wǎng)絡(luò)抗體矩陣中細胞親和力最高的細胞生成記憶細胞矩陣，連接網(wǎng)絡(luò)抗體庫與記憶細胞矩陣，清除親和力低的細胞，計算網(wǎng)絡(luò)抗體與抗體之間的親和力，清除親和力高的細胞，將用戶反饋特征加入網(wǎng)絡(luò)抗體庫。

vii利用生成的高親和力特征組，重新檢索，如此循環(huán)，直到結(jié)束檢索，算法停止。輸出結(jié)果為聚N個聚類中心點，即N個子簇。算法流程圖如圖3所示。

3.2 基于aiNet免疫網(wǎng)絡(luò)模型的K-means聚類算法

i將aiNet免疫網(wǎng)絡(luò)模型的輸出結(jié)果作為K-means聚類算法的k個聚類中心點。

ii根據(jù)k個聚類中心點把數(shù)據(jù)劃分為k個聚類。

iii計算上一步得到的每個聚類的中心點(由算數(shù)平均值計算)。

iv解散前一個階段形成的聚類，重復(fù)ii-iii步驟，直到聚類中心點不再發(fā)生變化為止。

4 實驗

表1 樣本數(shù)據(jù)

圖4 聚類結(jié)果圖

為了驗證上述算法的可行性，對表1數(shù)據(jù)所示的20個數(shù)據(jù)進行了仿真實驗，運用aiNet免疫網(wǎng)絡(luò)模型的K-means聚類算法迭代50次，目標聚簇為3，結(jié)果如圖4所示。結(jié)果表明，這種聚類算法可以避免局部極小值，具有很好的可行性。

5 結(jié)束語

本文將人工免疫原理中的aiNet免疫網(wǎng)絡(luò)模型與K-means聚類算法相結(jié)合，利用免疫網(wǎng)絡(luò)中抗體與抗原之間的親和力來計算聚類中心點，避免了K-means聚類算法容易陷入局部極小值的不足，同時也擁有了免疫算法計算速度快效率高的優(yōu)點，并且可忽略噪聲，能夠識別任意形狀的數(shù)據(jù)，是一種高效的并行搜索聚類算法。

[1]王沖，雷秀娟.基于人工免疫系統(tǒng)的蛋白質(zhì)相互作用網(wǎng)絡(luò)聚類算法[J].計算機應(yīng)用，2013，33(12)：3567-3570.

[2]田玉玲，段富.免疫優(yōu)化算法、模型及應(yīng)用[M].北京：國防工業(yè)出版社，2013：96-101.

[3]李文波，吳素研.數(shù)據(jù)挖掘十大算法[M].北京：清華大學(xué)出版社，2013：18-30.

[4]王珺，劉希玉.基于人工免疫系統(tǒng)aiNet模型的層次聚類算法[J].計算機工程與應(yīng)用，2006，24：167-169.

[5]劉世平，數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京：高等教育出版社，2010：30-37.

[6]耿立川，吳云東.基于aiNet人工免疫網(wǎng)絡(luò)的遙感圖像檢索[J].計算機工程與應(yīng)用，2010，46(7)：226-228.

[責任編輯 畢 偉]

K-means Clustering Algorithm Based on aiNet Immune Network Model

LIU Yan-bao,LEI ZHEN,YUAN QIAN,ZHU Wen-ting

(College of Mathematics and Computer Science,Yan′an University,Yan′an 716000,China)

This paper puts forward aK-means clustering algorithm based on aiNet immune network model.The algorithm calculates the clustering center point using the affinity between antibody and antigen in aiNet immune network model.The data is divided into several sub cluster and merge the clusters with theK-means clustering algorithm.The advantages of this algorithm is fast,high efficiency,and avoids the disadvantages ofK-means clustering algorithm which is easy to fall into local minimum.It is an efficient parallel search algorithm.

K-means clustering algorithm; aiNet immune network; affinity

2015-09-27

劉彥保(1964—)，男，陜西綏德人，延安大學(xué)教授。

TP311

A

1004-602X(2015)04-0027-03