何云峰

（泉州醫(yī)學(xué)高等專科學(xué)?！∪荨?62100）

1　引言

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的一個重要分支，在數(shù)據(jù)挖掘中占有重要的地位。它對數(shù)據(jù)庫中數(shù)據(jù)進行分析處理，從而發(fā)現(xiàn)數(shù)據(jù)之間的各種關(guān)系。而關(guān)聯(lián)規(guī)則挖掘中最為經(jīng)典、基本的算法則是Apriori算法［1］，眾多學(xué)者對Apriori算法本身進行了各種改進，更有學(xué)者把該算法與其他算法混和使用來改進該算法的效率［2～4］。大家公認的，首先，Apriori算法的最大弊端是其需要多次掃描數(shù)據(jù)庫和過多的IO接口操作，使其需要耗費過多大量的時間和空間。本文的工作之一就是先對Apriori算法進行改進。其次，Apriori算法挖掘出的關(guān)聯(lián)規(guī)則存在如下一些顯著問題：規(guī)則的數(shù)量太多，其中也含有一些誤導(dǎo)規(guī)則和弱關(guān)聯(lián)規(guī)則。如何從中提取出強關(guān)聯(lián)規(guī)則是需要解決的問題。這個過程是一個全局搜索的過程，而遺傳算法是一種偏向全局解優(yōu)化算法，雖然有時容易發(fā)生“早熟”以及在進化后期搜索效率低等缺點，但總體上還是有效地避免了搜索過程的局部最優(yōu)解問題。因此，將遺傳算法用于關(guān)聯(lián)規(guī)則的進一步提取上在理論上是可行的。該點則是本文的第二個工作。

2　Apriori算法中的幾個定義和改進的Apriori算法

2.1　Apriori算法中的幾個定義

Apriori算法中有幾個與本文相關(guān)而且在后續(xù)的遺傳算法中要用到的定義。

支持度：是指在事物數(shù)據(jù)庫中，包含 X∪Y事物的條數(shù)占整個事務(wù)條數(shù)的比例，記為

式中，σ(N)表示事務(wù)的總條數(shù)，σ(X∪Y)表示同時包含X和Y的事務(wù)條數(shù)。

置信度：是指在事物數(shù)據(jù)庫中，包含X∪Y事物的條數(shù)占含有項集X的事務(wù)條數(shù)的比例，記為

式中，σ(X)表示包含項目X事務(wù)的總條數(shù)，置信度越高表示X與Y關(guān)聯(lián)程度越大。

2.2　改進的Apriori算法

Apriori算法每次都要掃描數(shù)據(jù)庫，很是費時費力。本文以空間換時間的角度來對算法進行改進，即空間上生成大量的項目，而在時間上的節(jié)約則體現(xiàn)在僅掃描若干次數(shù)據(jù)庫。由于要產(chǎn)生巨量的項目組合，所以不可能把這些組合一次放入機器內(nèi)存中處理。于是產(chǎn)生了這樣一種想法，即：在Apriori算法每次掃描數(shù)據(jù)庫時，檢測在每次遍歷的末尾處集合Ck的大小是否能裝入內(nèi)存，且本次遍歷產(chǎn)生的大型候選比前次要少，那么就停止使用Apriori算法，轉(zhuǎn)而使用把集合Ck放入內(nèi)存的改進型Apriori算法。曾經(jīng)的實驗表明傳統(tǒng)的Apriori算法在生成頻繁k（通常小于4）項集時占用時間最多，幾乎占到該算法的3/5時間，而這種轉(zhuǎn)入內(nèi)存的Apriorii算法所耗時間遠比Apriori多，于是本文主要對生成頻繁k（通常小于4）項集部分進行相關(guān)改進。對于一些不是很復(fù)雜，且數(shù)據(jù)庫不是巨型的來說，通常生成頻繁3項集后就因為項集里的項目數(shù)劇減，而可以轉(zhuǎn)入內(nèi)存。所以本文在使用改進型的Apriori算法形成頻繁3項集后無需要再設(shè)置判斷條件即轉(zhuǎn)入內(nèi)存，再次使用傳統(tǒng)的Apriori算法思路，而因為使用了空間工具，使得后期所用的Apriori算法在查找數(shù)據(jù)時不必再掃描原始數(shù)據(jù)庫，從而節(jié)約了數(shù)據(jù)庫掃描次數(shù)。

改進思路：做一個行名、列名相同的2維數(shù)組用來存儲候選頻繁2項集C2的所有元素。例如第一條事務(wù)為（A，B，C），3個項目，則用圖1表示C2。這個數(shù)組稱為：2項集支持度矩陣。分別把順序號1，2，3賦予A，B，C，這樣就可以使用下標(biāo)（i，j）訪問到候選頻繁2項集中的任何一項，比如使用（2，3）就可以訪問到AB的坐標(biāo)。先對矩陣清零，第一邊掃描數(shù)據(jù)庫時就能確定C2中各項的支持度。把每一條交易按交易項目排序，生成所有可能的順序2項組合。比如第二條交易事務(wù)為（A，B，C，E，F(xiàn)），則所有的順序2項組合為｛A，B｝、｛A，C｝、｛A，E｝、｛A，F(xiàn)｝、｛B，C｝、｛B，E｝、｛B，F(xiàn)｝、｛C，E｝、｛C，F(xiàn)｝、｛E，F(xiàn)｝，那么它們相應(yīng)的矩陣元素的計數(shù)加1，就完成了對第二條交易事務(wù)的處理。處理完2條事務(wù)的矩陣如圖2。接著再掃描完數(shù)據(jù)庫的所有交易，并作相應(yīng)處理。再設(shè)置一個數(shù)組M［i］用以記錄事務(wù)中項目個數(shù)的，以備計算置信度和消減數(shù)據(jù)庫使用。

在獲得候選頻繁2項集的支持度后，接著查找矩陣的第二行，找出所有支持度大于等于min_sup，比如為2的項，再用第一項與第二項組合生成3項集，并且記下第一項與第二項分別所在的列號，于是查找由這兩個列號組成的矩陣元素的值，若大于等于min_sup，則用第一項與第二項組合生成的3項集就是頻繁3項集，其支持度即為第一項和第二項這兩項的2個列號組成的矩陣元素的支持度和第一項及第二項的支持度，三者的最小值。比如組合AB和AC兩項，形成ABC項，而項的支持度則是AB的支持度2，AC的支持度2，BC的支持度2中最小值2。依次組合矩陣第二行的其他項，再接著處理矩陣的其他行。該方法可直接產(chǎn)生頻繁3項集以及其支持度，無需生成候選頻繁3項集。

另外，本文在數(shù)據(jù)庫條目數(shù)的消減上也采取了一些方法。若一條事務(wù)包含k頻繁項集，那么在產(chǎn)生這個k（＞3）候選頻繁項集時，就只需查看數(shù)組M［i］的值大于k的事務(wù)。

圖1　候選頻繁2項集

圖2　2項集支持度矩陣

3　遺傳算法

遺傳算法是一種模擬生物界自然選擇、遺傳機制，基于群體的進化算法，具有很強的隨機性、魯棒性和隱含并行性。它處理的是參數(shù)集合的編碼，即給定的字符串，所以較為方便，省時；能夠搜索空間的多個點，因而有效地進行全局優(yōu)化搜索從而找到全局解，對大規(guī)模數(shù)據(jù)集的處理是種有效的方法。遺傳算法的主要步驟有三：第一，編碼，形成初始種群。第二，定義一個適應(yīng)度函數(shù)用以評價、引導(dǎo)、檢驗種群進化程度，適應(yīng)度越高說明種群里的個體越好，而不滿足適應(yīng)度的種群逐漸將被淘汰。第三，遺傳操作，結(jié)束時用適應(yīng)度函數(shù)或設(shè)置的終止條件檢驗，若不滿足，繼續(xù)遺傳操作［5～10］。

3.1　編碼

前述改進的Apriori算法中已經(jīng)產(chǎn)生了大量的關(guān)聯(lián)規(guī)則。所以此時的編碼方式宜選Michigan編碼，即對每一條規(guī)則編碼成一條染色體。例如數(shù)據(jù)集中有n個屬性，則前i個屬性稱為規(guī)則的前因，后n-i個屬性稱為規(guī)則的后果。例如，股票部分屬性的數(shù)據(jù)集，如表1。一條規(guī)則：單日K線形態(tài)=跳空大陽線，單日成交量=放量，MACD=白線上穿0軸?趨勢=上漲，這條規(guī)則的編碼即為“12#11”，編碼“#”表示不需要該屬性。

對已經(jīng)形成的關(guān)聯(lián)規(guī)則進行編碼后，則形成了一個遺傳算法所需的初始種群。

表1　股票屬性數(shù)據(jù)集

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

為了檢測群種的每個個體是否滿意，一般要根據(jù)目標(biāo)設(shè)置一個函數(shù)用以檢測。這個函數(shù)即為適應(yīng)度函數(shù)，它為群體進化的方向提供了依據(jù)。放到本文中，則是要檢測每條已挖掘出的規(guī)則的有效性的問題上。所以打算從實用性、確定性、理解性來考量，即支持度、置信度、理解度。前兩者之前已經(jīng)定義過?，F(xiàn)定義理解度和適應(yīng)度函數(shù)。

理解度：用來衡量規(guī)則的簡潔性。規(guī)則過長，即包含了大量的前因，這種情況不易用戶理解和操作。我們這樣定義：

式中，|Y|表示后果中包含的屬性個數(shù)，|X∪Y|表示某一規(guī)則中屬性的總量。

適應(yīng)度函數(shù)可定義為

式中，Z1，Z2，Z3是根據(jù)用戶需要定義的權(quán)重。某項值越大說明該項度量越重要。

3.3　遺傳操作

遺傳操作是遺傳算法的重要組成部分，包括選擇、交叉、變異三個步驟。

1）選擇算子。選擇操作的作用就是把優(yōu)勝的個體直接或通過交叉產(chǎn)生的個體遺傳到后代，再以個體適應(yīng)度函數(shù)值的評判通過一些方法將個體從父輩中抽取出來，再復(fù)制到下一代。本文采用傳統(tǒng)的輪賭法選擇算子。

2）交叉。子代總是同時要繼承父母代的基因。交叉則是把一對父母個體的部分基因用以重組后產(chǎn)生新的個體基因。交叉運算主要有：一點交叉、兩點交叉、多點交叉等操作。本文使用最簡單的一點交叉操作。以隨機的方式選取交叉位置，在由父母代生成的交配池中以交叉概率Pi選取兩個個體X，Y，并在某個交叉點交叉，交叉前形如X=（X1，X2，…，Xn），Y=（Y1，Y2，…，Yn），交叉后形如 X=（X1，X2，…，Xk，Yk+1，Yk+2，…，Yn），Y=（Y1，Y2，…，Yk，Xk+1，Xk+2，…，Xn）。

3）變異。對群種里的個體的某個基因進行改變，就形成了變異操作。變異可以使群種中的抗體變多，從而使搜索范圍擴大，進而在更大范圍內(nèi)找到更優(yōu)的個體。交叉運算使得遺傳算法有了全局搜索功能，而變異操作使得它具有了局部搜索能力。常見的變異方法有：基本變異算子、逆轉(zhuǎn)算子、自適應(yīng)變異算子。本文采用基本變異算子策略，在群中的基因序列中隨機選擇N個基因位置，再對這N個基因值以概率Pm進行變異，即1變成0，0變成1。

4　實驗

4.1　股市數(shù)據(jù)預(yù)處理

選取時間段2014年5月5日至2016年8月18日的滬深交易所2000支股票的相關(guān)基本數(shù)據(jù)。之所以選這個時間段，一是就近原則，二是這段時期股市經(jīng)歷了大幅上漲，大幅下跌，震蕩這幾種情況，而這幾種情況完全反映了股市里的各種情況，也就是說數(shù)據(jù)源很客觀，很全面。基本的股票數(shù)據(jù)信息太多，太雜亂，如果直接從中提取關(guān)聯(lián)規(guī)則，顯然會無的放矢。所以需要提取甚至組合一些數(shù)據(jù)。依照現(xiàn)今股票技術(shù)分析模型，以時間序列的模式模型，從長線屬性，中短線屬性，短線屬性和趨勢，這四個方面定義股票屬性［11～16］。長線屬性主要是長期股價構(gòu)造形態(tài)（一般是1到若干個月數(shù)據(jù)組成的模式，取值若干），相關(guān)成交量的組合形態(tài)（取值若干），長期均價線形態(tài)。中短線屬性主要是K線組合形態(tài)（比如3連陽等，取值若干），相關(guān)成交量的組合形態(tài)，中期均價線形態(tài)，一些中短期技術(shù)指標(biāo)（比如BOLL等指標(biāo)，選取3個）。短線屬性主要當(dāng)日K線形態(tài)（比如黃昏之星，跳空缺口等，取值若干），當(dāng)日成交量，一些短期技術(shù)指標(biāo)（比如MACD，KDJ等指標(biāo)，選取3個）。趨勢就是五種情況：大幅上漲、中幅上漲、區(qū)域震蕩、中幅下跌、大幅下跌?？偣?7個屬性。一支股票2年多的基本數(shù)據(jù)可以轉(zhuǎn)化成若干個關(guān)于5種趨勢的模式，即若干條基因。股票基本數(shù)據(jù)轉(zhuǎn)換成模式時，采用的是時間序列的模式匹配的方法。即按照當(dāng)今股市中的技術(shù)指標(biāo)提前創(chuàng)建定義好若干模式，比如三角形整理、圓弧底，等等［17～20］。之后，把股票基本數(shù)據(jù)分時段轉(zhuǎn)換成的模式與這些定義好的模式比較，看是否匹配。至于沒有匹配的模式，則把這種模式定義成一個新模式，讓其他的模式再與它比較，也就檢驗了這種新模式到底成立不。這樣股票的基本數(shù)據(jù)就轉(zhuǎn)變成了17個屬性的數(shù)據(jù)庫。數(shù)據(jù)庫規(guī)模上，一支股票2年多的的數(shù)據(jù)至少能轉(zhuǎn)化出5條基因，那么數(shù)據(jù)庫規(guī)模至少是上萬條的。實際上，股市數(shù)據(jù)預(yù)處理的時間和代價很大，遠遠超過Apriori算法和遺傳算法的總用時。

4.2　對股票數(shù)據(jù)庫用改進的Apriori算法和遺傳算法加以運行

首先，用改進的Apriori算法對17個屬性的數(shù)據(jù)庫進行挖掘。在i7—6700k處理器的計算機中運行，得到537條關(guān)聯(lián)規(guī)則。在時間上，改進的Apriori算法因為前期創(chuàng)建使用了額外空間，所以費時較多，而后期因減少了數(shù)據(jù)庫的掃描時間，所以節(jié)約了大量時間?？傮w耗時為15.7s，而傳統(tǒng)的Apriori算法耗時23.7s。改進的Apriori算法用時占傳統(tǒng)Apriori算法用時的66%。其次，用遺傳算法對挖掘出的關(guān)聯(lián)規(guī)則再進行提煉，精簡。主要參數(shù)為：變異概率Pm=0.1，交叉概率Pc=0.8，最小支持度Sup=0.7，最小可信度Con=0.1。537條關(guān)聯(lián)規(guī)則被篩選掉了124條弱關(guān)聯(lián)規(guī)則和誤導(dǎo)規(guī)則，剩下了413條。比如用改進的Apriori算法挖掘出了這樣2條規(guī)則，第一條，MACD指標(biāo)里的白線剛好穿越0軸向上（短線屬性），當(dāng)日中陽線且穿越最近的2根均線，比如5日和10日（短線屬性），成交量較大（短線屬性），不是處于下跌趨勢中（中短線屬性），則后面有一段上漲。第二條，MACD指標(biāo)里的白線剛好穿越0軸向上（短線屬性），當(dāng)日大、中陽線（短線屬性），成交量較大（短線屬性），60日均線已走平或趨勢已向上（中線屬性），則后面有一段上漲。這2條規(guī)則就被合成1條，MACD指標(biāo)里的白線剛好穿越0軸向上（短線屬性），當(dāng)日大、中陽線（短線屬性），成交量較大（短線屬性），中期趨勢不差（中線屬性），則后面有一段上漲。從而實現(xiàn)了去掉弱關(guān)聯(lián)規(guī)則。

5　結(jié)語

本文通過空間換時間的思路，對傳統(tǒng)的Apriori算法進行了改進，并對股票數(shù)據(jù)庫進行了建模與挖掘。而后又用遺傳算法對挖掘出的關(guān)聯(lián)規(guī)則進行了優(yōu)化，得到了大量、實用的股市規(guī)則，對股民買賣股票起著良好的指導(dǎo)作用。在遺傳算法中因為加入了理解度這個概念，從而使得挖掘出的規(guī)則在理解和操作上顯得不是那么困難。同時，也消除了弱關(guān)聯(lián)規(guī)則和誤導(dǎo)規(guī)則。

［1］R.Agrawal and R.Srikant，F(xiàn)ast Algorithms for Mining Association Rules in Large Databases［C］//In Research Report RJ 9839，IBM Almaden Research Center，San Jose，Califomia，1994.

［2］何云峰.Apriori改進算法綜述［J］.微型機與應(yīng)用，2013，32（6）：1-3.HE Yunfeng.A Survey of Improved Apriori Algorithm［J］.Microcomputer&ItsApplications，2013，32（6）：1-3.

［3］秦吉勝，宋瀚濤.關(guān)聯(lián)規(guī)則挖掘AprioriHybird算法的研究和改進［J］.計算機工程，2004，17（30）：7-9.QIN Jisheng，SONG Hantao.Study and Improvement of AprioriHybird Algorithm in Mining Association Rules［J］.Computer Engineering，2004，17（30）：7-9.

［4］何云峰.一種改進的Apriori算法及在計算機一級等級考試的應(yīng)用［J］.數(shù)字技術(shù)與應(yīng)用，2016（6）：147-149.HE Yunfeng.An Improved Apriori Algorithm and Its Application in National Computer First Rank Examination［J］.Digital Technology&Application，2016（6）：147-149.

［5］Anandhavalli M，Sudhanshu SK，Kumar A，et al.Optimized Association Rule Mining Using Genetic Algorithm［J］.Advances in Information Mining，2009，1（2）：1-4.

［6］馬永杰，云文霞.遺傳算法研究進展［J］.計算機應(yīng)用研究，2012，29（4）：1201-1206.MA Yongjie，YUNWenxia.Research Progress of Genetic Algorithm［J］.Application Research of Computers，2012，29（4）：1201-1206.

［7］歐陽桃紅，任彧.一種基于遺傳算法的關(guān)聯(lián)規(guī)則改進算法［J］.杭州電子科技大學(xué)學(xué)報（自然科學(xué)版），2015，35（5）：79-83.OUYANG Taohong，REN Yu.An Improved Algorithm for Mining Association Rules Based on Genetic Algorithm［J］.JournalofHangzhou DianziUniversity（Natural Sciences），2015，35（5）：79-83.

［8］詹芹，張幼明.一種改進的動態(tài)遺傳Apriori挖掘算法［J］.計算機應(yīng)用研究，2010，27（8）：2929-2930.ZHAN Qin，ZHANG Youming.Improved Dynamic Genetic Apriori Mining Algorithm［J］.Application Research of Computers，2010，27（8）：2929-2930.

［9］韓宏博.基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)研究［D］.西安：西安電子科技大學(xué)碩士學(xué)位論文，2010.HAN Hongbo.The Study of Association Rules Data Mining Based on Genetic Algorithm［D］.Xi'an：Master's thesis of Xi'an Electronic and Science University，2010.

［10］劉建文，丁潔玉，潘坤，等.基于個體相似度的改進自適應(yīng)遺傳算法研究［J］.青島大學(xué)學(xué)報（工程技術(shù)版），2016，31（1）：16-19.LIU Jianwen，DING Jieyu，PAN Kun.Improved Adaptive Genetic Algorithm Based on Individual Similarity［J］.Journal of QingDao University（E&T），2016，31（1）：16-19.

［11］何云峰，楊燕.基于模糊時間序列——股票走勢的建模與應(yīng)用［J］.微機算計信息，2006，22（11）：253-255.HE Yunfeng，YANG Yan.Modeling and Application of Stock Trend Based on Fuzzy Time Series［J］.Microcomputer Information，2006，22（11）：253-255.

［12］鄧強強.基于Agent的股市建模與市場分形特征研究［D］.南京：南京信息工程大學(xué)碩士學(xué)位論文，2015.DENG Qiangqiang.Agent-based Stock MarketModeling and Market Fractal Property Research［D］.Nanjing：Master's thesis of Nanjing University of Information Science and Technology，2015.

［13］戎容，吳萍.基于遺傳算法的股票市場選擇模型［J］.計算機工程與應(yīng)用，2016，52（18）：167-172.RONG Rong，WU Ping.Stock Market Selection Model Based on Genetic Algorithm［J］.Computer Engineering and Applications，2016，52（18）：167-172.

［14］潘明剛.基于遺傳算法的模糊分類系統(tǒng)在股票分析中的應(yīng)用［D］.北京：中國地質(zhì)大學(xué)碩士學(xué)位論文，2016.PAN Minggang.Application of Fuzzy Classification System Based on Genetic Algorithm in Stock Analysis［D］.Beijing：Master's thesis of China University of Geosciences，2016.

［15］黃智翔.數(shù)據(jù)挖掘技術(shù)在股價分析中的應(yīng)用研究［D］.云南：云南大學(xué)碩士學(xué)位論文，2016.HUANG Zhixiang.Research on the Application of Data Mining in Stock Price Analysis［D］.Yunnan：Master's thesisofYunnan University，2016.

［16］張在紅.基于基本分析與技術(shù)分析的股票投資研究［D］.蘭州：蘭州大學(xué)碩士學(xué)位論文，2016.ZHANG Zaihong.Based on Fundamental Analysis and Technical Analysis for Stock Investment Research［D］.Lanzhou：Master's thesis of Lanzhou University，2016.

［17］梁挺，孫金金.技術(shù)投資方法在股票實戰(zhàn)中的應(yīng)用分析［J］.商業(yè)經(jīng)濟，2016（4）：146-148.LIANG Ting，SUN Jinjin.An Analysis of Application of Technology Investment in Stock［J］.Shang Ye Jing Ji，2016（4）：146-148.

［18］賈云朋.數(shù)據(jù)挖掘在股票曲線趨勢預(yù)測中的研究及應(yīng)用［D］.吉林：吉林大學(xué)碩士學(xué)位論文，2015.JIA Yunpeng.Research and Application of Data Mining in the Prediction of Trends of the Curves in Stock［D］.Jilin：Master's thesisof Jilin University，2015.

［19］宋嘉輝.股票市場技術(shù)分析的理論與實踐［D］.蘭州：蘭州大學(xué)碩士學(xué)位論文，2015.SONG Jiahui.The Stock Market Technical Analysis Theory and the Practice［D］.Lanzhou：Master's thesis of Lanzhou University，2015.

［20］證券之星 www.stockstar.Com［EB/OL］.