一種利用蟻群系統(tǒng)提取隸屬度函數(shù)的方法

張春艷，徐開軍，王書旺

ZHANG Chun-yan，XU Kai-jun，WANG Shu-wang

(南京信息職業(yè)技術(shù)學(xué)院，南京 210023)

0 引言

近年來，模糊集理論由于其擬人推理功能，已越來越多地應(yīng)用于智能系統(tǒng)的設(shè)計中。在數(shù)據(jù)挖掘中應(yīng)用模糊集，有助于將量值轉(zhuǎn)變成語言值，從而減少挖掘過程可能的項集。在模糊數(shù)據(jù)挖掘中，隸屬度函數(shù)的確定對最終的挖掘結(jié)果有很重要的影響。

基本蟻群算法（Ant System A1gorithms）是由Co1orni等人于1992年提[1]，并且擴(kuò)展到蟻群系統(tǒng)（Ant Co1ony System，ACS）算法[2]。目前，ACS已經(jīng)很成功地應(yīng)用于一些較難問題，例如旅行商問題（TSP）、工作時間表問題（JSP）、車輛路線問題（VRP）、二次分配問題（QAP）等，它們是來自于群居昆蟲行為的啟發(fā)式方法[3～8]。螞蟻為了跟另外的螞蟻交流在地面上存儲它們的化學(xué)蹤跡及“信息素”，根據(jù)信息素，蟻群能找到起點(diǎn)和目標(biāo)之間的最短路徑。

本文提出了一種基于模糊數(shù)據(jù)挖掘及ACS算法的方法，從量化數(shù)據(jù)中提取隸屬度函數(shù)，并通過數(shù)值實驗來驗證該算法的有效性。

1 基于ACS的模糊挖掘

基于ACS的模糊挖掘分為兩個階段，第一階段通過ACS算法給所有的項尋找隸屬度函數(shù)的適當(dāng)集，第二階段利用第一階段中尋找到的最優(yōu)的隸屬度函數(shù)集從數(shù)據(jù)庫中進(jìn)行模糊數(shù)據(jù)挖掘，得到模糊關(guān)聯(lián)規(guī)則。ACS算法在第一階段的提取隸屬函數(shù)中起著重要作用[9]。

在這里，假設(shè)隸屬度函數(shù)的參數(shù)是離散的，并嘗試用ACS算法去尋找最優(yōu)的隸屬度函數(shù)集，從而把隸屬度函數(shù)的提取轉(zhuǎn)變成一個路徑搜索問題。一條路徑就代表一個可能的隸屬度函數(shù)集，用人工螞蟻去尋找一個近似的優(yōu)化方案。

2 ACS及其在模糊數(shù)據(jù)挖掘中的應(yīng)用

2.1 編碼方案

編碼方案即是用一組編碼來描述所有項的隸屬度函數(shù)，每項的隸屬度函數(shù)采用二進(jìn)制編碼。不是一般性，假設(shè)每項的隸屬度函數(shù)集是等腰三角形，這樣，每個隸屬度函數(shù)有兩個參數(shù)：中心與跨距。隸屬度函數(shù)代表語言值，如低、中、高。首先，根據(jù)數(shù)據(jù)庫中項的數(shù)值范圍用n位二進(jìn)制數(shù)去編碼每項的隸屬度函數(shù)的中心和跨度。例如，項的數(shù)值范圍是0-15，可以用4位二進(jìn)制數(shù)編碼。

下面，舉例來說明該編碼方案。假設(shè)項Ij的有三個語言值（即隸屬度函數(shù)），Cj1、Cj2、Cj3分別代表語言值的三個中心，Sj1、Sj2、Sj3分別代表三個跨度。若假設(shè)中心和跨度都用4位二進(jìn)制數(shù)編碼，例如，三個中心編碼為{(0,0,1,1)(0,1,1,1)(1,1,0,1)}，三個跨度編碼為{(0,0,1,1)(0,1,1,0)(0,1,1,1)}，如表1所示。則項Ij的隸屬度函數(shù)對應(yīng)的三個中心為{3,7,13}，三個跨度為{3,6,7}，如圖1所示。這里，跨度是有約束條件的，如果跨度擴(kuò)展到相鄰區(qū)域，它的值應(yīng)減小到相鄰區(qū)域的邊界[5,6]。

表1 三個中心和三個跨度及其編碼

圖1 項Ij的隸屬度函數(shù)

隸屬度函數(shù)被編碼后，應(yīng)用ACS算法找到最理想的解決方法，每組編碼包含兩位，一位是中心，一位是跨度，所以有四種情形，即（0,0），（0,1），（1,0），（1,1），如果把每一位看作一個節(jié)點(diǎn)，這就是一個多階段決策問題，雖然能通過動態(tài)編程技術(shù)解決，但這仍然是一個非確定性多項式（non-deterministic po1ynomia1，NP）難題，因此，這里用ACS算法來解決。例如旅行商問題（trave1 sa1esman prob1em，TSP），在每一條路徑的每一個節(jié)點(diǎn)，蟻群可以選擇四條路徑中的一個。因此，上面的例子，有十二個節(jié)點(diǎn)，分別為，每個節(jié)點(diǎn)有四種選擇，如圖2所示。每個節(jié)點(diǎn)由兩位編碼(Cj,Sj)組成，以表1所示為例，四個節(jié)點(diǎn)(0,0)、(0,0)、(1,1)、(1,1)為第一個隸屬度函數(shù)的一條路徑，當(dāng)一只螞蟻完成了共12個節(jié)點(diǎn)的路徑，隸屬度函數(shù)的可能集就產(chǎn)生了。蟻群系統(tǒng)重復(fù)這個過程，直到滿足最終的條件，此時得到的就是隸屬度函數(shù)最優(yōu)集（信息素最多），也就是模糊數(shù)據(jù)挖掘的輸出。

圖2 蟻群系統(tǒng)挖掘算法多級路徑圖

2.2 信息素初始化

每條路徑存放的信息素初始數(shù)量是0.5，每只螞蟻有它自己的信息素，當(dāng)一只螞蟻經(jīng)過時，就會在兩個節(jié)點(diǎn)間路徑上存放信息素。

2.3 狀態(tài)轉(zhuǎn)移規(guī)則

這里，每只螞蟻選擇的下一個節(jié)點(diǎn)是通過計算概率決定的，每只螞蟻在下一階段由節(jié)點(diǎn)j到節(jié)點(diǎn)n的狀態(tài)轉(zhuǎn)移規(guī)則如下：

這里q是[0,1]之間的一個隨機(jī)變量， q0（0≤q0≤1）是預(yù)先定義的一個參數(shù)，當(dāng)q的值比預(yù)先定義的值大時，每一個可能的下一節(jié)點(diǎn)的轉(zhuǎn)換概率由由下式計算：

這里tjn(t)是t時刻，節(jié)點(diǎn)j到節(jié)點(diǎn)n路徑上的當(dāng)前信息素，節(jié)點(diǎn)m與節(jié)點(diǎn)n在同一階段，hjn和hjm為啟發(fā)因子，表示螞蟻從節(jié)點(diǎn)j轉(zhuǎn)移到節(jié)點(diǎn)n（m）的期望程度。此處假設(shè)所有的啟發(fā)因子都相同。

2.4 信息素更新規(guī)則

蟻群系統(tǒng)與螞蟻系統(tǒng)之間的不同之一是信息素的更新規(guī)則。本文提出的方法中，人工螞蟻有兩種更新規(guī)則去尋找最優(yōu)的解決方案，一種是局部更新規(guī)則，另一種是全局更新規(guī)則。

1）局部更新規(guī)則

局部更新規(guī)則可防止螞蟻尋找路徑時落入局部優(yōu)化，在螞蟻構(gòu)建路徑時，能夠適當(dāng)?shù)卣{(diào)整信息素，局部更新規(guī)則如下：

這里r是信息素殘留因子，(1?r)是信息素?fù)]發(fā)因子，t0是信息素初始值。

2）全局更新規(guī)則

全局更新規(guī)則可使最優(yōu)路徑能夠進(jìn)一步利用，當(dāng)所有的螞蟻都完成了一次周游后，最優(yōu)路徑上的信息素增加，其他路徑的信息素減少，全局更新規(guī)則如下：

這里a是信息素蒸發(fā)系數(shù)，LIBest為最優(yōu)路徑的長度，也稱最優(yōu)迭代。

3 基于ACS的模糊數(shù)據(jù)挖掘算法

這部分提出一種基于ACS的模糊數(shù)據(jù)挖掘算法來提取隸屬度函數(shù)與模糊關(guān)聯(lián)規(guī)則。

3.1 種群的初始化

如前文所述，每個項有一組等腰三角形隸屬度函數(shù)，即三個語言值。將量值轉(zhuǎn)換成語言值需要一個可行的種群數(shù)據(jù)庫，因此，需要在進(jìn)化過程中對種群進(jìn)行初始化與更新。

3.2 適應(yīng)度函數(shù)

這里采用Hong等人[10]提出的適應(yīng)度函數(shù)來得到隸屬度函數(shù)的適當(dāng)集，描述如下：

圖3 兩種較差的隸屬度函數(shù)

隸屬度函數(shù)的適應(yīng)性包括重疊性和覆蓋性兩個方面，重疊因子是避免第一種情況發(fā)生，覆蓋因子是避免第二種情況發(fā)生。因此，Ij項的適應(yīng)性可描述為重疊因子與覆蓋因子之和。

3.3 算法描述

除了前面部分定義的參數(shù)外，還用到以下參數(shù)：人工螞蟻的數(shù)量、一只螞蟻的最小信息素率，信息素蒸發(fā)率、局部更新率及全局更新率，基于ACS挖掘隸屬度函數(shù)與模糊關(guān)聯(lián)規(guī)則的算法描述如下。

輸入如下數(shù)據(jù)信息：

1）n個量化事務(wù)數(shù)據(jù)；

2）m個項集，每個項集具有l(wèi)個預(yù)先定義的語言變量；

3）支持度閾值a；

4）置信度閾值l；

5）最大迭代值G。

輸出模糊數(shù)據(jù)挖掘中所有項的隸屬度函數(shù)的適當(dāng)集。具體步驟如下：

1）設(shè)p=1，這里p用于保持被處理項的數(shù)量恒定；

2）模糊挖掘問題的多級路徑如圖4所示，這里N是節(jié)點(diǎn)集，E是路徑集，第i階段的j節(jié)點(diǎn)表示為Nij，從節(jié)點(diǎn)Nij到節(jié)點(diǎn) N(i+1)k的路徑表示為Eijk，每條路徑信息素的初始值設(shè)為0.5；

3）設(shè)初始種群數(shù)g=1；

4）根據(jù)下列步驟為每只人工螞蟻Antq設(shè)立完整的路徑：1）根據(jù)狀態(tài)交易規(guī)則從開始到結(jié)束選擇路徑，2）根據(jù)局部更新規(guī)則，更新Antq經(jīng)過的路徑的信息素；

5）根據(jù)式（6）估算由每只人工螞蟻得到的隸屬度函數(shù)的適當(dāng)值；

6）一旦所有的智能螞蟻找到完整的路線，適當(dāng)值最高的螞蟻將會根據(jù)全局更新規(guī)則更新信息素；

7）當(dāng)g=G時，輸出該時刻Ip項的隸屬度函數(shù)的最優(yōu)值，否則 g=g+1 ，并轉(zhuǎn)到第（4）步；

8）如果p≠m，則 p=p+ 1，并轉(zhuǎn)到第 2）步，否則結(jié)束算法。

最終的模糊隸屬度函數(shù)集在第7）步輸出，并且將得到的項集用于從給定的數(shù)據(jù)庫中挖掘模糊關(guān)聯(lián)規(guī)則。

圖4 模糊挖掘問題的多級路徑圖

4 數(shù)值實驗

這里通過一個數(shù)值實驗來證明所提方法的有效性。實驗中共有64個項、10000個數(shù)據(jù)，蟻群的初始大小設(shè)為10，支持度閾值設(shè)為0.04，ACS算法的參數(shù)設(shè)置如下：信息素初始比為0.05，蟻群的最小信息素是0.2，揮發(fā)率是0.9，局部更新率是0.1，全局更新率是0.9，不同蟻群代對應(yīng)的人工螞蟻的平均適應(yīng)度值如圖5所示。從圖5可以看出，隨著蟻群代的增加平均適應(yīng)度值也逐漸增加，在1000代之后基本保持穩(wěn)定。圖6是不同蟻群代對應(yīng)的大于1的項集數(shù)量。

圖5 不同蟻群代對應(yīng)的平均適應(yīng)度值

圖6 不同蟻群代對應(yīng)的大于1的項集數(shù)量

5 結(jié)束語

本文針對利用模糊數(shù)據(jù)挖掘和ACS算法提取隸屬函數(shù)的問題進(jìn)行了研究，并提出了一種算法來實現(xiàn)。最后給出了一個數(shù)值實驗，以證明該算法的有效性。結(jié)果表明，該方法在隸屬度函數(shù)提取上能取得良好的效果。但是，仍然需要提高該方法的執(zhí)行效率，用更少的時間來完成計算。未來需要做更多的工作來優(yōu)化該方法，例如，可進(jìn)一步研究設(shè)計啟發(fā)式功能狀態(tài)轉(zhuǎn)移規(guī)則和定義不同的適應(yīng)度函數(shù)值。

[1] Co1orni,M Dorigo and V Maniezzo,DistributedOptimization by Ant Co1onies[C].The First European Conference on Artificia1 Life,1991∶134-142.

[2] M Dorigo,V Maniezzo and A Co1orni,Ant System∶Optimization by a Co1ony of Cooperating Agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1)∶29-41.

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

[4] 勞眷,林亞平,伍超奎.蟻群系統(tǒng)求解TSP問題的性能分析[J].計算機(jī)應(yīng)用與軟件,2009,(2)∶270-271.

[5] 徐開軍,張春艷,張磊,等.蟻群優(yōu)化算法在FPID參數(shù)調(diào)節(jié)中的應(yīng)用研究[J].計算機(jī)測量與控制,2013,21(5)∶1278-1280.

[6] M Kaya,R A1hajj,Genetic A1gorithm Based Framework for Mining Fuzzy Association Ru1es[J].Fuzzy Sets and Systems,2005,152∶587-601.

[7] R J Kuo,C Y Chiu,Y J Lin,Integration of Fuzzy Theory and Ant A1gorithm for Vehic1e Routing Prob1em with Time Window[J].IEEE Fuzzy Information,2004,2∶925-930.

[8] A Wade and S Sha1hi,An ant System A1gorithm for the Mixed Vehic1e Routing Prob1em with Backhau1s[C].in Metaheuristics∶ Computer Decision-Making,Norwe11,MA∶K1uwer,2004∶699-719.

[9] R S Parpine11i,H S Lopes,A A Freitas,An Ant Co1ony Based System for Data Mining∶App1ication to Medica1 Data[C].The Genetic and Evo1utionary Computation Conference,2001∶791-798.

[10] T P Hong,C H Chen,Y L Wu et a1,A GA-based Fuzzy Mining Approach to Achieve a Trade-off between Number of Ru1es and Suitabi1ity of Membership functions[J].Soft Computing-A Fusion of Foundations,Methodo1ogies and App1ications,2006∶1091-1101.