基于關聯規則的數據挖掘算法的分析及應用

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

?

基于關聯規則的數據挖掘算法的分析及應用

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

摘要：數據挖掘就是從大量的數據中挖掘出有用的信息。數據挖掘與傳統的數據分析的本質區別是數據挖掘是在沒有明確假設的前提下去挖掘信息、發現知識。文章分析了數據挖掘算法的關聯規則特性，對其在股票市場中的應用進行了重點，以便更好的應用在更多的領域。

關鍵詞：關聯規則；數據挖掘算法；股票

1　關聯規則

1.1關聯規則概述

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

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

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

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

1.2Apriori算法

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

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

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

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

輸入：事務數據庫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 用于計數

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

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

（1）基于動態的項目集計數

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

（2）基于劃分的方法

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

（3）基于hash技術

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

2　關聯規則在股票數據挖掘分析及預測中的應用

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

2.1選取數據

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

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

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

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

表1　關聯規則模型的變量

2.2數據預處理

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

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

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

表2　關聯規則模型的原始數據

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

2.3數據探索

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

3　總結

對于挖掘的方法，不同的研究者將根據各自的偏好和理解制定不同的策略，發現規律可能具有不穩定性和時效性；關聯規則是數據挖掘算法的一種，將對結果有決定性的影響，過分挖掘和優化不一定會產生預期的效果，在審慎的原則下對股票數據進行挖掘，將會成為可靠的研究手段。

參考文獻

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

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

[3] 謝忠.基于數據挖掘技術的證券投資輔助決策支持系統[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