關(guān)聯(lián)分類(lèi)算法的研究與實(shí)現(xiàn)

苗世強(qiáng) 鄭曉勢(shì)

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

關(guān)鍵詞： 關(guān)聯(lián)；關(guān)聯(lián)分類(lèi)；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)和分類(lèi)算法簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(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] 禹蒲陽(yáng). CBA分類(lèi)算法的一種改進(jìn)[J]. 計(jì)算機(jī)應(yīng)用與軟件，2010，27（8）：241-243，254.

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

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

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