啟發(fā)式搜索方法在關聯(lián)規(guī)則挖掘中的應用

啟發(fā)式搜索方法在關聯(lián)規(guī)則挖掘中的應用摘要:本文介紹了蟻群算法、遺傳算法、模擬退火算法等啟發(fā)式方法在關聯(lián)規(guī)則挖掘中的應用。【關鍵詞】關聯(lián)規(guī)則挖掘；蟻群算法；遺傳算法;模擬退火算法關聯(lián)規(guī)則關聯(lián)規(guī)則⑴是形如X=>Y的規(guī)則，其中X和Y是關于數(shù)據(jù)庫中屬性取值的斷言：由于某些事件的發(fā)生而引起另外一些事件的發(fā)生。設T是事務數(shù)據(jù)，即T={t,t,…，t},其中t(lWiWm)是每個事務的數(shù)據(jù)，這些數(shù)據(jù)稱為數(shù)據(jù)項。I是T中所有數(shù)據(jù)項(物品)的集合即I={i,i,…，i},(lWjWn)是T中的一個數(shù)據(jù)項。每個事務中含有I的一個子集。1關聯(lián)規(guī)則是j一種蘊含關系：X=>Y，其中XuI，YuI，且XGY=e。支持度(support)表示X=>Y在T事務數(shù)據(jù)中出現(xiàn)的普遍程度，稱關聯(lián)規(guī)則X=>Y在事務數(shù)據(jù)庫T中具有大小為s%的支持度，如果物品集X=>Y的支持度為s%；可信度(confidence)說明X=>Y成立的必然程度，稱規(guī)則X=>Y在事務數(shù)據(jù)庫T中具有大小為c%的可信度，如果T中支持物品集X的事務中有c%的事務同時也支持物品集Y；如果支持度和可信度都超過各自的閾值，則X=>Y可以看成是T中的一個有意義的關聯(lián)規(guī)則。蟻群算法蟻群算法基本原理現(xiàn)實生活中單個螞蟻的能力和智力非常簡單，但它們能通過相互協(xié)調(diào)、分工、合作來完成筑巢、覓食、遷徙、清掃蟻穴等復雜行為，尤其是螞蟻有能力在沒有任何可見提示的條件下找到從蟻穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化地搜索新的路徑，產(chǎn)生新的選擇。這是因為螞蟻在其走過的路上會分泌一種信息素，其他的螞蟻能夠感知這種物質(zhì)的存在和強度，并以此指導自己的運動方向，使其傾向于朝著信息素強度高的方向移動。蟻群算法就是從自然界中真實螞蟻覓食的群體行為中得到啟發(fā)而提出的。一個基本的蟻群算法［2］可以表述如下：初始時刻，各條路徑上的信息素量相等，設Tij(0)=C(C為常數(shù))，螞蟻k(k=l,2,3,…,m)在運動過程中根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向。螞蟻系統(tǒng)所使用的轉(zhuǎn)移規(guī)則被稱為隨機比例規(guī)則，在時刻t，螞蟻k從城市i選擇城市j的轉(zhuǎn)移概率pk(t)為：ij

pk(t)=ij?[pk(t)=ij?[\.(t)-工[t(t)]a-[n]卩’isissGJk(i)0,otherwise卩ifjGJk(i)(2.1)其中，Jk(i)={1,2,……,n}-tabuk表示螞蟻k下一步允許選擇的城市。列表tabuk記錄了螞蟻k在本次迭代中已經(jīng)走過的城市，不允許該螞蟻在本次循環(huán)中再經(jīng)過這些城市。當所有n座城市都加入到tabuk中時，螞蟻k便完成了一次周游，此時螞蟻k所走過的路徑便是TSP問題的一個可行解。(2.1)式中的nij是一個啟發(fā)式因子，被稱為能見度因子。在as算法中，nij通常取城市i與城市j之間距離的倒數(shù)。a和0分別反映了在螞蟻的運動過程中已積累的信息和啟發(fā)信息的相對重要程度。當所有螞蟻完成一次周游后，各路徑上的信息素根據(jù)(2.2)式更新。T0+n)=(1_p)*T(t)+At(2.2)ijijijAT=2"ATk(2.3)ijijk=1其中p(0<p<1)表示路徑上信息素的揮發(fā)系數(shù)，1-p表示信息素的持久系數(shù);△ij表示本次迭代邊(^)上信息素的增量。△Tkij表示第k只螞蟻在本次迭代中留在邊(ij)上的信息素量。△tk..表示為：ij「QAtk=<L代中留在邊(ij)上的信息素量。△tk..表示為：ij「QAtk=<LijK0,若螞蟻在本次周游中經(jīng)過邊ij(2.4)否則其中，Q為正常數(shù)，Lk表示第k只螞蟻在本次周游中所走過路徑的長度。蟻群算法在關聯(lián)規(guī)則中應用基于螞蟻尋路的特點和關聯(lián)規(guī)則中規(guī)則前件和后件的組織結(jié)構，首先對數(shù)據(jù)庫中的數(shù)據(jù)進行預處理，就是將連續(xù)的屬性離散化掉，形成一個一個屬性值的分區(qū)。以I中的每一個屬性作為超頂點，以該屬性值的每一個分區(qū)作為超頂點的子頂點，來構建一個無向完全圖，每對超頂點間根據(jù)子頂點的數(shù)目可以構成多條路徑供螞蟻選擇。然后將m只螞蟻分為m/2對，搜索過程由每對螞蟻合作完成，其中一只螞蟻在無向圖上搜索規(guī)則前件，該對螞蟻中的另一只在剩余的超頂點中尋找規(guī)則后件。當每對螞蟻中一只搜索頻繁項集合I]時，對應的螞蟻則在剩余的超頂點上搜索頻繁項集合12。根據(jù)規(guī)則的支持度和可信度，決定規(guī)則I]=>I2和I2=>I1的取舍。逐步固定頻繁項集中數(shù)據(jù)項的個數(shù)，因此算法只需循環(huán)a/2次⑶。螞蟻k在超頂點i上的第p子頂點位置根據(jù)如下公式選擇概率地下一個需訪問的超頂點j的第q子頂點。t(鳳(VXt(鳳(VXtad(vftiiLj€(?/hrcd#1()odicitviso1()在得到一條規(guī)則后,根據(jù)其質(zhì)量,即規(guī)則的支持度和可信度來更新所選擇路徑上的信息素,更新公式如下:環(huán)"+］Q仆一"玉溝”丿+—^玉用())伽切1叫J血虹\^(t)ollicnvise其中，Ti.表示超頂點i內(nèi)的子頂點p到超頂點j內(nèi)的子頂點q邊上的信息素。S為構造的規(guī)則的支持度,C為可信度。初始化時我們?nèi)..(0)=n..,在算法執(zhí)行中當越來越多的螞蟻選擇超頂點j的子頂點p時，說明規(guī)則構造中該子頂點的頻繁度較高，因此，需加大通往該頂點的所有邊上的信息素,給后來螞蟻提供正反饋信息。n作為啟發(fā)式因子，應該是一不變的量。螞蟻在選擇子頂點的時候，除了信息素提供參考信息之外,還要考慮到termip,termjq是否可以覆蓋一定量的事例，所以要考慮這兩個子頂點在數(shù)據(jù)庫中的支持度。nip,jq=Sup(termip，term.)，由超頂點和子頂點所構成的圖是無向圖，所以邊是無向邊，是對稱的。本算法通過一次掃描得到啟發(fā)式公式的值，然后采用m/2對螞蟻對分別搜索互補的頻繁項集I】和12,分別作為規(guī)則的前件或后件，可以看成并行操作，理論上一次操作可以得到兩條規(guī)則，大大加快了規(guī)則的挖掘效率。由于每只螞蟻只需在a/2(a為屬性的個數(shù))個屬性上搜索，當屬性數(shù)量較多時也可以顯著加快算法執(zhí)行的實際時間。遺傳算法3.1遺傳算法基本原理遺傳算法(GA)是模擬生物遺傳和進化過程建立起來的一種隨機搜索和優(yōu)化算法.遺傳算法的工作過程是將問題的可行解表示成"染色體"，由隨機方法產(chǎn)生的一群"染色體"組成的初始群體，通過適應度構成優(yōu)勝劣汰、適者生存的"自然環(huán)境"，種群通過復制、交換、突變等不斷演化，產(chǎn)生出新的更加優(yōu)良的種群.這樣經(jīng)過若干代的進化，最終得到適合問題的最優(yōu)解［1］。遺傳算法的工作過程如下：

遺傳算法在數(shù)據(jù)挖掘中的應用1）遺傳算法的編碼方法編碼問題中,字符串代表染色體,它是遺傳信息傳遞的載體,串上的每個位置的元素代表遺傳因子.采用實數(shù)數(shù)組的方法進行編碼,實數(shù)數(shù)組的元素個數(shù)與事務數(shù)據(jù)庫中的字段的個數(shù)相對應,元素值代表了字段的屬性值,如下：表1數(shù)據(jù)庫中的字段字段1字段2…字段R-1字段R屬性1屬性1…屬性■屬性1屬性I屬性J…屬性陋屬性N用一個長度為N的數(shù)組來表示表1中的事務數(shù)據(jù)庫的個體編碼,A[1]表示字段1,A[2]表示字段2,…，A[R]表字段R;例如：用數(shù)值i表示屬性值i,就可以用數(shù)組A[R]的元素值來表示相對應的字段的屬性值。另外再用0值表示此屬性與其它的屬性無關聯(lián)。表1所示的數(shù)據(jù)庫的個體編碼如下所示：A[l]A[2]…A[R-1]A[R]進行了這樣的編碼后,交叉、變異等的操作就變成了對數(shù)組的操作。適應度函數(shù)的構造適應度函數(shù)的設計應該綜合考慮，定義適應度為fit(X=>Y)=S(X=>Y)+C(X=>Y),它反映了綜合結(jié)果.在各種規(guī)則的競爭中,只有支持度和可信度都高才有可能生存下來.由于支持度和可信度都是百分比，因此0<fitXnY)<2采用雙層循環(huán)結(jié)構存儲數(shù)，見表2。表2雙層存儲表DATAC編碼Fit(2打適應度值DATA1C編碼F)適應度值DATA2C編碼Fit(2打適應度值表2中的DATA代表用來存儲所有計算完成的數(shù)據(jù)。DATA1代表從DATA中根據(jù)適應度值大小過濾出來80%的一般個體，DATA2代表從DATA中過濾出來的20%優(yōu)良個體。將優(yōu)秀的個體放到DATA2中，而大量普通個體放到DATA1中。對DATA2中的個體通過遺傳算子的作用產(chǎn)生后代，然后把DATA2中最差的個體同DATA1中最好的個體比較，再將其中優(yōu)秀的個體放到DA!TA2中，這樣通過競爭機制來保證進化，具有較好的全局和局部搜索能力。遺傳算子的改進精英重組算法將選擇和交換整合在一起，算法過程如下:首先初始化種群，然后對于每一代隨機打亂種群，將交叉操作用于所有的配偶對，在家庭范圍內(nèi)比較父本與子本的適應度值，選擇最好的兩個個體進入下一代。由于精英的選擇是在家庭范圍內(nèi)進行的，所以這樣做既可以保證收斂速度又避免了早熟現(xiàn)象。變異算法采用一致變異算法，對于每個個體，根據(jù)變異率Pm來決定是否進行變異。對需要進行變異的個體，隨機產(chǎn)生一個與個體編碼串長度等長的二進制屏蔽字，根據(jù)屏蔽字位來決定父代個體編碼串相應基因進行變異操作，為0時不進行變異操作。這種方法既避免了普通突變算法的單調(diào)和不精確，而且方法實現(xiàn)比較簡單。變異概率P是一個重要參數(shù)，利用自適應方法來確定它，這樣可以避免優(yōu)良基因結(jié)構被破壞或發(fā)生近親雜交而使進化過程過早收斂或降低收斂速度。當群體最大適應度值與平均適應度接近時則群體趨于收斂，應增大Pm;反之，則群體多樣性較強，應減少Pm。規(guī)則的提取根據(jù)適應度函數(shù)和遺傳算子選擇出的規(guī)則表示的是所有具有關聯(lián)性的屬性。在每個子種群中，為了最后找到符合要求的關聯(lián)規(guī)則，我們利用事先設定的可信度和支持度來提取規(guī)則。提取的標準是:滿足用戶給定的可信度要求的規(guī)則就輸出,否則舍去。模擬退火遺傳算法4.1模擬退火算法基本原理模擬退火算法的基本思想:通過模擬高溫物體退火過程的方法,來找到優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解。從統(tǒng)計物理學的觀點看,隨著溫度的降低,物質(zhì)的能量將逐漸趨近于一個較低的狀態(tài),并最終達到某種平衡。模擬退火遺傳算法[4的]基本思想:將遺傳算法與模擬退火算法相結(jié)合構成一種混合優(yōu)化算法。遺傳算法的局部搜索能力較差,但把握搜索過程總體的能力較強;而模擬退火算法具有較強的局部搜索能力,并能使搜索過程避免陷入局部最優(yōu)解,但它卻對整個搜索空間的了解不多,不便于使搜索過程進入最有希望的搜索區(qū)域,從而使得模擬退火算法的運算效率不高。但如果將遺傳算法和模擬退火算法相結(jié)合,互相取長補短,則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法。結(jié)合遺傳算法對模擬退火算法做以下改進:采用動態(tài)調(diào)節(jié)近鄰子集的方法,利用以下公式確定近鄰子集的容量M的大小:X（f-f）。式中，fmaxavgmax為最大適應度值，f為平均適應度值，入為系數(shù)。這樣在算法前期，f與favgmaxavg相差較大，所以此時取近鄰子集的容量較大，在算法后期，favg與fmax的差別越avgmax來越小，近鄰子集的容量也隨之變小。通過動態(tài)的調(diào)節(jié)近鄰子集的大小，可以使搜索在更有效的范圍內(nèi)進行，提高算法的運行效率。改進的模擬退火遺傳算法工作流程如下圖所示。模擬退火算法在數(shù)據(jù)挖掘中的應用1）遺傳算法的編碼方法編碼方式和3.2遺傳算法的編碼方式相同。2）適應度函數(shù)的構造對適應度函數(shù)做了改進，按照如下公式計算。f^essU）=WS次沁@+化沃運包-S"陽血5猛其中，W+Wc=l,Ws鼻O,Wc鼻O,SupPmm是支持度的閾值,Confmm是可信度的閾值。3）遺傳算子的選擇交叉運算是指對兩個相互配對的染色體按某種方式相互交換部分基因,從而形成兩個新的個體。變異模擬了生物進化過程中的基因突變現(xiàn)象,變異算子是以一定的概率改變遺傳基因的操作。。為了避免早熟現(xiàn)象,采用自適應方法動態(tài)調(diào)節(jié)交叉概率和變異概率,使得交叉概率Pc、變異概率Pm能夠隨適應度自動改變。當種群各個體適應度趨于一致或者趨于局部最優(yōu)時，使Pc和Pm增加，而當群體適應度比較分散時，使P和P減少。其中交叉概率P:mcmc式中Pc1=0.9,Pc2=0.6,f為要交叉的兩個個體中較大的適應度值。選取的變異概率Pm：式中Pm1=0.1,Pm2=0.001,f為要變異個體的適應度值。（4）個體模擬退火運算用適應度作為模擬退火遺傳算法中的能量,對算法中的近鄰子集采用動態(tài)調(diào)節(jié)的方式選取:M二久X（f-f）。當適應度值增加時，接受該解作為下一個maxavg當前解，否則，當前解，否則，以一定的概率p=exp(-Afitness/T)接受該解，即Z-1Z-1<￡其中f.+i為子個體的適應度值，fi為父個體的適應度值，溫度T由隨著算法進程遞減其值的控制參數(shù)擔當。5)選擇操作在群體中選取優(yōu)勝的個體，淘汰劣質(zhì)的個體的操作稱作選擇。根據(jù)染色體適應度值的大小選擇適應性更強的染色體生成新的種群。因此適應度值越大，被選中的概率就越大。若經(jīng)過若干代運算后，仍沒有滿足用戶給定閾值的規(guī)則，則結(jié)束，輸出結(jié)果。總結(jié)將關聯(lián)規(guī)則挖掘與現(xiàn)在的各種啟發(fā)式搜索方法相結(jié)合，可以更快的挖掘出感興趣的信息。傳統(tǒng)的數(shù)據(jù)挖掘算法具有完備性的特點，雖然可能需要多次掃描數(shù)據(jù)庫但是可以把滿足最小支持度和最小置信度的關聯(lián)規(guī)則都給挖掘出來。這些啟發(fā)式方法都有著各自的缺點，例如蟻群算法易于早熟，遺傳算法和模擬退火易于陷入局部最優(yōu)等，所以他們在完備性方面不及傳