王小華,沈 杰,王榮波

(杭州電子科技大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)研究所,浙江杭州310018)

0 引 言

聚類分析是多元統(tǒng)計(jì)分析的一個(gè)重要分支,是一種無(wú)監(jiān)督的分類,是把一個(gè)沒(méi)有類別標(biāo)記的樣本集按某種相似性準(zhǔn)則劃分成若干個(gè)子集(類),使每一類中的樣本點(diǎn)盡可能相似,而不同類中的樣本點(diǎn)之間的差異盡可能大,其實(shí)質(zhì)是尋找隱藏在數(shù)據(jù)中不同的數(shù)據(jù)模型。目前,常用的聚類算法有基于層次的凝聚算法、基于劃分的算法、基于密度的算法以及基于各種生物模型的算法等[1]。由于聚類算法采取不同的模型,在聚類效果以及時(shí)間復(fù)雜度上各有不同,例如基于劃分的K均值聚類算法,算法簡(jiǎn)單,效果尚佳,但是該算法對(duì)于初始參數(shù)敏感,不易于找到全局最優(yōu)解,而蟻群算法易于找到全局優(yōu)化解,而收斂速度相對(duì)較慢。本文提出一種基于蟻群算法[2]和凝聚算法的混合聚類算法,并對(duì)蟻群算法加以改進(jìn),在測(cè)試樣本獲得了滿意的結(jié)果。

1 經(jīng)典蟻群算法和凝聚算法

基于蟻群聚類現(xiàn)象建立了一種基本模型(BM)首先提出。后然,BM模型被推廣到數(shù)據(jù)分析范疇[3-5],其主要思想是把待聚類的樣本集數(shù)據(jù)隨機(jī)初始散布在一個(gè)二維平面內(nèi),然后在該平面上放置人工螞蟻對(duì)其進(jìn)行聚類分析。隨著該算法被一步步深入研究,各種改進(jìn)后的算法競(jìng)相涌現(xiàn),一種較為穩(wěn)定的蟻群算法[2,6]被積淀下來(lái)。

定義:

(1)平均相似性

假設(shè)在時(shí)刻t某只螞蟻在地點(diǎn)r發(fā)現(xiàn)一個(gè)數(shù)據(jù)對(duì)象o,則可將對(duì)象oi與其鄰域?qū)ο髈j的平均相似性定義為:

式中,α為相似性參數(shù);v表示螞蟻運(yùn)動(dòng)的速度;vmax為最大速度;Ns(r)表示地點(diǎn)r周圍的以s為邊長(zhǎng)的正方形局部區(qū)域,d(oi,oj)表示對(duì)象oi和oj在屬性空間中的距離。距離表示法較多,根據(jù)不同的數(shù)據(jù)類型可選用不同的距離表示方法。

式2是明可夫斯基距離。

(2)概率轉(zhuǎn)換函數(shù)

概率轉(zhuǎn)換函數(shù)是f(oi)的一個(gè)函數(shù),將數(shù)據(jù)對(duì)象的平均相似性轉(zhuǎn)化為拾起概率Pp或者放下概率Pd。

(3)算法描述

1)初始化蟻群算法參數(shù),螞蟻數(shù)量Ant-Size,最大迭代次數(shù)Max-Iterate,局部邊長(zhǎng)參數(shù)s等,將樣本隨即分布到二維平面。初始化螞蟻,設(shè)置移動(dòng)參數(shù)v。

2)For i=1,2,…,Max-Iterate:

For j=1,2,…,Ant-Size:

①根據(jù)式1計(jì)算對(duì)象平均相似性;

作為一種新型經(jīng)濟(jì)模式和商業(yè)模式，物流業(yè)發(fā)展共享經(jīng)濟(jì)中難免會(huì)遇到質(zhì)疑和困難，有些問(wèn)題會(huì)引起政府或者有關(guān)部門的干涉和禁止。在共享經(jīng)濟(jì)的快速發(fā)展與應(yīng)用中，其更新速度遠(yuǎn)遠(yuǎn)超出了目前政府所監(jiān)管的范疇和能力，政府還沒(méi)有一個(gè)針對(duì)性地健全監(jiān)管制度，一定程度上阻礙了物流業(yè)共享經(jīng)濟(jì)的發(fā)展?；谶@種背景，為了更好地利用共享經(jīng)濟(jì)促進(jìn)我國(guó)綠色物流的建設(shè)、實(shí)現(xiàn)對(duì)社會(huì)物流費(fèi)用的有效降低，政府要充分發(fā)揮出其監(jiān)管作用，建立起針對(duì)物流共享平臺(tái)搭建以及合理運(yùn)行的相關(guān)監(jiān)管制度，形成一個(gè)允許試錯(cuò)、寬容、多元化、開放的經(jīng)濟(jì)環(huán)境，打破一味禁止和限制的監(jiān)管弊端，完善經(jīng)濟(jì)環(huán)境，為物流共享經(jīng)濟(jì)的發(fā)展提供必要保障。

②如果螞蟻無(wú)負(fù)載,根據(jù)式3計(jì)算拾起概率Pp。若Pp大于設(shè)定的閾值,拾起該物體;否則,螞蟻拒絕拾起該物體而選擇其它物體;

③如果螞蟻有負(fù)載,根據(jù)式4計(jì)算放下概率Pd。若Pd大于設(shè)定的閾值,則放下該物體,并選擇一個(gè)新的對(duì)象。

3)For i=1,2,…,n,其中n為所有樣本點(diǎn):

①如果某個(gè)樣本點(diǎn)所在的領(lǐng)域小于某一閾值,則標(biāo)記該樣本點(diǎn)為孤立、異常點(diǎn);

②否則給該對(duì)象分配一個(gè)類id,并且遞歸將其領(lǐng)域樣本點(diǎn)標(biāo)記為同一個(gè)id。

經(jīng)典凝聚算法基本思想:以樣本點(diǎn)的個(gè)數(shù)作為初始類個(gè)數(shù),基于特定的相似度函數(shù)相繼合并兩個(gè)最相似的類,直到滿足退出條件,聚類結(jié)束并獲得聚類結(jié)果。

該算法思路簡(jiǎn)單,如果樣本點(diǎn)大小為n,則算法的時(shí)間復(fù)雜度為O(n2log(n))。若樣本點(diǎn)數(shù)量n規(guī)模大,則直接運(yùn)用該算法消耗的時(shí)間比較大。

2 蟻群算法的改進(jìn)

(1)在螞蟻放置物體時(shí)采用緊湊算法。在二維平面圖中若找到點(diǎn)直接放下物體容易產(chǎn)生松散的物體堆積,造成少量物體占據(jù)大量平面空間,從而在上述蟻群經(jīng)典算法步驟3中遞歸產(chǎn)生類時(shí)模糊類邊界。如圖1所示。

圖1中,b、d子圖分別是a、c子圖采用緊湊算法后螞蟻放置物體后的二維平面圖片段。標(biāo)記為0的網(wǎng)格點(diǎn),表明該點(diǎn)被物體占據(jù),標(biāo)記為1的網(wǎng)格點(diǎn)是經(jīng)典蟻群算法中在放置物體時(shí)選擇的點(diǎn),標(biāo)記為2的網(wǎng)格點(diǎn)是采用緊湊算法后螞蟻放置物體的可能點(diǎn)之一。

(2)對(duì)可被螞蟻拾起的物體進(jìn)行基于評(píng)估函數(shù)的選擇。改進(jìn)的基本思想:根據(jù)螞蟻負(fù)載時(shí)所經(jīng)過(guò)的步數(shù)對(duì)物體放下后被重新選擇的優(yōu)先級(jí)進(jìn)行設(shè)置:

1)若螞蟻拾起物體后,沒(méi)有移動(dòng)即放下,或者在相對(duì)少的步數(shù)之內(nèi)就放下物體,則表明該物體已經(jīng)處于某一相對(duì)正確的類中,將該物體放入優(yōu)先級(jí)低的隊(duì)列;

2)若螞蟻拾起物體后,走了相對(duì)較多的步驟才放下物體,則表明螞蟻放下的物體剛剛加入某一類中,穩(wěn)定性待測(cè),則將該物體放入優(yōu)先級(jí)高的隊(duì)列;

圖1 采用緊湊算法后物體放置點(diǎn)

3)若螞蟻拾起物體后走的步驟大于某一相對(duì)較大閾值,則可認(rèn)為該物體為噪聲點(diǎn),將該物體放入不可再被螞蟻負(fù)載隊(duì)列;

4)當(dāng)螞蟻負(fù)載為空時(shí),基于評(píng)估函數(shù)從未被負(fù)載的物體隊(duì)列中獲得物體,從而使不穩(wěn)定的點(diǎn)以更大的概率融入合適的類中。

3 混合的蟻群算法和凝聚算法

由經(jīng)典的凝聚算法可知,若直接使用凝聚對(duì)原始樣本點(diǎn)進(jìn)行聚類,由于樣本點(diǎn)的數(shù)量直接制約了聚類的時(shí)間,若在蟻群算法迭代過(guò)程中,基于蟻群算法形成的粗聚類進(jìn)行凝聚算法,則可以加速蟻群聚類算法,使得分散類獲得直接合并的機(jī)會(huì)。如圖2所示。

圖2 凝聚算法效果圖

圖2(a)表示在蟻群算法作用下,一些小的類形成,但沒(méi)有合并應(yīng)該合并的類。圖2(b)表示在對(duì)左圖所代表的粗聚類結(jié)果進(jìn)行凝聚后的聚類結(jié)果。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)數(shù)據(jù)是來(lái)自UCI的iris花卉數(shù)據(jù)集[7],該數(shù)據(jù)集是由3種類別組成的150個(gè)樣本采集點(diǎn),每個(gè)樣本點(diǎn)包含有4個(gè)屬性。實(shí)驗(yàn)計(jì)算F-measure[2]值和運(yùn)行時(shí)間,共進(jìn)行10次,取其中最好的成績(jī)作為結(jié)果。參與實(shí)驗(yàn)的算法除了本文提出的混合聚類算法,還有經(jīng)典蟻群算法、遺傳算法、禁忌搜索算法、模擬退火算法[6]。如表1所示。

表1 聚類算法實(shí)驗(yàn)結(jié)果表

由表1的測(cè)試結(jié)果可知,本文改進(jìn)的方法在F-measure值這項(xiàng)基本上與最好的經(jīng)典蟻群算法持平,但在運(yùn)行時(shí)間上有了很大的提高,獲得了較好的結(jié)果。

5 結(jié) 論

本文提出一種基于蟻群算法和凝聚算法的混合聚類算法,該算法采用改進(jìn)蟻群算法,并融入凝聚算法到蟻群算法模型。與經(jīng)典蟻群算法相比,本文提出的方法在繼承蟻群聚類算法的固有優(yōu)點(diǎn)的同時(shí),速度更快,效果更佳,另外對(duì)于樣本中異常點(diǎn)加以檢測(cè),是一種較為新穎的混合聚類算法。

[1] 范明,范宏建.數(shù)據(jù)挖掘?qū)д揫M].北京:人民文學(xué)出版社,2006:320～321.

[2] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2007:290～297.

[3] Deneubourg JL,Goss S,Franks N.The dynamics of collective sorting:robot-likeants and ant-like robots[J].Proceedings of the 1st International Conference on Simulation of Adaptive Behavior From Animal to Animal,1991,25(18):356～363.

[4] Dorigo M,Bonabeaub E,Theraulaz G.Antalgorithms and stigmergy[J].Future Generation Computer Systems,2000,16(8):851～871.

[5] Erik D,Lumer Baldo Faieta.Diversity and adaptation in populations of clustering ants[J].Proceedings of the third international conference on Simulation of adaptive behavior from animals to animals,1994,19(6):501～508.

[6] Shelokar P S,Jayaraman V K,Kulkarni BD.An ant colony approach for clustering[J].Analytic Chimica Acta,2004,33(23):187～195.

[7] Fisher R A.Iris Data Set[EB/OL].http://www.ics.uci.edu/mlearn/MLRepository.htm l.2009-04-08.