苗世強(qiáng) 鄭曉勢

摘 要： 關(guān)聯(lián)分類算法是對數(shù)據(jù)進(jìn)行分析處理中的一個分支。文中結(jié)合了關(guān)聯(lián)分類CBA算法，針對數(shù)據(jù)集樣本進(jìn)行了詳細(xì)分析。首先，對關(guān)聯(lián)分類中的CBA算法進(jìn)行了研究，并同步對其實現(xiàn)的代碼進(jìn)行了編寫。隨后，結(jié)合相關(guān)數(shù)據(jù)，運(yùn)行相關(guān)算法進(jìn)行實現(xiàn)與分析。最終，對該樣本數(shù)據(jù)進(jìn)行了有效地分類和預(yù)測，也完成了算法的有效實現(xiàn)與分析。

關(guān)鍵詞： 關(guān)聯(lián)；關(guān)聯(lián)分類；CBA算法

Abstract：Classification algorithm based on association rules is a branch of data analysis and processing. In this paper the CBA algorithm is used to analyze the detailed sample data. First of all the CBA algorithm is studied and the code of CBA algorithm is realized synchronously. After that combined with the relevant data it is designed to run the CBA algorithm for analysis. Finally the sample data are effectively classified and predicted the algorithm implementation and analysis are also completed.

Key words： association；classification based on association rules；CBA algorithm

1 關(guān)聯(lián)和分類算法簡介

關(guān)聯(lián)規(guī)則和分類方法作為大數(shù)據(jù)分析和處理中的2個分支，一直得到了廣泛的研究與應(yīng)用。其中，分類就是通過已有的分類技術(shù)，實際地構(gòu)造出一個分類器模型，在此基礎(chǔ)上繼續(xù)進(jìn)行分類分析。其中比較典型的算法就是決策樹算法和貝葉斯分類算法。而關(guān)聯(lián)規(guī)則就是通過對頻繁數(shù)據(jù)的挖掘，進(jìn)而找到關(guān)聯(lián)性強(qiáng)的規(guī)則集合。

決策樹是一種代表性的分類算法，也是一種歸納學(xué)習(xí)算法。具體來說，決策樹中的標(biāo)志性算法主要有ID3[1]、C4.5[2]、CART算法[3]。決策樹算法的基本思想是，從最上端到下端開始使用貪心算法，繼而遞歸調(diào)用搜索樣本集，并在每個測試候選集上展開測試，最終構(gòu)造出決策樹。貝葉斯分類算法是一種基于統(tǒng)計學(xué)的分類算法。通過給定的數(shù)據(jù)，結(jié)合貝葉斯分類來預(yù)測樣本數(shù)據(jù)屬于一個指定類的發(fā)生概率。

顧名思義，關(guān)聯(lián)規(guī)則就是對數(shù)據(jù)集合中挖掘出一些關(guān)聯(lián)性強(qiáng)的數(shù)據(jù)，即頻繁項集，整個過程需要挖掘出符合設(shè)定的最小支持度的數(shù)據(jù)。關(guān)聯(lián)分類算法，作為二者的結(jié)合，就是通過對關(guān)聯(lián)規(guī)則的挖掘，并以此為基礎(chǔ)來設(shè)計實現(xiàn)分類操作。

2 關(guān)聯(lián)分類CBA算法

研究中，將對關(guān)聯(lián)分類CBA算法[4]展開如下設(shè)計論述。過程中，關(guān)聯(lián)分類的第一步就是通過已有的數(shù)據(jù)結(jié)合關(guān)聯(lián)規(guī)則算法，產(chǎn)生頻繁項集數(shù)據(jù)，找到類關(guān)聯(lián)規(guī)則。在此基礎(chǔ)上將轉(zhuǎn)入分類處理中。分類的原理思路就是按照支持度與置信度的不同構(gòu)造分類器，然后進(jìn)行分類。挖掘頻繁項集的步驟就是通過關(guān)聯(lián)規(guī)則Apriori算法[5]挖掘得到了頻繁項。假設(shè)一項集中含有該已知的屬性，同時含有分類的該屬性的值，隨后在該算法中通過計算此頻繁項是否能通過已知的屬性值來推導(dǎo)出決策的屬性值的關(guān)聯(lián)規(guī)則。如果該規(guī)則滿足設(shè)定的最小置信度，那么就把該頻繁項集中的決策屬性的值作為最終的分類結(jié)果。

CBA算法是建立在關(guān)聯(lián)規(guī)則上的分類算法，重點分為CBA-RG和CBA-CB兩個操作進(jìn)程。具體內(nèi)容如下：

（1）CBA-RG主要用于產(chǎn)生類關(guān)聯(lián)規(guī)則數(shù)據(jù)集合。在該階段利用關(guān)聯(lián)規(guī)則算法運(yùn)行發(fā)現(xiàn)類關(guān)聯(lián)規(guī)則集合，同時還要設(shè)定給出最小支持度和置信度。通過掃描數(shù)據(jù)庫，生成滿足最小支持度和置信度的數(shù)據(jù)集合。

（2）CBA-CB主要就是構(gòu)建分類器。在該過程對上述產(chǎn)生的規(guī)則數(shù)據(jù)提供了進(jìn)一步的排序研究，并且選擇具有高置信度的規(guī)則優(yōu)先插入到分類器中。最后，根據(jù)該分類器，對數(shù)據(jù)進(jìn)行分類。

3 關(guān)鍵步驟代碼實現(xiàn)

輸入：所有的事務(wù)集，最小支持度MinSup

輸出：關(guān)聯(lián)分類結(jié)果

4 實驗與結(jié)果分析

該算法選用的計算機(jī)硬件環(huán)境如下：CPU為Core i5-7500，3.4 GHz，內(nèi)存為2 GB；操作系統(tǒng)為Window7；采用的開發(fā)語言為Java。使用的數(shù)據(jù)測試集合是從UCI上真實下載，該程序測試的樣本數(shù)據(jù)分別為：car、led7、cmc。由于在這些數(shù)據(jù)中，存在著一些連續(xù)、且冗余的數(shù)據(jù)，在算法尚未開啟執(zhí)行時，需要對此中數(shù)據(jù)進(jìn)行預(yù)處理。對一些存在連續(xù)性的數(shù)據(jù)轉(zhuǎn)換為離散化，同時對干擾數(shù)據(jù)實現(xiàn)了部分刪除，保證了數(shù)據(jù)的質(zhì)量。處理后的數(shù)據(jù)內(nèi)容信息可見表1。

隨后，將應(yīng)用本次研究選取的測試樣本數(shù)據(jù)來設(shè)計執(zhí)行算法，并分別從算法執(zhí)行準(zhǔn)確度和運(yùn)行時間進(jìn)行了分析。在算法運(yùn)行過程中，測試了不同最小支持度下對算法精確度和運(yùn)行時間的作用影響。本文研究算法的綜合測試效果對比可詳見圖1、圖2。

由圖1、圖2可知，在選用數(shù)據(jù)集car、led7、cmc的情況下，當(dāng)設(shè)定不同的最小支持度時，對算法的準(zhǔn)確性和運(yùn)行時間均會帶來一定的調(diào)控影響。

5 結(jié)束語

著重研究了關(guān)聯(lián)分類中的CBA算法，并編譯實現(xiàn)了該算法。結(jié)合UCI數(shù)據(jù)集上下載數(shù)據(jù)，通過成功設(shè)計編寫本文算法，輸入部分測試的樣本數(shù)據(jù)項，完成了對數(shù)據(jù)的關(guān)聯(lián)分類和預(yù)測。基于此，還對算法分別從準(zhǔn)確度以及性能方面進(jìn)行了測試與分析，并獲得了合理、有效的研究成果。

參考文獻(xiàn)

[1] QUINLAN J R. Induction of decision trees[J]. Machine learning 1986 1（1）： 81-106.

[2] QUINLAN J R. C4. 5：Programs for machine learning[J]. Machine Learning，1994，16（3）：235-240.

[3] BREIMAN L REIEDMAN J H OLSHEN R A et al. Classification and regression trees[M]. New York： Chapman & Hall 1984.

[4] LIU Bing HSU W MA Yiming. Integrating classification and association rule mining[C]//Proceedings of the fourth international conference on knowledge discovery and data mining. New York：AAAI 1998：1-7.

[5] AGRAWAL R IMIELINSKI T SWAMI A. Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD Conference. Washington DC USA： ACM 1993：1-10.

[6] 禹蒲陽. CBA分類算法的一種改進(jìn)[J]. 計算機(jī)應(yīng)用與軟件，2010，27（8）：241-243，254.

[7] 張明衛(wèi)，朱志良，劉瑩，等. 一種大數(shù)據(jù)環(huán)境中分布式輔助關(guān)聯(lián)分類算法[J]. 軟件學(xué)報，2015，26（11）：2795-2810.

[8] 王熙照，趙東壘. 基于規(guī)則興趣度的關(guān)聯(lián)分類[J]. 計算機(jī)工程與應(yīng)用，2007，43（25）：168-171.

[9] 武建華，沈鈞毅，方加沛. 提取有效規(guī)則的關(guān)聯(lián)分類算法[J]. 西安交通大學(xué)學(xué)報，2009，43（4）：22-25.