改進(jìn)的Apriori算法的研究與應(yīng)用?

李 龍 劉 澎 張可佳 黃 珊 李 倩

（東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 大慶 163318）

1 引言

數(shù)據(jù)挖掘是對大數(shù)據(jù)集的探索過程，并揭示出其中的隱含規(guī)律，它融合了眾多的技術(shù)，是計(jì)算機(jī)科學(xué)的一個(gè)重要分支［1］。利用數(shù)據(jù)挖掘技術(shù)進(jìn)行數(shù)據(jù)分析，是一項(xiàng)極具現(xiàn)實(shí)意義的嘗試，它能夠加速理論知識到實(shí)際應(yīng)用的轉(zhuǎn)化。其中關(guān)聯(lián)分析是數(shù)據(jù)挖掘中重要的分析技術(shù)之一，關(guān)聯(lián)分析是從歷史數(shù)據(jù)集中發(fā)現(xiàn)隱含模式，從海量數(shù)據(jù)集中發(fā)現(xiàn)潛在價(jià)值的方法，它反映過了一個(gè)事件與其他事件相互關(guān)聯(lián)的關(guān)系。

隨著信息化時(shí)代的到來，各類公司積攢了大量的數(shù)據(jù)，如何利用這些長期積攢的數(shù)據(jù)成為了主要問題［2］。本文主要針對股票的歷史交易數(shù)據(jù)進(jìn)行挖掘，指導(dǎo)投資者合理購買股票，達(dá)到輔助決策的效果。

目前，部分研究學(xué)者提出了經(jīng)典的Apriori關(guān)聯(lián)規(guī)則挖掘算法［3～5］，提出了股市中關(guān)聯(lián)規(guī)則挖掘方面的相關(guān)技術(shù)應(yīng)用。本文在具體探究中的研究目標(biāo)是挖掘頻繁項(xiàng)集中涉及到的Apriori算法，并將其改進(jìn)。針對股票板塊聯(lián)動(dòng)關(guān)聯(lián)規(guī)則挖掘這一問題，提出一種改進(jìn)的Apriori 算法。在目前傳統(tǒng)Apriori算法的基礎(chǔ)上改進(jìn)算法中數(shù)據(jù)庫的掃描次數(shù)，篩選出有用候選集，提高算法的利用效率。

2 改進(jìn)的Apriori算法

目前研究學(xué)者提出的改進(jìn)Apriori 算法［6～10］對掃描數(shù)據(jù)庫的次數(shù)與時(shí)間過程的考慮較少，對Apriori 算法的研究并沒有克服全部的局限性［11～15］，沒有做到將Apriori算法的運(yùn)算時(shí)間效率提高。

本文在深入研究傳統(tǒng)的Apriori算法的基礎(chǔ)上，提出一種改進(jìn)的Apriori-L 算法，優(yōu)化頻繁集的計(jì)算過程，提高算法的運(yùn)行時(shí)間效率，對二項(xiàng)頻繁集數(shù)目超過二項(xiàng)的頻繁集方面的操作在具體實(shí)踐應(yīng)用中起到關(guān)鍵性的意義。

2.1 算法描述

綜合性的結(jié)合Apriori 算法在學(xué)術(shù)界中相關(guān)的研究過程和現(xiàn)有的實(shí)驗(yàn)結(jié)果分析，可知算法在運(yùn)算掃描過程中耗費(fèi)時(shí)間多［16～20］，篩選候選集是s函數(shù)，同時(shí)也是計(jì)算支持度的函數(shù)和產(chǎn)生過頻繁項(xiàng)集的函數(shù)，進(jìn)一步分析算法在運(yùn)算過程中耗費(fèi)時(shí)間長的原因主要有以下兩方面：

1）候選集過多的問題。在頻繁集生成候選集的過程中，即由k-1生成k的過程中，利用關(guān)聯(lián)規(guī)則得到所有k 項(xiàng)集合作為候選集，部分K 項(xiàng)集存在對算法結(jié)果無用的現(xiàn)象。此時(shí)，這些無效的K 項(xiàng)集會(huì)造成算法時(shí)間的耗費(fèi)。

2）算法在整個(gè)掃描操作中會(huì)產(chǎn)生比較多的掃描次數(shù)。在相關(guān)的掃描事務(wù)集、支持度的分析與計(jì)算、頻繁集的獲取操作中，算法應(yīng)用中的循環(huán)次數(shù)與候選集數(shù)量兩者之間的關(guān)聯(lián)性有很強(qiáng)的關(guān)系，如果候選集的數(shù)量龐大，直接影響算法在運(yùn)行過程中的時(shí)間效果。

綜上所述，針對目前傳統(tǒng)Apriori算法在具體應(yīng)用中所存在的不足之處，本文結(jié)合實(shí)際問題制定出科學(xué)可行的改進(jìn)算法-Apriori-L 算法。改進(jìn)后算法的主要思路如下：

1）首先，將一項(xiàng)頻繁集L 獲取到，并與每一個(gè)事務(wù)集進(jìn)行合并操作，找出每個(gè)事務(wù)集中頻繁性小的數(shù)據(jù)，將其刪除，獲得W。

2）其次，在W中找出所有的二項(xiàng)子集cu。

3）再次，二項(xiàng)候選集z 由cu 生成，將二項(xiàng)候選集z 作為關(guān)鍵值存入一個(gè)h 表中。如果h 表中己經(jīng)存在將要存入的關(guān)鍵值，把與這個(gè)關(guān)鍵值相對應(yīng)的v值在應(yīng)用中加1處理；若h表中沒有所需存入相關(guān)關(guān)鍵值，需要把key 直接存儲在h 表中按照專業(yè)性的流程有效處理，同時(shí)將其對應(yīng)的v值變成1。

4）最后，在h 表中將關(guān)鍵值變成二項(xiàng)候選集z，關(guān)鍵值對應(yīng)的v即為該二項(xiàng)候選集z的支持度。

2.2 算法分析

假設(shè)事物集a中的事物項(xiàng)的數(shù)量為b，n為平均元素在事物項(xiàng)中，L1代表的是一項(xiàng)頻繁集在算法應(yīng)用中的實(shí)際數(shù)量。

假設(shè)O（n）指的是各個(gè)事物項(xiàng)在算法操作中和頻繁集所有時(shí)間的復(fù)雜度，O（Cn2）代表的是二元子集在具體操作中的時(shí)間復(fù)雜度情況，O（1）是指存入表與v值在操作中加1的時(shí)間復(fù)雜情況。

基于上述綜合性的分析可知，在進(jìn)行二項(xiàng)候選集Cz獲取時(shí)，將支持度進(jìn)行綜合性分析計(jì)算的操作過程中，Apriori-L的時(shí)間復(fù)雜度表示如下：

對上述步驟按照專業(yè)性的規(guī)范流程進(jìn)行掃描，即可有效地獲取到候選集的支持度h 表s，并對每一個(gè)候選集在算法應(yīng)用中的支持度和最小支持度關(guān)系的時(shí)間復(fù)雜度進(jìn)行判斷并表示如下：

由式（1）、（2）可知，Apriori-L 在生成二項(xiàng)頻繁集的過程中的時(shí)間復(fù)雜度為

通過綜合性的對比分析，能夠明確地推斷出Apriori 算法在形成二項(xiàng)頻繁集過程中的時(shí)間復(fù)雜度情況。

在進(jìn)行二項(xiàng)候選集C2 獲取的算法操作時(shí)所對應(yīng)的時(shí)間復(fù)雜度表示如下：

事務(wù)集的掃描、支持度的分析計(jì)算以及頻繁集選取所對應(yīng)的時(shí)間復(fù)雜度表示如下：

由式（4）、（5）可知，Apriori 算法在生成二項(xiàng)頻繁集的過程中的時(shí)間復(fù)雜度為

綜上所述，可知Apriori算法在運(yùn)算過程中比改進(jìn)的Apriori-L 算法需多運(yùn)算L21，對比分析Apriori算法與Apriori-L 算在的時(shí)間復(fù)雜度表示情況能夠明確的推斷出，Apriori-L算法在進(jìn)行二項(xiàng)頻繁集生成的操作中，能夠科學(xué)精確地獲取到L21/n 在算法應(yīng)用中的加速效果，可提高算法的使用效率。

Apriori算法在生成二項(xiàng)頻繁集時(shí)，時(shí)間復(fù)雜度與L12有重要的關(guān)系，一項(xiàng)頻繁集數(shù)量L1直接影響算法的運(yùn)行效率，如果L1數(shù)量特別多，則算法的使用效率變低。而在Apriori-L 算法中，生成二項(xiàng)頻繁集的過程與L1關(guān)聯(lián)性不大，與事務(wù)項(xiàng)中的元素平均數(shù)量n 的關(guān)聯(lián)性較強(qiáng)，n 作為事物集中的平均數(shù)量，n 小的情況下，該算法可以對算法的運(yùn)行效率產(chǎn)生較好的影響，即提高運(yùn)行效率。在實(shí)際生活中，有許多一項(xiàng)頻繁集數(shù)量大于事物集中平均元素?cái)?shù)量的基本現(xiàn)象。比如說，水果超市中銷售的水果類別要超過平均每一位顧客所選購的水果類別的實(shí)際數(shù)量。

3 Apriori-L算法的實(shí)際應(yīng)用

股票模塊是按照上市的股票進(jìn)行的分類，主要包括行業(yè)、概念、地區(qū)等方面，本文主要對30 個(gè)模塊采取科學(xué)的方式進(jìn)行關(guān)聯(lián)性分析操作。這些模塊在算法應(yīng)用中主要涉及到酒店餐飲、旅游、石油和電力等諸多專業(yè)性的模塊。把模塊聯(lián)動(dòng)看為一個(gè)模塊的漲和跌和另外一個(gè)模塊的漲和跌相互影響。對于投資者來說獲取模塊的聯(lián)動(dòng)信息的價(jià)值十分重要。利用經(jīng)驗(yàn)去判斷模塊間的關(guān)系缺乏科學(xué)依據(jù)，如旅游行業(yè)和酒店餐飲行業(yè)兩個(gè)模塊通過經(jīng)驗(yàn)可以分析出具有一定的關(guān)聯(lián)性，可是關(guān)聯(lián)的強(qiáng)度靠經(jīng)驗(yàn)較難判斷。現(xiàn)有的挖掘股票數(shù)據(jù)的方法主要有Apriori算法，利用此算法可以得出確切的模塊間聯(lián)動(dòng)信息，指導(dǎo)投資者進(jìn)行股市投資，幫助股市投資者及時(shí)規(guī)避風(fēng)險(xiǎn)。

本文在具體分析中采取科學(xué)的理論提出了改進(jìn)的Apriori算法，實(shí)踐操作中對各行業(yè)模塊間的所存在的關(guān)聯(lián)規(guī)則有效的挖掘，與以往探究板塊間關(guān)系的方法具有很大差別，本文在原有研究方法的基礎(chǔ)上，對不同模塊的漲跌幅度聯(lián)動(dòng)性結(jié)合實(shí)際情況綜合性的探究，根據(jù)在實(shí)踐應(yīng)用中的每一種漲跌幅其模塊之間的關(guān)聯(lián)性的數(shù)據(jù)挖掘，對于股市投資者全面明確模塊之間的聯(lián)動(dòng)的關(guān)聯(lián)規(guī)律起到直接性的促進(jìn)作用。

3.1 數(shù)據(jù)預(yù)處理

對板塊每一天的具體漲幅情況進(jìn)行綜合性的分析計(jì)算，深入化的探究海量的測試數(shù)據(jù)集在算法應(yīng)用中的數(shù)據(jù)分布狀況，將每個(gè)模塊的漲幅劃分為6 個(gè)部分：0＜幅度＜0.01；-0.01＜幅度＜0；0.01＜幅度＜0.03；-0.03＜幅度＜-0.01；幅度＞0.03；幅度＜-0.03。板塊的幅度在實(shí)踐操作中能夠均勻有序的歸入到這6 個(gè)種類中是主要的劃分準(zhǔn)則。按照專業(yè)性的規(guī)范標(biāo)準(zhǔn)將幅度區(qū)間有序的劃分，為每一個(gè)模塊所對應(yīng)的幅度區(qū)間合理的排號。表1 是每日的模塊數(shù)據(jù)的具體轉(zhuǎn)化情況。

表1 部分模塊數(shù)據(jù)

綜合性地把排號和數(shù)字6 科學(xué)的運(yùn)算所獲取到的值與數(shù)字6 中的某種狀態(tài)是相互對應(yīng)的。處理好的數(shù)據(jù)后存入到數(shù)據(jù)庫中。對處理后的數(shù)據(jù)采用sql進(jìn)行檢測，結(jié)果如下：

1）未在數(shù)據(jù)中發(fā)現(xiàn)空值、冗余值，2322 條記錄與2322 天30 個(gè)板塊指數(shù)的情況一一對應(yīng)，完整性良好。

2）利用統(tǒng)計(jì)方法，找出所有板塊每天的漲幅幾乎均落在6 種狀態(tài)下。因此可知漲幅區(qū)間的劃分是合理有效的。

3.2 頻繁項(xiàng)集

通過對不同的最小支持度的調(diào)整，對Apriori算法以及Apriori-L 算法分別科學(xué)的分析與挖掘數(shù)據(jù)的頻繁集。

基于各種支持度的實(shí)際情況可知，圖1 是原始Apriori 算法和Apriori-L 算法在二項(xiàng)頻繁集計(jì)算過程中相關(guān)運(yùn)行時(shí)間的具體示意圖。

圖1 不同支持度下的運(yùn)行時(shí)間

支持度320 下，Apriori算法和Apriori-L 算法在進(jìn)行關(guān)聯(lián)規(guī)則算法應(yīng)用中總時(shí)間和二項(xiàng)頻繁集時(shí)的時(shí)間計(jì)算的綜合性對比情況如下圖2 和圖3 所示，其中a為計(jì)算二項(xiàng)頻繁集時(shí)間，b 為計(jì)算關(guān)聯(lián)規(guī)則總時(shí)間。

圖2 Apriori算法

圖3 Apriori-L算法

由圖2、圖3 的實(shí)驗(yàn)結(jié)果可知，在支持度320下，改進(jìn)后的Apriori-L 算法相比較原Apriori 算法可提高算法中二次頻繁集的計(jì)算時(shí)間效率值約為81.5%，可提高算法總體運(yùn)行時(shí)間效率值約為78.5%。

綜上可知，Apriori-L算法的性能與原始Apriori算法相比有很強(qiáng)的優(yōu)勢，Apriori-L能夠在實(shí)踐應(yīng)用中展現(xiàn)出較強(qiáng)的算法功能特性。

3.3 計(jì)算關(guān)聯(lián)性

在實(shí)踐應(yīng)用中選取支持度320 下的相關(guān)頻繁集，結(jié)合實(shí)際需求將置信度設(shè)置為0.8，在此基礎(chǔ)上采取專業(yè)性的操作方式計(jì)算關(guān)聯(lián)規(guī)則，獲取到如表2所示的具體計(jì)算結(jié)果。

表2 部分模塊聯(lián)動(dòng)性

在計(jì)算關(guān)聯(lián)規(guī)則的綜合性操作過程中能夠有效地獲取到元件、導(dǎo)體、化纖這三個(gè)主要的板塊在漲幅區(qū)間中具體的關(guān)聯(lián)規(guī)則情況。如果元件漲幅超過0.03，導(dǎo)體模塊可能大于0.8001 的漲幅情況會(huì)超過0.03。所以投資者在觀察到元件漲幅超過0.03時(shí)，可以對導(dǎo)體模塊加強(qiáng)關(guān)注。

與根據(jù)模塊的是否漲跌來進(jìn)行關(guān)聯(lián)挖掘相比，新的基于漲跌幅關(guān)聯(lián)挖掘可以排除股市小幅正常漲幅的影響；獲得信息也更加具體精確，相同模塊中的不同漲跌幅度在一定程度上和不同的模塊會(huì)產(chǎn)生聯(lián)動(dòng)作用。

4 結(jié)語

對股市的歷史數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則的挖掘分析對股市的投資者具有重要的指導(dǎo)意義。Apriori 算法作為挖掘頻繁項(xiàng)集最重要的一種算法具有較好的意義，但是算法運(yùn)行效率有一定的缺陷性。本文提出的Apriori-L 算法先分析時(shí)間復(fù)雜性，再在分析的基礎(chǔ)上找出在人們?nèi)粘Ｉ钪械膶?shí)際性，在彌補(bǔ)算法不足的基礎(chǔ)上將算法應(yīng)用到實(shí)際中發(fā)現(xiàn)本文的方法對提高算法的運(yùn)行效率具有一定意義。本文將提出的算法應(yīng)用到股市模塊聯(lián)動(dòng)性的挖掘中，改進(jìn)后的Apriori算法能夠快速發(fā)現(xiàn)不同股票模塊的不同幅度之間的聯(lián)動(dòng)規(guī)則，可為股市投資者提供數(shù)據(jù)信息支持，為決策提供數(shù)據(jù)支撐。