啟發式搜索方法在關聯規則挖掘中的應用摘要:本文介紹了蟻群算法、遺傳算法、模擬退火算法等啟發式方法在關聯規則挖掘中的應用。【關鍵詞】關聯規則挖掘；蟻群算法；遺傳算法;模擬退火算法關聯規則關聯規則⑴是形如X=>Y的規則，其中X和Y是關于數據庫中屬性取值的斷言：由于某些事件的發生而引起另外一些事件的發生。設T是事務數據，即T={t,t,…，t},其中t(lWiWm)是每個事務的數據，這些數據稱為數據項。I是T中所有數據項(物品)的集合即I={i,i,…，i},(lWjWn)是T中的一個數據項。每個事務中含有I的一個子集。1關聯規則是j一種蘊含關系：X=>Y，其中XuI，YuI，且XGY=e。支持度(support)表示X=>Y在T事務數據中出現的普遍程度，稱關聯規則X=>Y在事務數據庫T中具有大小為s%的支持度，如果物品集X=>Y的支持度為s%；可信度(confidence)說明X=>Y成立的必然程度，稱規則X=>Y在事務數據庫T中具有大小為c%的可信度，如果T中支持物品集X的事務中有c%的事務同時也支持物品集Y；如果支持度和可信度都超過各自的閾值，則X=>Y可以看成是T中的一個有意義的關聯規則。蟻群算法蟻群算法基本原理現實生活中單個螞蟻的能力和智力非常簡單，但它們能通過相互協調、分工、合作來完成筑巢、覓食、遷徙、清掃蟻穴等復雜行為，尤其是螞蟻有能力在沒有任何可見提示的條件下找到從蟻穴到食物源的最短路徑，并且能隨環境的變化而變化地搜索新的路徑，產生新的選擇。這是因為螞蟻在其走過的路上會分泌一種信息素，其他的螞蟻能夠感知這種物質的存在和強度，并以此指導自己的運動方向，使其傾向于朝著信息素強度高的方向移動。蟻群算法就是從自然界中真實螞蟻覓食的群體行為中得到啟發而提出的。一個基本的蟻群算法［2］可以表述如下：初始時刻，各條路徑上的信息素量相等，設Tij(0)=C(C為常數)，螞蟻k(k=l,2,3,…,m)在運動過程中根據各條路徑上的信息量決定轉移方向。螞蟻系統所使用的轉移規則被稱為隨機比例規則，在時刻t，螞蟻k從城市i選擇城市j的轉移概率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在本次迭代中已經走過的城市，不允許該螞蟻在本次循環中再經過這些城市。當所有n座城市都加入到tabuk中時，螞蟻k便完成了一次周游，此時螞蟻k所走過的路徑便是TSP問題的一個可行解。(2.1)式中的nij是一個啟發式因子，被稱為能見度因子。在as算法中，nij通常取城市i與城市j之間距離的倒數。a和0分別反映了在螞蟻的運動過程中已積累的信息和啟發信息的相對重要程度。當所有螞蟻完成一次周游后，各路徑上的信息素根據(2.2)式更新。T0+n)=(1_p)*T(t)+At(2.2)ijijijAT=2"ATk(2.3)ijijk=1其中p(0<p<1)表示路徑上信息素的揮發系數，1-p表示信息素的持久系數;△ij表示本次迭代邊(^)上信息素的增量。△Tkij表示第k只螞蟻在本次迭代中留在邊(ij)上的信息素量。△tk..表示為：ij「QAtk=<L代中留在邊(ij)上的信息素量。△tk..表示為：ij「QAtk=<LijK0,若螞蟻在本次周游中經過邊ij(2.4)否則其中，Q為正常數，Lk表示第k只螞蟻在本次周游中所走過路徑的長度。蟻群算法在關聯規則中應用基于螞蟻尋路的特點和關聯規則中規則前件和后件的組織結構，首先對數據庫中的數據進行預處理，就是將連續的屬性離散化掉，形成一個一個屬性值的分區。以I中的每一個屬性作為超頂點，以該屬性值的每一個分區作為超頂點的子頂點，來構建一個無向完全圖，每對超頂點間根據子頂點的數目可以構成多條路徑供螞蟻選擇。然后將m只螞蟻分為m/2對，搜索過程由每對螞蟻合作完成，其中一只螞蟻在無向圖上搜索規則前件，該對螞蟻中的另一只在剩余的超頂點中尋找規則后件。當每對螞蟻中一只搜索頻繁項集合I]時，對應的螞蟻則在剩余的超頂點上搜索頻繁項集合12。根據規則的支持度和可信度，決定規則I]=>I2和I2=>I1的取舍。逐步固定頻繁項集中數據項的個數，因此算法只需循環a/2次⑶。螞蟻k在超頂點i上的第p子頂點位置根據如下公式選擇概率地下一個需訪問的超頂點j的第q子頂點。t(鳳(VXt(鳳(VXtad(vftiiLj€(?/hrcd#1()odicitviso1()在得到一條規則后,根據其質量,即規則的支持度和可信度來更新所選擇路徑上的信息素,更新公式如下:環"+］Q仆一"玉溝”丿+—^玉用())伽切1叫J血虹\^(t)ollicnvise其中，Ti.表示超頂點i內的子頂點p到超頂點j內的子頂點q邊上的信息素。S為構造的規則的支持度,C為可信度。初始化時我們取T..(0)=n..,在算法執行中當越來越多的螞蟻選擇超頂點j的子頂點p時，說明規則構造中該子頂點的頻繁度較高，因此，需加大通往該頂點的所有邊上的信息素,給后來螞蟻提供正反饋信息。n作為啟發式因子，應該是一不變的量。螞蟻在選擇子頂點的時候，除了信息素提供參考信息之外,還要考慮到termip,termjq是否可以覆蓋一定量的事例，所以要考慮這兩個子頂點在數據庫中的支持度。nip,jq=Sup(termip，term.)，由超頂點和子頂點所構成的圖是無向圖，所以邊是無向邊，是對稱的。本算法通過一次掃描得到啟發式公式的值，然后采用m/2對螞蟻對分別搜索互補的頻繁項集I】和12,分別作為規則的前件或后件，可以看成并行操作，理論上一次操作可以得到兩條規則，大大加快了規則的挖掘效率。由于每只螞蟻只需在a/2(a為屬性的個數)個屬性上搜索，當屬性數量較多時也可以顯著加快算法執行的實際時間。遺傳算法3.1遺傳算法基本原理遺傳算法(GA)是模擬生物遺傳和進化過程建立起來的一種隨機搜索和優化算法.遺傳算法的工作過程是將問題的可行解表示成"染色體"，由隨機方法產生的一群"染色體"組成的初始群體，通過適應度構成優勝劣汰、適者生存的"自然環境"，種群通過復制、交換、突變等不斷演化，產生出新的更加優良的種群.這樣經過若干代的進化，最終得到適合問題的最優解［1］。遺傳算法的工作過程如下：

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