一種改進關聯分類算法的研究

苗世強， 鄭曉勢

(齊魯工業大學 信息學院， 濟南 250353)

引言

關聯分類算法是數據分析的一個領域，代表的算法有：CBA[1]、CMAR[2]、CPAR[3]等。這里，本文將對關聯分類CBA算法展開如下詳述與分析。首先，要通過對頻繁項集的挖掘，找到頻繁項集，而后在此基礎上進行關聯分類。分類原則就是按照給定已知屬性，再借此判斷屬于哪一類別。

1 基本定義與關聯分類算法

1.1 概念介紹

設數據集合I={i1,i2,…,im}，有事務集合transaction-D，D中每項事務T是數據集I的子集，則有T?I。其中，單個事務T都關聯對應著一個TID。為方便后續研究，首先探討本次研究中的重點概念定義如下。

定義1頻繁項集 就是在某些集合中，一些事務集中出現了相同的數據項，這些數據項的出現頻率是非常高的。在這些集合中，滿足一定閾值的集合可稱為頻繁項集。

定義2支持度 在某個集合中既出現項集A又出現B的概率,即：

Support(A→B)=P(A∪B)

(1)

定義3置信度 就是假設數據項A出現的同時，數據項B有多大幾率出現，即：

Confidence(A→B)=P(A|B)

(2)

1.2 CBA算法

CBA算法是建立在關聯規則上的分類算法，主要分為CBA-RG和CBA-CB兩個過程。過程內容可分述如下。

1.2.1 CBA-RG

CBA-RG算法的核心思想是采用迭代方法，從候選集中來產生頻繁項集。具體步驟如下：

(1)設定最小的支持度。

(2)掃描整個數據庫中的事務集數據，產生候選集合，同時生成了候選一項集C1。

(3)從候選一項集中，找出滿足大于設定最小支持度的數據，保留得到頻繁一項集K1，并刪除不滿足的數據。

(4)利用得到的L1去生成候選集合C2。

(5)根據設定的最小支持度生成頻繁項集K2。

(6)迭代生成頻繁項集K，直至不能再繼續為止。

1.2.2 CBA-CB

該算法主要通過如下步驟來構造其分類器。對其可得闡釋解析如下。

(1)選取高置信度的規則優先插入到分類器中，同時刪除前規則、連同其覆蓋的數據對象。假設該規則沒有覆蓋任何對象，則不進入分類器。

(2)將該分類器中不能繼續增加準確率的規則開展剪枝處理，生成最后的分類器規則。

2 一種改進的關聯分類算法ACW設計

研究中，假設數據庫中存在事務F={F1,F2,F3,…,Fn}，類L={l1,l2,l3,…,ln}，數據條目D={D1,D2,…,Dn}。其中，每個數據D={D1,D2,…,Dn}在類L中都有一個從屬類別。單數據對應的類L可能有多個。事務F對應的數據條目總數為{n1,n2,n3,…,nk}。

對于數據條目D1，分屬的類別可能包含有{l1,l2,l3,…,ln}。研究時將D1∈l1的次數設為a1。D2∈l2的次數設為a2。以此類推到an。同時，將這些數據條目出現的次數記為A={t1,t2,t3,…,tn},再設sum={t1+t2+t3+…+tn}，則D1∈{l1,l2,l3,…,ln}的類權重表示為{t1/sum,t2/sum,t3/sum,…,tn/sum}，并記作s1。將D2∈{l1,l2,l3,…,ln}的類權重表示為{t1/sum,t2/sum,t3/sum,…,tn/sum}，并記作s2。以此類推，Dn∈{l1,l2,l3,…,ln}的類別集合權重為{t1/sum,t2/sum,t3/sum,…,tn/sum}記作sn。最后，集合L={l1,l2,l3,…,ln}權重可推斷設置為{(s1+s2+…+sn)/n1,(s1+s2+s3+…+sn)/n2，…，(s1+s2+s3+…+sn)/nk}。將計算得到的結果記為w{wi1,wi2,wi3,…,win}，同時，把所有數據條目權重設為a，其中0

定義4數據條目D={D1,D2, …,Dn}的加權支持度[4]為：

(3)

定義5形如規則X?Y的加權支持度為：

(4)

定義6規則X?Y的加權置信度為:

(5)

(1)先不考慮數據庫中數據條目的權重，利用CBA-RG產生出所有的最大屬性的方法，在數據庫中找到所有大于設定的最小加權支持度數據。由于加權支持度小于支持度，很容易知道這些屬性集合是大加權屬性集合的超集。

(2)根據公式(3)～(5)計算超集中所有數據條目及類的加權支持度，同時乘以相應的數據權重。刪除了加權支持度低于最小加權支持度的數據，生成所有加權屬性大的數據集。

(3)生成最終關聯分類數據條目。輸入相關數據條目，并依據運行結果，得到最終類別。

3 實驗數據分析

該算法使用的硬件環境配置為：CPU為Core i5-7500、3.4 GHz，內存為2 GB，硬盤500 GB。系統環境為Window7。研究時，從UCI上下載了樣本數據集。本程序采用Java運行實現。該程序的測試樣本數據flare是從UCI數據集下載。實驗中，涉及到的類別數據內容可見表1。

表1 樣本數據集合介紹Tab. 1 Introduction of sample data set

過程中，在未執行算法前，對一些數據進行了預處理，把一些連續數據離散化，同時刪除了部分干擾數據。隨后啟動算法運行，分別從算法執行準確度和運行時間進行了分析，最終運行效果如圖1、圖2所示。

圖1 設定不同最小支持度的準確度Fig. 1 The accuracy with different minsupport settings

圖2 設定不同最小支持度的運行時間Fig. 2 Running time with different minsupport settings

4 結束語

本文針對現有的關聯分類算法，設計提出了一種基于類權重改進的ACW算法。結合UCI上的數據，并對算法性能進行了測試。實驗表明，改進后的ACW算法是一種有效的、穩定的關聯分類算法。

[1] 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: ACM, 1998:1-7.

[2] LI Wenmin, HAN Jiawei, PEI Jian. CMAR: Accurate and efficient classification based on multiple class-association rules[C]//Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on. San Jose, CA, USA:IEEE, 2001: 369-376.

[3] YIN Xiaoxin, HAN Jiawei. CPAR: Classification based on predictive association rules[C]//Proceedings of the 2003 SIAM International Conference on Data Mining. San Francisco, CA, USA：Society for Industrial and Applied Mathematics, 2003: 331-335.

[4] 李成軍,楊天奇. 一種改進的加權關聯規則挖掘方法[J]. 計算機工程,2010,36(7):55-57.

[5] 陳曉云,胡運發. 基于自適應加權的文本關聯分類[J]. 小型微型計算機系統,2007，28(1):116-121.

[6] 張健,王蔚. 基于支持度與置信度閾值優化技術的關聯分類算法[J]. 計算機應用,2007，27(12):3032-3034，3038.

[7] 蔡永泉,晉月培,葛安生,等. 基于關聯分類的中文短信分類[J]. 北京工業大學學報,2015,41(7):1020-1027.