方 蓉(惠州市廣播電視大學，廣東惠州,516007)

?

基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法的分析及應用

方 蓉
(惠州市廣播電視大學，廣東惠州,516007)

摘要：數(shù)據(jù)挖掘就是從大量的數(shù)據(jù)中挖掘出有用的信息。數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒有明確假設的前提下去挖掘信息、發(fā)現(xiàn)知識。文章分析了數(shù)據(jù)挖掘算法的關(guān)聯(lián)規(guī)則特性，對其在股票市場中的應用進行了重點，以便更好的應用在更多的領域。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘算法；股票

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

1.1關(guān)聯(lián)規(guī)則概述

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識。如果兩個或多個變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)，關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。近些年來，很多業(yè)界人士對關(guān)聯(lián)規(guī)則挖掘進行了詳細的探討，關(guān)聯(lián)規(guī)則挖掘已經(jīng)成為數(shù)據(jù)挖掘中的一個非常重要的課題。

關(guān)聯(lián)規(guī)則概念是Agrawal等人在1993年首先提出的，與此同時還給出了一種性能相對較差的挖掘算法AIS。1994年，由于項目集格空間理論的建立，他們在以往定理的基礎上提出了著名的Apriori算法，這種算法目前仍作為關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法引起了人們的廣泛研究和討論。

一開始，關(guān)聯(lián)規(guī)則的產(chǎn)生主要是針對購物籃分析問題。對于分店經(jīng)理來說，如何更詳細更清楚的了解顧客的購物習慣，尤其是想了解顧客可能會在一次購物時同時購買哪些商品？為此，我們對商店的顧客購物零售數(shù)量進行購物籃分析。而顧客的購物習慣就可通過他們放入“購物籃”中的不同商品之間的關(guān)聯(lián)進行分析，零售商也可以通過這種關(guān)聯(lián)分析了解哪些商品頻繁的被顧客同時購買，進而有助于他們設計出更好的營銷方案。

與此同時，一些知名的電子商務站點也可以從具有強大功能的關(guān)聯(lián)規(guī)則挖掘中獲得很大好處。通過使用關(guān)聯(lián)規(guī)則對數(shù)據(jù)進行分析，這些電子購物網(wǎng)站可以設置用戶有可能會同時購買捆綁包，也有很多購物網(wǎng)站設置了相應的交叉銷售，具體是指顧客在購買一種產(chǎn)品時會看到與該類產(chǎn)品相關(guān)的另外一種產(chǎn)品的廣告。但是目前我國商業(yè)銀行在數(shù)據(jù)大集中之后，普遍面臨著“數(shù)據(jù)海量，信息缺乏”的窘迫情況。目前，在金融業(yè)所采用的數(shù)據(jù)庫中，大多數(shù)數(shù)據(jù)庫的功能層次都很低，只能夠簡單的實現(xiàn)數(shù)據(jù)的錄入、統(tǒng)計、查詢等，根本發(fā)現(xiàn)不了數(shù)據(jù)中蘊含的大量有實用價值的信息。綜上所述，可以說在關(guān)聯(lián)規(guī)則挖掘技術(shù)方面，我國所進行的應用研究并不是很廣泛，而且也不夠深入。

1.2Apriori算法

使用關(guān)聯(lián)規(guī)則對數(shù)據(jù)進行挖掘主要分兩個階段：第一階段必須先從原始資料集合中找出所有的高頻項目組，第二階段再由這些高頻項目組中產(chǎn)生關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘的第一階段中高頻的意思是指在所有記錄中某一項目組出現(xiàn)的頻率必須相對達到某一水平。這一項目組出現(xiàn)的頻率稱為支持度。關(guān)聯(lián)規(guī)則挖掘的第二階段是利用前一步驟的高頻k-項目組來產(chǎn)生關(guān)聯(lián)規(guī)則，在最小信賴度的條件門檻下，要稱之為關(guān)聯(lián)規(guī)則一規(guī)則所求得的信賴度滿足最小信賴度。

Apriori算法是關(guān)聯(lián)規(guī)則挖掘頻繁項集的一種原創(chuàng)性算法。Apriori算法使用的是迭代方法。Apriori算法的核心算法思想是：該算法中有連接步和剪枝步兩個關(guān)鍵步驟。對于連接步來說，為了能夠找出Lk，即頻繁k項集，而通過Lk-1與自身相連接，產(chǎn)生候選k項集Ck；其中Lk-1的元素是能夠連接的。對于剪枝步來說，Ck是Lk的超集，也就是說Ck的元素可以是頻繁的也可以不是頻繁的，但是所有的頻繁項集都包含在Ck中。對數(shù)據(jù)庫進行掃描，將Ck中的每一個候選的計數(shù)加以確定，從而確定Lk。如果Ck很大，就會導致涉及的計算量變得很大。為了能夠壓縮Ck，通常會使用Apriori性質(zhì)。

Apriori算法，使用逐層迭代找出頻繁項集。

輸入：事務數(shù)據(jù)庫D；最小支持度閾值min_sup。

輸出：D 中的頻繁項集L。

1） L1 = find_frequent_1_itemsets（D）；

2） for （k = 2； k++） {

3） Ck = aproiri_gen（Lk-1，min_sup）；

4） for each transaction t D{ // 掃描 D 用于計數(shù)

5） Ct = subset（Ck，t）；// 得到 t 的子集，它們是候選

6） for each candidate 錯誤！未找到引用源。 Ct

7） c.count++；

8） }

9） Lk={ Ck | c.count ≥ min_sup}

10） }

11） return L = 錯誤！未找到引用源。Lk；

Procedure apriori_gen (Lk-1:frequent(k-1)-itemsets)

重復，返回 Ck。

1.3Apriori算法評價和改進

基于頻繁項集的Apriori算法采用了逐層搜索的迭代方法，該算法沒有復雜的理論推導過程，簡單易懂，并且很容易實現(xiàn)。但是仍然存在一些不可避免的不足：掃描數(shù)據(jù)庫的次數(shù)過多。在Apriori算法的描述中，每生成一個候選項集，都要進行一次全面的數(shù)據(jù)庫搜索。如果要生成的頻繁項集的最大長度為N，那么就要掃描N次數(shù)據(jù)庫。在有限的內(nèi)存容量下，如果數(shù)據(jù)庫中存放的事務數(shù)據(jù)過多，就會使得系統(tǒng)過大，導致掃描數(shù)據(jù)庫時間變長，進而造成效率低下的不良現(xiàn)象。Apriori算法過程中會產(chǎn)生很多的中間項集。Apriori_gen函數(shù)是用Lk-1產(chǎn)生候選Ck，而Ck是由k個項集組成的，所以k越大，所產(chǎn)生的候選k項集的數(shù)量就會以幾何級數(shù)的形式增加。采用唯一支持度，沒有綜合考慮到各個屬性的重要程度會有所不同。Apriori算法的適應面是非常窄的，在實際的應用過程中，可能出現(xiàn)數(shù)量的、多維的、多層的關(guān)聯(lián)規(guī)則，而Apriori算法只考慮單維布爾關(guān)聯(lián)規(guī)則的挖掘。因此，這種情況下Apriori算法就不能再應用了，需要對其進行進一步的改進。

為了能夠提高Apriori算法的性能，目前已經(jīng)有許多變種對Apriori算法進行擴展和改進。具體的改進方法有以下幾個方面：

（1）基于動態(tài)的項目集計數(shù)

該算法是將數(shù)據(jù)庫分成不同的部分，標記最初的點，對數(shù)據(jù)庫進行重復掃描。該算法能夠在第二次掃描后完成所有的操作，它與Apriori算法最明顯的區(qū)別是能在任何開始點增加新的候選項目集，在每個開始點，該算法對所有項目集的支持度進行估計，如果估計所有子集是頻繁的，就會把該項目集增加到候選項目集中。

（2）基于劃分的方法

PARTITION算法首先將數(shù)據(jù)庫分成若干個互相不重疊的子數(shù)據(jù)庫，然后分別對子數(shù)據(jù)庫進行頻繁項集的挖掘，最后將所有的局部頻繁項集合并作為整個交易庫的候選項集。該算法生成整個交易數(shù)據(jù)庫的頻繁項集只需要對數(shù)據(jù)庫進行兩次掃描即可。

（3）基于hash技術(shù)

通過hash技術(shù)的使用，在生成候選集時，DHP能夠過濾掉更多的項集。因此每一次生成的候選集都會更加接近頻繁集，對于二項候選集的剪枝來說，這種技術(shù)是非常有效的。除此之外，DHP技術(shù)還能夠十分有效的降低每一次掃描數(shù)據(jù)庫的規(guī)模。

2　關(guān)聯(lián)規(guī)則在股票數(shù)據(jù)挖掘分析及預測中的應用

證券市場中的漲跌起伏往往是瞬息萬變的，盡管如此，它還是存在著一定的規(guī)律：在某一段時間中，如果A股票出現(xiàn)上漲趨勢，則B股票必然會隨之上漲；如果A股票在tl時刻出現(xiàn)上漲趨勢，B股票在t2時（t2>tl）刻出現(xiàn)上漲趨勢，則C股票必然會在t3（t3>t2）時刻上漲。前一條規(guī)律能夠用來對股票之間的相互關(guān)系進行分析，后一條規(guī)律能夠用來對股票的漲跌進行預測，這些規(guī)律在投資者的實際決策過程中有著重要的參考價值和指導作用。

2.1選取數(shù)據(jù)

如果上市公司所經(jīng)營的業(yè)務是相同或相近的，則在一段時間內(nèi)股票價格的走勢就會呈現(xiàn)出相似性；在一定時間內(nèi)，屬于同一個區(qū)域的上市公司也會受到區(qū)域經(jīng)濟政策的直接影響，也會呈現(xiàn)出大體相同的變化形勢；如果上市公司之間具有關(guān)聯(lián)交易，相互持股、控股，則它們之間也會產(chǎn)生某種相互作用。上述規(guī)則能夠通過關(guān)聯(lián)規(guī)則分析來發(fā)現(xiàn)，然而更重要的是發(fā)現(xiàn)另一種表面上沒有很強的相關(guān)性、但是實際的股票價格卻具有很大關(guān)聯(lián)的規(guī)則。

設股票行情數(shù)據(jù)D={X1，X2，…，Xi，…，Xn。}，其中Xi (1

本文選取的研究對象是滬深300指數(shù)成分股，樣本時間是從2010年9月2日到2011年9月1日一年的數(shù)據(jù)。分析可知，滬深300指數(shù)成分股能很好反映出上海和深圳證券市場的總體特征，具有很強的代表性。

選取樣本時間從2010年9月2日到2011年9月1日這段時間的主要原因是：在這段時間中，大盤經(jīng)歷了上漲波段和下跌波段，滬深300指數(shù)最低到 1598，最高達3256，而且上漲時間和下跌時間大致相同。本文數(shù)據(jù)均來源于CASMAR數(shù)據(jù)庫，著重考慮股票價格變化之間存在的關(guān)聯(lián)關(guān)系，由于一天中股票價格有很多種，本文主要考慮的是收盤價。因此原始數(shù)據(jù)包含日期、股票代碼、收盤價三個變量，經(jīng)過處理數(shù)據(jù)中共有71268條記錄。

表1　關(guān)聯(lián)規(guī)則模型的變量

2.2數(shù)據(jù)預處理

數(shù)據(jù)預處理是指在主要的處理以前對數(shù)據(jù)進行的一些處理。在我們實際生活的世界中，數(shù)據(jù)大多數(shù)都是不完整并且不一致的，根本沒有辦法直接使用數(shù)據(jù)挖掘方法，或者會導致挖掘的結(jié)果不能讓人滿意。為了能夠有效的將數(shù)據(jù)挖掘的質(zhì)量提高，數(shù)據(jù)預處理技術(shù)便在這種形勢下產(chǎn)生了。數(shù)據(jù)預處理的方法有很多，具體包括：數(shù)據(jù)清理，數(shù)據(jù)集成，數(shù)據(jù)歸約，數(shù)據(jù)變換等。在對數(shù)據(jù)進行挖掘之前，使用這些數(shù)據(jù)處理技術(shù)，能夠在很大程度上提高數(shù)據(jù)挖掘模式的質(zhì)量，并且有效的減少挖掘所使用的時間。我們所要研究的是在一段時間內(nèi)，股票價格變動之間存在的關(guān)聯(lián)關(guān)系，因此只需對那些對投資有參考價值的數(shù)據(jù)進行研究。在投資過程中，關(guān)系到投資者收益的重要指標是收益率，在數(shù)據(jù)挖掘中所選用的是每天的漲跌幅。首先以收盤價為依據(jù)，將每日的漲跌幅計算出來，日漲跌幅就是當日收盤價和上一個交易日收盤價之差與上一個交易日收盤價之比。計算公式如下：

在分析過程中我們所感興趣的是那些每天的漲跌幅大于一定幅度的股票，因為在股票市場中，大多數(shù)股票會隨著大盤指數(shù)的漲跌而不斷發(fā)生變化，多數(shù)股票都會在大盤指數(shù)漲跌幅進行上下波動，所以只有漲跌幅超過一定范圍的股票才具有研究意義。因此我們在進行分析之前，引入最小日漲跌幅Min-UpRat。最小日漲跌幅的值是以具體的股票行情為依據(jù)并由用戶確定的，本文選取Min-UpRat為3%，這主要是從以下幾個方面考慮：現(xiàn)階段，中國的證券市場還處于發(fā)展階段，尚不成熟。股票在牛市中會存在隨大盤指數(shù)普遍上漲的情況，因此只有對那些漲勢較為劇烈的股票進行分析研究才會有實際意義。大部分股票在熊市中會出現(xiàn)普遍下跌的情況，出現(xiàn)上漲形勢的股票只有極少的一部分，漲勢能達到3%漲幅的股票更是少之又少。

在樣本中添加一個新的變量，極為win，當日漲跌幅大于最小日漲跌幅min-UpRat時，win就記為1，日漲跌幅小于或等于最小日漲跌幅min-UpRat時，win就記為0。在原始數(shù)據(jù)中，交易日期均為10個字符的字符型變量，共有244天。眾所周知，在進行數(shù)據(jù)挖掘時，字符長度較大會占用大量的內(nèi)存，因此應該盡量用簡短的數(shù)據(jù)型變量來對其進行替換。所以為了節(jié)省空間進而提高運行的效率，我們重新對交易時間變量進行編碼，用1，2，…，244來標記。將股票代碼均變?yōu)?位字符的字符型數(shù)據(jù)，共有300只股票，分別用1，2，…，300標識。在進行關(guān)聯(lián)規(guī)則挖掘時，直接處理對象是股票和日期的新編碼，間接處理對象是股票代碼和交易日期，這樣便可有效減少內(nèi)存的占用，有利于提高挖掘效率。

表2　關(guān)聯(lián)規(guī)則模型的原始數(shù)據(jù)

選取的原始數(shù)據(jù)有字符型證券代碼，字符型交易日期，數(shù)值型收盤價，如表2所示。接著對原始數(shù)據(jù)進行變換和預處理，然后計算出每個交易日各只股票的漲跌幅。

2.3數(shù)據(jù)探索

一般情況下，在進行數(shù)據(jù)挖掘之前可以先對數(shù)據(jù)進行初步探索，用描述性統(tǒng)計方法對數(shù)據(jù)進行初步的分析，從而對滬深300指數(shù)的一些基本性質(zhì)進行簡單的了解。通過整理可以看出，雖然股票指數(shù)有某種程度的變化和波動，但是總體變化趨勢是先下跌而后上漲。這種情況表明，在這一年中由于受到全球經(jīng)濟的影響，股票市場先逐漸下降，隨著中國各項經(jīng)濟政策的一系列措施的實施，中國證券市場又出現(xiàn)了回升的趨勢。

3　總結(jié)

對于挖掘的方法，不同的研究者將根據(jù)各自的偏好和理解制定不同的策略，發(fā)現(xiàn)規(guī)律可能具有不穩(wěn)定性和時效性；關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘算法的一種，將對結(jié)果有決定性的影響，過分挖掘和優(yōu)化不一定會產(chǎn)生預期的效果，在審慎的原則下對股票數(shù)據(jù)進行挖掘，將會成為可靠的研究手段。

參考文獻

[1] 夏火松主編.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)[M]. 科學出版社, 2004

[2] 王玲.數(shù)據(jù)挖掘在證券分析中的應用[D]. 貴州大學 2008

[3] 謝忠.基于數(shù)據(jù)挖掘技術(shù)的證券投資輔助決策支持系統(tǒng)[D].重慶大學 2005

Analysis and application of data mining algorithm based on association rules

Fang Rong
(Huizhou radio and TV University,Guangdong Huizhou,516007)

Abstract：Data mining is to extract useful information from a large number of data.The essential difference between data mining and traditional data analysis is that data mining is to excavate information and discover knowledge without explicit assumptions. This paper analyzes the characteristics of association rules of data mining algorithms, and focuses on the application of the data mining algorithm in the stock market, so that it can be applied in more areas.

Keywords：association rule; data mining algorithm; stock