基于改進(jìn)遺傳算法與Apriori算法的岸橋機(jī)械關(guān)聯(lián)規(guī)則挖掘

潘海洋　薛超飛

（上海海事大學(xué) 物流工程學(xué)院，上海 201306）

基于改進(jìn)遺傳算法與Apriori算法的岸橋機(jī)械關(guān)聯(lián)規(guī)則挖掘

潘海洋薛超飛

（上海海事大學(xué) 物流工程學(xué)院，上海 201306）

基于對(duì)傳統(tǒng)遺傳算法的關(guān)聯(lián)規(guī)則挖掘，提出了改進(jìn)型遺傳算法。該算法提出了一種自適應(yīng)變異率方法，并改進(jìn)了個(gè)體選擇方法。最后，將其應(yīng)用到岸橋機(jī)械數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘中進(jìn)行實(shí)驗(yàn)，并用Apriori算法驗(yàn)證了該方法的高效性和可靠性。

遺傳算法 Apriori算法 岸橋機(jī)械 關(guān)聯(lián)規(guī)則

引言

隨著信息時(shí)代的到來(lái)，各行各業(yè)大量的數(shù)據(jù)積累形成了大數(shù)據(jù)的倉(cāng)庫(kù)。所以，急需智能地把這些數(shù)據(jù)信息轉(zhuǎn)換成有用參考信息的技術(shù)，輔助決策層進(jìn)行決策。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要內(nèi)容，但傳統(tǒng)的遺傳算法存在一定的缺陷，容易導(dǎo)致算法過(guò)早收斂而陷于局部最優(yōu)困境，或收斂時(shí)間過(guò)長(zhǎng)而消耗大量的搜索時(shí)間。因此，本文提出了一種改進(jìn)的遺傳算法。該算法采用自適應(yīng)變異率和改進(jìn)的個(gè)體選擇方法克服上述缺陷，并將這種改進(jìn)的遺傳算法用于關(guān)聯(lián)規(guī)則的挖掘[1-2]。

目前，廣泛使用的關(guān)聯(lián)規(guī)則算法是Apriori算法或其改進(jìn)算法。數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則問(wèn)題發(fā)掘支持度S和置信度C分別大于用戶最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。支持度是包含X和Y的數(shù)所占總體的百分比。置信度是包含X和Y的數(shù)與包含X數(shù)的百分比。找到所有支持度大于用戶最小支持度的項(xiàng)集，稱為頻繁項(xiàng)集。然后，從找到的頻繁項(xiàng)集中構(gòu)造其置信度大于用戶最小置信度的關(guān)聯(lián)規(guī)則[3]。

1　一種改進(jìn)的遺傳算法用于關(guān)聯(lián)規(guī)則挖掘

遺傳算法是一種基于自然選擇和生物遺傳機(jī)制的優(yōu)化技術(shù)。它依靠自然隨機(jī)算法逼近問(wèn)題的最優(yōu)解，具有很好的全局搜索能力，已經(jīng)成為優(yōu)化、搜索和求解非確定多項(xiàng)式問(wèn)題的有力工具。然而，算法中早熟問(wèn)題不可忽視，主要表現(xiàn)在兩方面：群體中所有的個(gè)體都陷于同一極值而停止進(jìn)化；接近最優(yōu)解的個(gè)體總是被淘汰，進(jìn)化過(guò)程不收斂。

1.1自適應(yīng)變異率的改進(jìn)

在遺傳算法進(jìn)化的早期階段，提出了一種自適應(yīng)變異率方法，變異率如下所示：

1.2個(gè)體選擇方法的改進(jìn)

傳統(tǒng)的遺傳算法采用輪盤(pán)賭方式選擇交叉組。這樣進(jìn)化初期，可能個(gè)別適應(yīng)度特別高的個(gè)體復(fù)制出很多后代，所帶的基因就會(huì)很快占據(jù)在種群中。因而，在后期的進(jìn)化中，其中的搜索陷入局部最優(yōu)解。因?yàn)檫m應(yīng)度大體相同，復(fù)制最后的淘汰作用降低。本文提出一種改進(jìn)的選擇淘汰方法，應(yīng)用于遺傳算法的后期：適應(yīng)度大小對(duì)待篩選個(gè)體排序；復(fù)制2份前1/4個(gè)體，復(fù)制1份前1/4到2/4的個(gè)體，隨后進(jìn)行下次選擇；留下前2/4到3/4部分個(gè)體，隨后進(jìn)行下次選擇；淘汰前3/4到4/4的部分個(gè)體，不進(jìn)行下次選擇[4]。

1.3其遺傳算法用于關(guān)聯(lián)規(guī)則挖掘

將改進(jìn)的遺傳算法用于岸橋機(jī)械關(guān)聯(lián)規(guī)則挖掘：選取20份岸橋?qū)崟r(shí)狀態(tài)健康評(píng)價(jià)表中8個(gè)主要監(jiān)測(cè)點(diǎn)，采用文章中提出的改進(jìn)遺傳算法分析其關(guān)聯(lián)規(guī)則，其編碼如表1所示[5]。

表1　測(cè)點(diǎn)位置編碼

按照“良好、預(yù)警、危險(xiǎn)、停機(jī)”四種狀態(tài)，采用十進(jìn)制編碼“良好=3，預(yù)警=2，危險(xiǎn)=1，停機(jī)=0”。將岸橋?qū)崟r(shí)狀態(tài)的健康評(píng)價(jià)表中8個(gè)主要監(jiān)測(cè)點(diǎn)表示為8位的十進(jìn)制數(shù)字，如“30313213”表示岸橋的前大梁外端區(qū)域振動(dòng)、海側(cè)門(mén)架橫梁區(qū)域振動(dòng)、左側(cè)起升電機(jī)振動(dòng)烈度、小車(chē)電機(jī)振動(dòng)烈度狀態(tài)良好，岸橋的右側(cè)起升電機(jī)振動(dòng)烈度有預(yù)警狀態(tài)，陸側(cè)門(mén)架橫梁區(qū)域振動(dòng)和起升減速箱高速軸振動(dòng)烈度有危險(xiǎn)狀態(tài)，前后大梁鉸接區(qū)域振動(dòng)有停機(jī)狀態(tài)。對(duì)于上述數(shù)據(jù)用Matlab進(jìn)行實(shí)驗(yàn)分析，隨機(jī)生成N=20的初始種群，適應(yīng)度函數(shù)中α=2.5，β=0.5，初始變異率=0.05，自適應(yīng)變異率公式中λ=1.5，交叉率=0.7，進(jìn)化終止條件為fmax-fmin＜0.05或者進(jìn)化300代[6]。

對(duì)運(yùn)算結(jié)果進(jìn)行合并相似規(guī)則 的處理，可以得到如表2所示的結(jié)果。

表2　發(fā)現(xiàn)的規(guī)則

1.4Apriori算法對(duì)比驗(yàn)證[7]

提取20份岸橋健康評(píng)價(jià)表中測(cè)點(diǎn)的“預(yù)警狀態(tài)”情況，也表示為8位的十進(jìn)制數(shù)字，如“10040670”表示預(yù)警狀態(tài)的測(cè)點(diǎn)有前大梁外端區(qū)域振動(dòng)、陸側(cè)門(mén)架橫梁區(qū)域振動(dòng)、右側(cè)起升電機(jī)振動(dòng)烈度、起升減速箱高速軸振動(dòng)烈度。將提取的數(shù)據(jù)輸入Matlab中，以“testdata.mat”命名保存。同樣，設(shè)置其最小支持度為0.2，最小置信度為0.8。使用Apriori算法對(duì)其關(guān)聯(lián)規(guī)則進(jìn)行挖掘。部分主程序如下：

load'testdata.mat'%讀入事務(wù)矩陣（每行代表一個(gè)事務(wù)，每列代表一個(gè)項(xiàng)）

PrintTransactions(testdata);%打印出事務(wù)

min_sup=4;%初始化最小支持度

min_conf=0.8;%初始化最小置信度

[rules_left，rules_right]=Apriori(testdata，min_sup， min_conf);%運(yùn)算Apriori算法

PrintRules(rules_left, rules_right);%打印強(qiáng)關(guān)聯(lián)規(guī)則

得到的頻繁項(xiàng)集和支持度截圖如圖1所示，關(guān)聯(lián)規(guī)則如圖2所示。

圖1　頻繁項(xiàng)集與支持度

圖2　關(guān)聯(lián)規(guī)則

通過(guò)圖1和圖2可以得出，根據(jù)Matlab實(shí)驗(yàn)要求的支持度都大于等于0.20，置信度都大于等于0.80的三個(gè)關(guān)聯(lián)規(guī)則基本與表2的結(jié)果吻合，海側(cè)門(mén)架橫梁區(qū)域振動(dòng)與小車(chē)電機(jī)振動(dòng)同時(shí)出現(xiàn)預(yù)警狀態(tài)最頻繁，其次是前后大梁鉸接區(qū)域振動(dòng)與左側(cè)起升電機(jī)振動(dòng)、前大梁外端區(qū)域振動(dòng)與起升減速箱高速軸振動(dòng)。

2　結(jié)語(yǔ)

針對(duì)傳統(tǒng)遺傳算法所存在的容易過(guò)早收斂問(wèn)題，提出了一種自適應(yīng)變異率算法，并應(yīng)用于進(jìn)化的早期階段，以避免進(jìn)化早期出現(xiàn)的高適應(yīng)度個(gè)體的過(guò)度復(fù)制而陷入局部最優(yōu)值。進(jìn)化后期，個(gè)體相似度很大，輪盤(pán)賭方式的淘汰能力減弱，于是提出了一種改進(jìn)的個(gè)體選擇方法。將算法應(yīng)用于岸橋機(jī)械數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘中，并用Apriori算法進(jìn)行驗(yàn)證，得出了一致的關(guān)聯(lián)規(guī)則結(jié)果。該方法只應(yīng)用于簡(jiǎn)單的岸橋機(jī)械數(shù)據(jù)，但在實(shí)際應(yīng)用過(guò)程中，可以根據(jù)具體情況在本文所選的指標(biāo)上進(jìn)一步修改，從而可以獲取更多實(shí)用有價(jià)值的岸橋信息。

[1]鄭繼剛，王邊疆.數(shù)據(jù)挖掘研究的現(xiàn)狀與發(fā)展趨勢(shì)[J].思茅師范高等專科學(xué)校學(xué)報(bào)，2010，26（1）：35-38.

[2]張莉.數(shù)據(jù)挖掘研究現(xiàn)狀及發(fā)展趨勢(shì)[J].赤峰學(xué)院學(xué)報(bào)：自然科學(xué)版，2014，30（9）：14-15.

[3]潘俊輝，王輝.一種基于改進(jìn)的遺傳算法的關(guān)聯(lián)規(guī)則挖掘及應(yīng)用[J].齊齊哈爾大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，27（2）：11-14.

[4]S.Narmadha，S.Vijayarani.Protecting Sensitive Association Rules in Privacy Preserving Data Mining using Genetic Algorithms[J].International Journal of Computer Applications，2011，（33）：37-39.

[5]Song Xiaona，ZHU Qiliang.The Application of Genetic Algorithms in Data Mining[J].Science & Technology Information，2008，（17）：401-402.

[6]溫正.精通MATLAB智能算法[M].北京：清華大學(xué)出版社，2015：143-192.

[7]呂德文.MATLAB遺傳算法工具箱的研究與應(yīng)用[J].湖南農(nóng)機(jī)，2013，40（3）：130-131.

Mining Based on Improved Genetic Algorithm and Apriori Algorithm Quayside Machinery Association Rules

PAN Haiyang,XUE Chaofei
(Logistics E ngineering, Sha nghai Maritime University, Shanghai 201306)

Based on the traditional genetic algorithm mining associa tion rules proposed improved genetic al gorithms. The genetic algorithm is an adaptive m utation rate method, and improved individual s election. F inally, apply it to the quay mechanical data mining association rules experiment and verify the efficiency and reliability of the methods used in Apriori algorithm.

genetic algorithm, Apriori algorithm, quayside machinery, association rules