宋中山，周 騰，周晶平

(中南民族大學(xué)計算機(jī)科學(xué)學(xué)院，武漢430074)

人們通過對大自然中社會性動物有組織的行為進(jìn)行數(shù)學(xué)建模，提出了群體智能算法［1］，如猴群算法、魚群算法及蟻群算法等，這些群體智能算法使得人類的研究擺脫了固定的模式，大膽地用于解決復(fù)雜的組合優(yōu)化問題，為人工智能的發(fā)展開辟了一條新的道路.

20世紀(jì)90年代，Dorigo M等人提出了蟻群算法［2］，最早被應(yīng)用于解決旅行商問題［3］，還運(yùn)用于二次調(diào)度問題，并結(jié)合數(shù)據(jù)挖掘中的聚類算法，應(yīng)用于很多復(fù)雜的實際問題中［4-6］.但是，蟻群算法中參數(shù)的設(shè)置往往憑借于經(jīng)驗，時常出現(xiàn)易陷入局部最優(yōu)等問題.人們通過對蟻群算法的研究，發(fā)現(xiàn)蟻群算法的很多特性與聚類分析問題的求解方式都比較相似，當(dāng)把蟻群算法和聚類分析結(jié)合使用用于求解問題時，往往比單一使用聚類分析技術(shù)所得到的結(jié)果好很多［7，8］.

本文針對傳統(tǒng)的蟻群聚類算法中參數(shù)設(shè)置依賴于經(jīng)驗的指導(dǎo)以及螞蟻移動隨機(jī)性大等問題，提出一種改進(jìn)的自適應(yīng)蟻群聚類算法，該算法與標(biāo)準(zhǔn)的蟻群聚類算法相比，去除了參數(shù)對聚類結(jié)果的影響，降低螞蟻移動的隨機(jī)性以加快聚類的速度.銀行存在大量的客戶數(shù)據(jù)，將蟻群聚類算法應(yīng)用于銀行客戶細(xì)分，有利于對客戶關(guān)系進(jìn)行管理.

1 蟻群聚類算法

蟻群聚類算法可分為4類:以信息素為指導(dǎo)，根據(jù)螞蟻覓食行為來聚類;根據(jù)螞蟻習(xí)性，以自身形成一堆為指引的行為實現(xiàn)聚類;依據(jù)螞蟻尸體堆積原理聚類;根據(jù)可以相互識別并創(chuàng)建不同巢穴的原理實現(xiàn)聚類.

Lumer和Faieta把Deneubourg等人提出的基本模型進(jìn)行推廣，運(yùn)用到數(shù)據(jù)分析領(lǐng)域，使用實值元素來聚類數(shù)據(jù)向量，提出了LF算法模型［9］，主要思想是:首先將待處理的數(shù)據(jù)隨機(jī)散放在一個Z×Z的2維網(wǎng)格中，同樣也產(chǎn)生一些虛擬的螞蟻，每個網(wǎng)格單元中只能分布一個數(shù)據(jù)對象.d(Oi，Oj)表示網(wǎng)格中的兩個對象Oi和Oj之間的距離，也稱為相似度，一般使用歐式距離，若這兩個對象為同一個對象，則d(Oi，Oj)=0，否則 d(Oi，Oj)=1，進(jìn)而可以得到一個相似度矩陣.設(shè)N只螞蟻在此網(wǎng)格上運(yùn)動，都是隨機(jī)撿起或放下某個數(shù)據(jù)對象，若在某時刻在r位置螞蟻找到了數(shù)據(jù)Oi，則它的局部密度表示為:

其中Neights×s(r)為單元r的鄰域面積，α為相異度因子，它決定了數(shù)據(jù)對象之間的區(qū)分度，α越大區(qū)分度越小，反之亦然，s2表示螞蟻可以觀察到以r為中心的s×s范圍內(nèi)分布的所有數(shù)據(jù)對象.若螞蟻沒有負(fù)載，則隨機(jī)撿起一個鄰近單元中的數(shù)據(jù)對象，其概率為公式(2);若螞蟻有負(fù)載，則隨機(jī)選擇鄰近一個空的單元中，將該數(shù)據(jù)對象放下，其概率為公式(3).

其中k1，k2為閾值常量.

相似密度的大小制約著螞蟻撿起或放下的概率，當(dāng)相似度小時，放下的概率小，撿起的概率大，螞蟻容易將數(shù)據(jù)轉(zhuǎn)移;反之亦然.

從而判斷背負(fù)的對象與觀察到的對象是否相似，對象Oi在地點r處通過相似度計算，從而不斷拾起或放下對象.重復(fù)這一過程，直到達(dá)到算法最初設(shè)置的最大迭代次數(shù)，算法結(jié)束.而數(shù)據(jù)對象最終在2維網(wǎng)格中的分布情況就是聚類的結(jié)果［10］.

2 自適應(yīng)蟻群聚類算法

蟻群聚類算法在求解的過程中，主要存在兩個問題:隨機(jī)選擇策略大大減緩了算法的進(jìn)化速度;正反饋原理的根本是為了得到更好的解，但是容易出現(xiàn)停滯現(xiàn)象.人們對蟻群聚類算法中隨機(jī)參數(shù)的狀態(tài)轉(zhuǎn)移和信息素進(jìn)行研究，主要可以通過以下策略進(jìn)行自適應(yīng)調(diào)節(jié).

(1)隨機(jī)參數(shù)q0的自適應(yīng)調(diào)節(jié).為了避免出現(xiàn)停滯現(xiàn)象，在螞蟻移動過程中動態(tài)調(diào)整轉(zhuǎn)移概率.就是讓螞蟻以q0選擇距離長度短或者信息素濃度較高的節(jié)點，以1－q0來進(jìn)行概率式搜索.

(2)信息素?fù)]發(fā)度ρ的自適應(yīng)調(diào)節(jié).信息素?fù)]發(fā)度ρ的設(shè)置影響到蟻群算法搜索時間的長短以及能否得到全局的最優(yōu)解.使用1－ρ表示信息殘留因子，它間接衡量螞蟻個體間相互影響大小的尺度.若將ρ的最初大小置為1，即ρ(0)=1，使用ρmin表示ρ的最小值，如果蟻群算法某個時刻已經(jīng)求得了一個解，而這個解在后面的N次循環(huán)內(nèi)沒有較大變化時，即當(dāng)0.95ρ(t－1)≥ρmin時，將此時的 ρ置為 0.95ρ(t－1);否則將ρ置為ρmin.通過這種方式對信息素?fù)]發(fā)度不斷進(jìn)行自適應(yīng)調(diào)節(jié).在算法求解過程中，為了提高蟻群算法的查找速度，加大全局搜索的能力，在每次循環(huán)結(jié)束后，求出此時的解，并保存.

(3)通過比較某處螞蟻與其周圍8個鄰居的相異度，記錄螞蟻前一個運(yùn)動狀態(tài)，所處的坐標(biāo)及附屬的類號，可以通過公式(4)定義自適應(yīng)度函數(shù):

其中d(ai，aj)表示螞蟻代表的數(shù)據(jù)對象i和j之間的距離，一般使用歐幾里德距離，而參數(shù)αij可由公式(5)確定.

螞蟻所屬的類可根據(jù)以下規(guī)則進(jìn)行更新.

(1)當(dāng)某個螞蟻到達(dá)一個合適的位置而轉(zhuǎn)變成睡眠態(tài)時，將它所屬的類號更改為與它相異度最小的類號;

(2)若螞蟻由睡眠態(tài)變?yōu)榛钴S態(tài)，則將其類號改為它在移動過程中的類號;

(3)若螞蟻保持睡眠態(tài)不變，則其類號不變.

3 改進(jìn)的蟻群聚類算法

為了解決傳統(tǒng)蟻群聚類算法中容易出現(xiàn)停滯現(xiàn)象和易陷入局部最優(yōu)的問題，本文從以下3個方面對算法進(jìn)行改進(jìn).

(1)公式(1)說明了相似度衡量的方式，其中參數(shù)α的值對聚類的結(jié)果具有較大的影響，它表示相異度因子，它的值沒有范圍，可以達(dá)到任何值，因此參數(shù)α值的設(shè)置往往依賴于經(jīng)驗指導(dǎo)，如果缺乏相關(guān)的經(jīng)驗，很難保證聚類結(jié)果的準(zhǔn)確.由于相似度衡量的標(biāo)準(zhǔn)主要由各模式間的距離決定，由公式(1)可以看出，相似度的大小與模式間的距離成反比，當(dāng)各模式間的距離越小的，所得的相似度越大，反之亦然.依此，本文采用一種更直接的方法，去除α，直接使用公式(6)來表示模式Oi與其局部環(huán)境中其他模式的相似度.

通過公式(6)可以看出，f(Oi)與模式間的距離成正比，即f(Oi)的值越大，說明模式Oi與模式Oj間的距離越大，表明模式Oi與其它模式的相似度越小.公式(6)去除了參數(shù)α對聚類結(jié)果的影響，使得模式的相似度與距離的關(guān)系更加明顯，并且不需要經(jīng)驗的指導(dǎo).

(2)在標(biāo)準(zhǔn)蟻群聚類算法中，螞蟻的前進(jìn)方向是隨機(jī)選擇的.這種隨機(jī)選擇的方法，當(dāng)某只螞蟻長時間承載一個模式，如果找不到合適的位置，會使它一直承載而不放下，或者當(dāng)螞蟻放下一個模式后再次選擇時，一直沒有模式可以選擇而長時間處于空閑狀態(tài).研究發(fā)現(xiàn)，當(dāng)對待處理數(shù)據(jù)進(jìn)行主成分分析后，發(fā)現(xiàn)整體的聚類效果已初步形成.如果螞蟻再次選擇隨機(jī)移動，很可能導(dǎo)致螞蟻后面的多次移動都是無效的，因為螞蟻移動的下一個位置，極有可能該鄰域內(nèi)模式數(shù)據(jù)極少甚至沒有模式，這將嚴(yán)重阻礙螞蟻放下或拾起模式進(jìn)度，對聚類結(jié)果造成影響.針對這些問題，本文采用一種基于網(wǎng)格化的運(yùn)動方式，通過前后坐標(biāo)對比，判斷螞蟻的狀態(tài)，如果處于運(yùn)動，并且需要丟棄模式時，使螞蟻有選擇性地往較多模式的地方運(yùn)動，從而降低螞蟻移動的隨機(jī)性，加快收斂速度.

(3)去除概率轉(zhuǎn)換函數(shù)的使用，引入相似度閾值F，通過對f(Oi)與閾值F比較，判斷螞蟻下一步的運(yùn)動狀態(tài)是移動還是靜止.這種處理方式簡單而且容易實現(xiàn)，可以避免概率轉(zhuǎn)換函數(shù)中因參數(shù)設(shè)置不準(zhǔn)確而對聚類的結(jié)果造成較大的影響.隨機(jī)移動會增加算法的處理時間，在這里使用一種局部最近鄰移動原則來改善螞蟻的移動.一只螞蟻Oi的局部最近鄰就是在其局部環(huán)境中，與該螞蟻最相似的螞蟻，用Ok表示，則它們之間的關(guān)系可以表示為:

螞蟻的移動具有方向性，使得它始終朝著信息素強(qiáng)度高的地方移動.由于閾值F直接影響螞蟻下一步的狀態(tài)，因此在實際運(yùn)算中，必須取合適的值.如果F過大，會導(dǎo)致螞蟻一直處于靜止?fàn)顟B(tài)，如果過小，又會導(dǎo)致螞蟻一直移動，找不到合適的位置休息.在這里采用一種自適應(yīng)調(diào)整閾值的方法.

螞蟻只有移動和靜止2種狀態(tài)，用m1表示移動狀態(tài)下螞蟻的數(shù)量，用m2表示靜止?fàn)顟B(tài)下螞蟻的數(shù)量.通過記錄前一次迭代時螞蟻的位置和再次迭代后螞蟻的位置的比較來判斷螞蟻是移動還是靜止.假設(shè)總的螞蟻數(shù)量為N=m1+m2，N也可以表示聚類模式的個數(shù)，如果處于移動狀態(tài)的螞蟻與處于靜止?fàn)顟B(tài)的螞蟻比例幾乎持平，表明閾值合適，如果m1比例比較大(大于總數(shù)的85%)，則閾值設(shè)置過小，應(yīng)該適當(dāng)加大，反之，如果m2比例比較大，則閾值設(shè)置過大，應(yīng)該適當(dāng)減小.在本文中，每迭代50次，統(tǒng)計移動了的螞蟻的數(shù)量值，而F的大小通過公式(9)進(jìn)行調(diào)整.

改進(jìn)后算法的具體步驟如下.

步驟1:初始化各個參數(shù)，包括最大循環(huán)次數(shù)T_MAX，螞蟻的個數(shù)N，鄰域半徑r，相似度閾值F等.

步驟2:對待聚類模式進(jìn)行主成分分析，然后對選取其中的兩個主成分進(jìn)行一定的處理并作為投影坐標(biāo)［11］.這兩個主成分必須保留模式的大部分信息，以便經(jīng)過投影后，相近的模式之間的距離較小而挨得比較近.投影完畢后將所有的螞蟻投影到2維網(wǎng)格上，并賦給每個螞蟻一個初始的坐標(biāo).

步驟3:循環(huán)以螞蟻Oi的此處坐標(biāo)為中心，r為半徑，按照公式(6)計算相似度的方式，計算該螞蟻在當(dāng)前所處的環(huán)境中的相似度.對比此時閾值F(t)與當(dāng)前相似度f的大小，如果F(t)大于或等于f，螞蟻靜止;否則，按公式(8)中表示的局部最近鄰原則，重新將螞蟻置為新的坐標(biāo)值.

步驟4:計算每50次迭代后計算m1和m2的值，然后再按照公式(9)調(diào)節(jié)相似度閾值F(t).再回到步驟3，直到達(dá)到最大迭代次數(shù)退出.

步驟5:根據(jù)所得的結(jié)果計算各類的聚類中心，輸出各聚類的模式.

4 在客戶細(xì)分中的應(yīng)用

客戶細(xì)分是指依照客戶的屬性進(jìn)行劃分的客戶集合，它不僅是客戶關(guān)系管理的重要理論組成部分，也是其重要管理工具之一［12］.它在管理客戶的分類、預(yù)測有價值的客戶、有效分配人力或物力以及成功執(zhí)行相關(guān)政策等基本原則中發(fā)揮著重要的作用，并使得企業(yè)能夠充分清晰地了解客戶，從客戶的需求出發(fā)，制定相應(yīng)的決策.總的來說，客戶細(xì)分就是指企業(yè)根據(jù)現(xiàn)有的發(fā)展方向和市場的定位與走勢，依據(jù)企業(yè)對客戶個人資料的分析，按照某種或某些屬性對客戶的種類進(jìn)行劃分，并提供個性化的商品和服務(wù)的過程［13］.

銀行客戶細(xì)分的原理是首先對現(xiàn)有的客戶信息收集和整理，然后依據(jù)客戶的屬性，按照某一條件對客戶進(jìn)行分類，最后銀行管理者針對不同類別的客戶制定不同的策略和服務(wù)，如圖1所示.

圖1 銀行客戶細(xì)分原理Fig.1 Theory of bank customer segmentation

本文所使用的數(shù)據(jù)來源于某銀行對客戶的數(shù)據(jù)記錄，該數(shù)據(jù)庫中存在大量個人存款及消費(fèi)記錄，每條記錄都代表了持卡人的基本資料，例如:客戶編號，姓名，年齡，證件號碼，手機(jī)，工作單位名稱，住址，月薪及存款等.對數(shù)據(jù)進(jìn)行預(yù)處理，刪除一些缺失或錯誤的信息，并從中抽取1000條記錄，去除與實驗無關(guān)的數(shù)據(jù)屬性，例如姓名，性別，證件號碼，手機(jī)號等屬性，只保留幾項重要屬性如年齡、工作年限、客戶月薪、存款及借貸情況，將1000條記錄分成5類，結(jié)果分配如表1所示.

表1 客戶類別分配Tab.1 Distribution of customer categories

K均值聚類算法是數(shù)據(jù)挖掘中一種比較健壯的算法，因其處理速度快，常被用于處理客戶細(xì)分，在此運(yùn)用K均值聚類算法對剛分配的數(shù)據(jù)集進(jìn)行識別，處理結(jié)果如表2所示.

表2 K均值聚類算法識別客戶類別Tab.2 Customer segmentation through K-means clustering algorithm

利用MATLABR2009a作為開發(fā)軟件，運(yùn)用改進(jìn)后的算法對數(shù)據(jù)集進(jìn)行識別，處理結(jié)果如表3所示.

表3 改進(jìn)算法識別客戶類別Tab.3 Customer segmentation through the improved clustering algorithm

統(tǒng)計K均值聚類算法與改進(jìn)算法對銀行客戶細(xì)分的處理時間和結(jié)果，可得到如表4所示的對比結(jié)果分析.

表4 兩種算法的對比結(jié)果Tab.4 Comparison of the results through two algorithms

從表4可以看出，使用K均值聚類算法對銀行客戶進(jìn)行細(xì)分時，時間要優(yōu)于改進(jìn)算法，通過對K均值聚類算法的原理進(jìn)行分析發(fā)現(xiàn)，發(fā)現(xiàn)它的處理時間短緣于它過早陷入了局部最優(yōu)，不能發(fā)現(xiàn)全局的最優(yōu)，通過各類客戶中數(shù)據(jù)的統(tǒng)計，改進(jìn)后的算法在正確率方面明顯優(yōu)于K均值聚類算法，表明該算法可以用于處理銀行客戶細(xì)分問題.

5 結(jié)束語

本文提出的改進(jìn)算法簡化了參數(shù)，避免了參數(shù)對聚類結(jié)果造成的影響，在聚類過程中，通過引入自適應(yīng)策略，動態(tài)調(diào)整螞蟻的狀態(tài)，減少螞蟻移動的隨機(jī)性，加快了聚類的過程.同時，螞蟻在移動過程中通過閾值調(diào)整相似度的大小，有效避免了陷入局部最優(yōu)，使得最終的聚類結(jié)果更理想.改進(jìn)后的算法在迭代次數(shù)和半徑的選擇上都要優(yōu)于標(biāo)準(zhǔn)蟻群聚類算法和自適應(yīng)蟻群聚類算法，在聚類的速度方面得到了較大的提升.實驗結(jié)果表明改進(jìn)后的算法在迭代次數(shù)上更少，算法的收斂速度更快，效率更高.將改進(jìn)后的算法用于客戶細(xì)分，實驗結(jié)果與K均值聚類算法對比分析發(fā)現(xiàn)，改進(jìn)后的算法識別客戶的正確率明顯高于K均值聚類算法.

［1］高 尚，楊靜宇.群智能算法及其應(yīng)用［M］.北京:中國水利水電出版社，2006.

［2］Dorigo M，Maniezzo V，Colorni A.The ant system:optimization by a colony of cooperation agents［J］.IEEE Transaction Systems，Man and Cybernetics，Part B，1996，26(1):29-41.

［3］Dorigo M，Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem［J］.IEEE Transactionson Evolutionary Computations，1997，1(1):53-66.

［4］宋中山，陳建國，鄭波盡.一種多項指標(biāo)全提升的多目標(biāo)優(yōu)化演化算法［J］.中南民族大學(xué)學(xué)報:自然科學(xué)版，2011，30(3):89-93.

［5］宋佩莉，祁 飛，張 鵬.混合蟻群蜂群算法在旅行Agent問題中的應(yīng)用［J］.計算機(jī)工程與應(yīng)用，2012，48(36):33-38.

［6］陳慶全，張棟楠，張永平.基于蟻群算法的動態(tài)人員疏散模擬［J］.微計算機(jī)信息，2012，28(10):424-426.

［7］周 騰，基于MATLAB的自適應(yīng)蟻群聚類算法研究與仿真［J］.軟件，2012，33(7):105-107.

［8］張春凱，王麗君.基于遺傳算法的一種改進(jìn)的K-均值聚類算法［J］.計算機(jī)工程與應(yīng)用，2012，48(26):144-147.

［9］Faieta B，Lumer E.Exploratory database analysis via selforganization［C］//RIAO.4th International Conference on Computer-Assisted Information Retrieval(RIAO 1994).NY:Rockefeller University，1994:570-584.

［10］Swee Chuan Tan，Kai Ming Ting，Shyh Wei Teng.Simplifying and improving ant-based clustering［C］//ICCS.Proceedings of the International Conference on Computational Science.Tsukuba:Elsevier，2011:46-55.

［11］張 蕾，曹其新，李 杰.一種基于群體智能聚類的設(shè)備性能橫向比較算法［J］.上海交通大學(xué)學(xué)報，2006，40(3):439-443.

［12］周晶平，宋中山.旅行社客戶關(guān)系OLAP系統(tǒng)的設(shè)計與實現(xiàn)［J］.中南民族大學(xué)學(xué)報:自然科學(xué)版，2012，31(4):101-104

［13］張建萍，劉希亞.基于聚類分析的K-means算法研究與應(yīng)用［J］.計算機(jī)應(yīng)用研究，2007，24(5):166-168.