(南京航空航天大學(xué) 信息中心, 南京 210016)

0 引言

當(dāng)今已是大數(shù)據(jù)時(shí)代，隨著信息技術(shù)的發(fā)展，人們積累的音頻、視頻、文本圖片等越來越多，在某些時(shí)候需要將這些數(shù)據(jù)從海量的數(shù)據(jù)中提取出來，從而將這些數(shù)據(jù)提供給相關(guān)研究人員進(jìn)行研究和分析。為了將這些不同屬性的數(shù)據(jù)進(jìn)行正確分類，必須采用聚類算法或分類算法，聚類和分類是機(jī)器學(xué)習(xí)中兩種重要的理論和技術(shù)，原理上來看聚類技術(shù)和分類技術(shù)有明顯的區(qū)別，聚類分析是一種無監(jiān)督的學(xué)習(xí)，而分類技術(shù)一種有監(jiān)督的學(xué)習(xí)[1-9]，聚類分析的智能性要強(qiáng)于其它算法，基于上述理由可以知道聚類分析在大數(shù)據(jù)時(shí)代有著廣泛的應(yīng)用[10-13]。

聚類分析是一種尋找最優(yōu)解的算法，而粒子群算法，人工蜂群算法以及人工蟻群算法都是一種尋找問題最優(yōu)解的算法，然而這些仿生物學(xué)的智能算法在聚類過程中都有所應(yīng)用。人工蟻群算法最早是由意大利學(xué)者M(jìn)Dorigo提出，該算法在工程領(lǐng)域中主要有如下應(yīng)用：組合優(yōu)化問題，網(wǎng)絡(luò)優(yōu)化，機(jī)器人優(yōu)化等一系列方面[1-9]。人工蟻群在聚類技術(shù)中也有相當(dāng)?shù)膽?yīng)用: 人工蟻群的覓食過程就是一個(gè)尋找問題最優(yōu)解的過程，因此基于蟻群覓食行為的算法在聚類算法中是最早的應(yīng)用[1-9]。在2000年Monmarche學(xué)者提出了一種混合型的蟻群聚類算法[3-9]，該算法在聚類時(shí)容易產(chǎn)生早熟現(xiàn)象，在收斂之前過早的就終止了該算法，這樣將造成算法的聚類效果較差等不足之處。人工蟻群在搜索食物源之時(shí)，人工螞蟻都能揮發(fā)一種叫做信息素的物質(zhì)，因此Labroche等相關(guān)科研人員根據(jù)人工蟻群的這一特征，在2002年提出了一種基于人工蟻群信息素濃度的聚類算法[2-9]，在該算法中人工蟻群，在通過不同的標(biāo)簽來尋找巢穴這一過程，從而實(shí)現(xiàn)數(shù)據(jù)聚類的目的，此算法具有較強(qiáng)的魯棒性性和較好的適應(yīng)性，但在算法收斂性這一方面存在一定問題，值得廣大科研人員研究。以上是蟻群算法在聚類中有不同的應(yīng)用，這些算法存在一定的優(yōu)點(diǎn)，同時(shí)也存在某些的不足之處，因此本文在參考了相關(guān)的蟻群算法和聚類算法后，提出了一種新的聚類算法，該算法有兩部分組成即相似性計(jì)算與蟻群算法對(duì)聚類中心的選擇。

1 什么是聚類分析

聚類分析是一種智能技術(shù)，在數(shù)據(jù)挖掘中是一個(gè)重要分支。聚類技術(shù)能夠?qū)ξ粗獢?shù)據(jù)進(jìn)行有效的分類，強(qiáng)化機(jī)器的智能性，因此各種聚類算法在各個(gè)科學(xué)領(lǐng)域都有所應(yīng)用[10-13]。

聚類算法的思想是使用一定的規(guī)則將最為相似的數(shù)據(jù)聚成一個(gè)族，然而要求不同族之間的差異性達(dá)到最大值，這就是數(shù)據(jù)的聚類[10-13]。聚類分析進(jìn)行數(shù)據(jù)聚類時(shí)，在沒有訓(xùn)練的條件下能夠把對(duì)象劃分為若干類，這樣最相似的數(shù)據(jù)就聚成了族，因此聚類分析進(jìn)行數(shù)據(jù)聚類時(shí)是一種無監(jiān)督的學(xué)習(xí)。聚類分析中，同一個(gè)族中的數(shù)據(jù)具有較高的相似度，而不同的族數(shù)據(jù)之間的差異達(dá)到最大，這就是聚類的最大特點(diǎn)，在聚類的過程中相似度是聚類經(jīng)常采用的度量方法。

2 蟻群算法的介紹

2.1 蟻群算法的特點(diǎn)

蟻群算法最初之目的是幫助人們?nèi)ダ斫馕浵佭@類物種的復(fù)雜行為。蟻群算法出現(xiàn)后不久，便引起了數(shù)學(xué)家、計(jì)算機(jī)專家和工程師們的注意，他們把超越生物本身的模型，轉(zhuǎn)換成為一項(xiàng)有用的優(yōu)化和控制算法，該算法這就是蟻群算法[6-13]。

蟻群在尋找到達(dá)食物源的最短路徑時(shí)，是群體的行為，這些蟻群在路徑中都會(huì)留下一種叫做信息素的物質(zhì)，信息素具有揮發(fā)性。蟻群之間通過信息素這一物質(zhì)進(jìn)行相互交流，從而實(shí)現(xiàn)蟻群之間的相互協(xié)作和競爭。在路徑上的信息素濃度有強(qiáng)有弱，然而蟻群總是向著信息素濃度最高的方向前進(jìn)。如果路徑中的蟻群數(shù)量越多，則信息素的濃度就越高，信息素濃度越高，則吸引更多的螞蟻來到這條路勁中，因此在信息素的協(xié)調(diào)和作用下，使得整個(gè)蟻群都能向著食物源的方向前進(jìn)。

2.2 蟻群算法的簡要分析

蟻群是一個(gè)種群，所以蟻群在尋找最短路徑過程中是一個(gè)群體行為，螞蟻之間通過相互和協(xié)作和競爭來完成共同的目標(biāo)。當(dāng)蟻群出發(fā)尋找最短路徑時(shí)，各條路徑中的螞蟻可以在不同的時(shí)間點(diǎn)上出發(fā)，也可以在同一個(gè)時(shí)間點(diǎn)上，有若干螞蟻同時(shí)出發(fā)。當(dāng)蟻群搜索算法開始時(shí)，尋找最短路徑時(shí)是螞蟻的個(gè)體行為，但是通過蟻群之間的協(xié)調(diào)機(jī)制和信息素，最終能使得整個(gè)蟻群都能找到通往食物源的最短路徑。

在蟻群算法中，蟻群之間采用一種分布式的合作機(jī)制，蟻群之間的協(xié)作性和并行性是其分布合作的具體表現(xiàn)，信息素濃度的大小指引著蟻群尋找通往食物源的最短路徑，這是蟻群算法的主要特點(diǎn)。在蟻群算法中人工螞蟻具有記憶力，因此縮短了蟻群尋找最短路徑的時(shí)間，從而提高了算法的效率。由于人工螞蟻具有記憶力，從而蟻群在尋找最短路徑時(shí)，并不是盲目的搜索，而是有規(guī)律、有意識(shí)地尋找最優(yōu)路徑，即最短路徑。

2.3 蟻群算法的重要參數(shù)

β指的是期望啟發(fā)因子，它反映的是啟發(fā)式信息在影響蟻群搜索的過程中的相對(duì)重要度。β值越大，蟻群就越容易選擇局部較短路徑，這時(shí)算法的收斂速度是加快了，但是隨機(jī)性卻不高，容易得到局部的相對(duì)最優(yōu)。

Q同樣是蟻群算法中的一個(gè)重要參數(shù)，蟻群進(jìn)行搜索時(shí)在路徑中能留下不同強(qiáng)度的信息素，不同路徑中蟻群揮發(fā)的信息素濃度是不同的，如果路徑中信息素濃度越大，則Q的值就越大，事實(shí)可以證明Q值大小的不同，能對(duì)整個(gè)蟻群算法產(chǎn)生不同的正反饋功能。算法在正反饋和負(fù)反饋的影響下，能夠有效地找到問題的最優(yōu)解。

3 數(shù)據(jù)的聚類過程

3.1 聚類數(shù)據(jù)的相似度計(jì)算

(1)

分析和討論：

在3.2經(jīng)過3.1的數(shù)據(jù)屬性相似度計(jì)算后，以下用蟻群算法進(jìn)行數(shù)據(jù)聚類中心選擇。

3.2 聚類中心的選擇與聚類的實(shí)現(xiàn)

1)函數(shù)：

h(x)=|1-f(x)|

(2)

以上函數(shù)討論如下：

當(dāng)公式(1):yn=f(x)比值越近于1，則表明數(shù)據(jù)的相似性更優(yōu)。數(shù)據(jù)相似越好，則此時(shí)h(x)=|1-f(x)|的值就越小，在采用蟻群算法進(jìn)行聚類時(shí)，聚類數(shù)據(jù)選擇該聚類中心的概率也就越大，此時(shí)蟻群啟發(fā)參數(shù)β期望值的相對(duì)重要程度也相對(duì)越大。

當(dāng)公式(1):yn=f(x)比值偏離1的程度越明顯，則表明數(shù)據(jù)的相似性更差。數(shù)據(jù)相似越差，則此時(shí)h(x)=|1-f(x)|的值就越大，在采用蟻群算法進(jìn)行聚類時(shí)，聚類數(shù)據(jù)選擇該聚類中心的概率也就越小，此時(shí)蟻群啟發(fā)參數(shù)β期望值的相對(duì)重要程度也相對(duì)越小。

2)在采用蟻群算法進(jìn)行數(shù)據(jù)聚類時(shí)，聚類公式：h(x)=|1-f(x)|有以下的分析和結(jié)論：

(1)蟻群算法聚類時(shí)相關(guān)參數(shù)的說明：

符號(hào)di j代表著城市i轉(zhuǎn)移到城市j的距離，每一個(gè)城市都是聚類過程中的一個(gè)聚類中心。

在選擇聚類中心的算法中：設(shè)定dij=h(x)=|1-f(x)|。

在聚類中心選擇算法中，有兩個(gè)重要的蟻群算法參數(shù)：

參數(shù)ηij表示某條路徑的能見度程度，反映由城市i轉(zhuǎn)移到城市j的啟發(fā)程度，通常取值為1/dij。參數(shù)β是蟻群算法中的一個(gè)重要因子，作為蟻群尋找下一條路徑的期望啟發(fā)因子。β值越大，則人工螞蟻選擇這條路徑的概率就也大，并且蟻群越傾向于能見程度高的路徑上行走，因此β和ηij的值越大，則人工蟻群選擇該路徑的概率就越大，該路徑上的人工蟻群數(shù)量就也就越多。另外在蟻群算法中還以可以證明減小距離，參數(shù)β的值也可使該路徑被選中的概率增加。

(2)蟻群算法聚類中心的選擇：

在本文提出的算法中，一般將數(shù)據(jù)視為具有不同屬性的人工螞蟻，聚類中心就是蟻群所要尋找的食物源，數(shù)據(jù)聚類的過程可以被看作是螞蟻尋找食物源的過程，在這一過程中每個(gè)城市可看作某個(gè)聚類中心，當(dāng)蟻群從一個(gè)城市到達(dá)另一個(gè)城市時(shí)，這些聚類中心可以按照一定的規(guī)律變化。

以下是聚類過程中聚類中心選擇的具體分析：

(3)數(shù)據(jù)聚類過程的分析：

當(dāng)蟻群選擇一個(gè)聚類中心后，這條路徑中的信息素濃度會(huì)逐步的增大，這時(shí)蟻群算法中的參數(shù)Q值就會(huì)逐步變大。然而Q值越大，這樣又會(huì)吸引更多的人工螞蟻來到這個(gè)聚類中心。在本文中人工螞蟻代表的含義需要聚類的數(shù)據(jù)，因此這些根據(jù)蟻群搜索食物的原理，相似屬性的數(shù)據(jù)都能在無監(jiān)督學(xué)習(xí)的條件下聚集到某個(gè)聚類中心。

當(dāng)蟻群發(fā)現(xiàn)下一個(gè)更佳的聚類中心時(shí)，那么原來路徑中人工蟻群的數(shù)量會(huì)逐步減少，并且蟻群揮發(fā)的信息素濃度也會(huì)逐步減小，此時(shí)蟻群算法的參數(shù)Q值就會(huì)逐步變小。然而在通往新聚類中心的路徑上信息素濃度又會(huì)逐步增強(qiáng)，Q值就會(huì)逐步變大。如果Q的值越大，這樣又會(huì)吸引更多的人工螞蟻來到這個(gè)新的聚類中心，此時(shí)可以達(dá)到數(shù)據(jù)聚類的新目的。

蟻群算法在搜索食物源的過程是反復(fù)迭代的過程，因此采用蟻群算法作為聚類的過程也是一個(gè)多次迭代的過程，經(jīng)過若干次反復(fù)迭代過程，需要聚類的數(shù)據(jù)都找到最好的聚類中心，最終達(dá)到數(shù)據(jù)之目的。

在3.1節(jié)的算法中對(duì)需要聚類數(shù)據(jù)進(jìn)行了相似的計(jì)算，而在3.2節(jié)中采用蟻群算法為相似的數(shù)據(jù)選擇了相應(yīng)的聚類中心，因此經(jīng)過3.1與3.2兩部分算法對(duì)數(shù)據(jù)屬性的計(jì)算可以完成對(duì)未知數(shù)據(jù)的聚類。

4 結(jié)束語

為了對(duì)海量數(shù)據(jù)進(jìn)行相似性計(jì)算，需要采用聚類算法，聚類算法是一種智能型算法，因此在工程領(lǐng)域中有廣泛地應(yīng)用價(jià)值。本文采用數(shù)據(jù)屬性的相似性計(jì)算實(shí)現(xiàn)了數(shù)據(jù)的聚類，而經(jīng)典型的聚類算法是通過計(jì)算數(shù)據(jù)與聚類中心的距離來實(shí)現(xiàn)聚類的，這是不同于其他聚類算法的特征之處，蟻群算法在聚類算法中的再次應(yīng)用也體現(xiàn)了該算法是一種尋找最優(yōu)解的算法，由本文提出的聚類算法有自己的特色和不同于其它算法的地方，該算法在某種程度上具有一定的智能性，能夠?qū)δ承?shù)據(jù)進(jìn)行聚類。

參考文獻(xiàn)：

[1] 李玲娟,李 冰.一種基于特征加權(quán)的蟻群聚類新算法[J].計(jì)算技術(shù)與發(fā)展,2010,20(8):67-70.

[2] 張建華,江 賀,張憲超.蟻群聚類算法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2006(6):171-174.

[3] 李 振,賈瑞玉.一種改進(jìn)的K-means蟻群聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(12):28-31.

[4] 王 鶴.蟻群聚類算法[J].中國科技信息,2007(15):280-281.

[5] 馬春英,曹安得,周允征.蟻群聚類組合的改進(jìn)算法[J].沈陽建筑大學(xué)學(xué)報(bào)(自然科學(xué)版).2011,27(4):798-803.

[6] 田力威,曹安得.基于信息熵的蟻群聚類組合算法的研究[J].計(jì)算機(jī)應(yīng)用研究,2011,28(4):1269-1271.

[7] 向培素.聚類算法綜述[J].西南民族大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,37(5):112-114.

[8] 陳一昭,姜 麟.蟻群算法參數(shù)分析[J.].科學(xué)技術(shù)與工程,2011,11(36):9080-9084.

[9] 徐紅梅,陳義保,劉加光,等.蟻群算法總參數(shù)設(shè)置的研究[J].山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,22(1):7-11.

[10] 方 媛,車啟鳳.數(shù)據(jù)挖掘之聚類算法綜述[J.]河西學(xué)院學(xué)報(bào),2012,28(5):72-75.

[11] 伍育紅.聚類算法綜述[J].計(jì)算機(jī)科學(xué),2015,42(6):491-524.

[12]李衛(wèi)軍.K-means聚類算法的研究綜述[J].現(xiàn)代計(jì)算機(jī)，2014(8):31-36.

[13] 海 沫.大數(shù)據(jù)聚類算法綜述[J].計(jì)算機(jī)科學(xué),2016,43(6):380-383.