基于改進遺傳算法與Apriori算法的岸橋機械關聯規則挖掘

潘海洋　薛超飛

（上海海事大學 物流工程學院，上海 201306）

基于改進遺傳算法與Apriori算法的岸橋機械關聯規則挖掘

潘海洋薛超飛

（上海海事大學 物流工程學院，上海 201306）

基于對傳統遺傳算法的關聯規則挖掘，提出了改進型遺傳算法。該算法提出了一種自適應變異率方法，并改進了個體選擇方法。最后，將其應用到岸橋機械數據關聯規則挖掘中進行實驗，并用Apriori算法驗證了該方法的高效性和可靠性。

遺傳算法 Apriori算法 岸橋機械 關聯規則

引言

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

目前，廣泛使用的關聯規則算法是Apriori算法或其改進算法。數據挖掘關聯規則問題發掘支持度S和置信度C分別大于用戶最小支持度和最小置信度的關聯規則。支持度是包含X和Y的數所占總體的百分比。置信度是包含X和Y的數與包含X數的百分比。找到所有支持度大于用戶最小支持度的項集，稱為頻繁項集。然后，從找到的頻繁項集中構造其置信度大于用戶最小置信度的關聯規則[3]。

1　一種改進的遺傳算法用于關聯規則挖掘

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

1.1自適應變異率的改進

在遺傳算法進化的早期階段，提出了一種自適應變異率方法，變異率如下所示：

1.2個體選擇方法的改進

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

1.3其遺傳算法用于關聯規則挖掘

將改進的遺傳算法用于岸橋機械關聯規則挖掘：選取20份岸橋實時狀態健康評價表中8個主要監測點，采用文章中提出的改進遺傳算法分析其關聯規則，其編碼如表1所示[5]。

表1　測點位置編碼

按照“良好、預警、危險、停機”四種狀態，采用十進制編碼“良好=3，預警=2，危險=1，停機=0”。將岸橋實時狀態的健康評價表中8個主要監測點表示為8位的十進制數字，如“30313213”表示岸橋的前大梁外端區域振動、海側門架橫梁區域振動、左側起升電機振動烈度、小車電機振動烈度狀態良好，岸橋的右側起升電機振動烈度有預警狀態，陸側門架橫梁區域振動和起升減速箱高速軸振動烈度有危險狀態，前后大梁鉸接區域振動有停機狀態。對于上述數據用Matlab進行實驗分析，隨機生成N=20的初始種群，適應度函數中α=2.5，β=0.5，初始變異率=0.05，自適應變異率公式中λ=1.5，交叉率=0.7，進化終止條件為fmax-fmin＜0.05或者進化300代[6]。

對運算結果進行合并相似規則 的處理，可以得到如表2所示的結果。

表2　發現的規則

1.4Apriori算法對比驗證[7]

提取20份岸橋健康評價表中測點的“預警狀態”情況，也表示為8位的十進制數字，如“10040670”表示預警狀態的測點有前大梁外端區域振動、陸側門架橫梁區域振動、右側起升電機振動烈度、起升減速箱高速軸振動烈度。將提取的數據輸入Matlab中，以“testdata.mat”命名保存。同樣，設置其最小支持度為0.2，最小置信度為0.8。使用Apriori算法對其關聯規則進行挖掘。部分主程序如下：

load'testdata.mat'%讀入事務矩陣（每行代表一個事務，每列代表一個項）

PrintTransactions(testdata);%打印出事務

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

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

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

PrintRules(rules_left, rules_right);%打印強關聯規則

得到的頻繁項集和支持度截圖如圖1所示，關聯規則如圖2所示。

圖1　頻繁項集與支持度

圖2　關聯規則

通過圖1和圖2可以得出，根據Matlab實驗要求的支持度都大于等于0.20，置信度都大于等于0.80的三個關聯規則基本與表2的結果吻合，海側門架橫梁區域振動與小車電機振動同時出現預警狀態最頻繁，其次是前后大梁鉸接區域振動與左側起升電機振動、前大梁外端區域振動與起升減速箱高速軸振動。

2　結語

針對傳統遺傳算法所存在的容易過早收斂問題，提出了一種自適應變異率算法，并應用于進化的早期階段，以避免進化早期出現的高適應度個體的過度復制而陷入局部最優值。進化后期，個體相似度很大，輪盤賭方式的淘汰能力減弱，于是提出了一種改進的個體選擇方法。將算法應用于岸橋機械數據的關聯規則挖掘中，并用Apriori算法進行驗證，得出了一致的關聯規則結果。該方法只應用于簡單的岸橋機械數據，但在實際應用過程中，可以根據具體情況在本文所選的指標上進一步修改，從而可以獲取更多實用有價值的岸橋信息。

[1]鄭繼剛，王邊疆.數據挖掘研究的現狀與發展趨勢[J].思茅師范高等專科學校學報，2010，26（1）：35-38.

[2]張莉.數據挖掘研究現狀及發展趨勢[J].赤峰學院學報：自然科學版，2014，30（9）：14-15.

[3]潘俊輝，王輝.一種基于改進的遺傳算法的關聯規則挖掘及應用[J].齊齊哈爾大學學報：自然科學版，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].北京：清華大學出版社，2015：143-192.

[7]呂德文.MATLAB遺傳算法工具箱的研究與應用[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