關聯分類算法的研究與實現

苗世強 鄭曉勢

摘 要： 關聯分類算法是對數據進行分析處理中的一個分支。文中結合了關聯分類CBA算法，針對數據集樣本進行了詳細分析。首先，對關聯分類中的CBA算法進行了研究，并同步對其實現的代碼進行了編寫。隨后，結合相關數據，運行相關算法進行實現與分析。最終，對該樣本數據進行了有效地分類和預測，也完成了算法的有效實現與分析。

關鍵詞： 關聯；關聯分類；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 關聯和分類算法簡介

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

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

顧名思義，關聯規則就是對數據集合中挖掘出一些關聯性強的數據，即頻繁項集，整個過程需要挖掘出符合設定的最小支持度的數據。關聯分類算法，作為二者的結合，就是通過對關聯規則的挖掘，并以此為基礎來設計實現分類操作。

2 關聯分類CBA算法

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

CBA算法是建立在關聯規則上的分類算法，重點分為CBA-RG和CBA-CB兩個操作進程。具體內容如下：

（1）CBA-RG主要用于產生類關聯規則數據集合。在該階段利用關聯規則算法運行發現類關聯規則集合，同時還要設定給出最小支持度和置信度。通過掃描數據庫，生成滿足最小支持度和置信度的數據集合。

（2）CBA-CB主要就是構建分類器。在該過程對上述產生的規則數據提供了進一步的排序研究，并且選擇具有高置信度的規則優先插入到分類器中。最后，根據該分類器，對數據進行分類。

3 關鍵步驟代碼實現

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

輸出：關聯分類結果

4 實驗與結果分析

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

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

由圖1、圖2可知，在選用數據集car、led7、cmc的情況下，當設定不同的最小支持度時，對算法的準確性和運行時間均會帶來一定的調控影響。

5 結束語

著重研究了關聯分類中的CBA算法，并編譯實現了該算法。結合UCI數據集上下載數據，通過成功設計編寫本文算法，輸入部分測試的樣本數據項，完成了對數據的關聯分類和預測?；诖?，還對算法分別從準確度以及性能方面進行了測試與分析，并獲得了合理、有效的研究成果。

參考文獻

[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]. 計算機應用與軟件，2010，27（8）：241-243，254.

[7] 張明衛，朱志良，劉瑩，等. 一種大數據環境中分布式輔助關聯分類算法[J]. 軟件學報，2015，26（11）：2795-2810.

[8] 王熙照，趙東壘. 基于規則興趣度的關聯分類[J]. 計算機工程與應用，2007，43（25）：168-171.

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