使用多支持度的關(guān)聯(lián)規(guī)則分類算法

黃亞東 劉 淵

(江南大學(xué)數(shù)字媒體學(xué)院 江蘇 無錫 214122)

使用多支持度的關(guān)聯(lián)規(guī)則分類算法

黃亞東 劉 淵

(江南大學(xué)數(shù)字媒體學(xué)院 江蘇 無錫 214122)

傳統(tǒng)關(guān)聯(lián)分類算法使用單一最小項(xiàng)目支持度挖掘關(guān)聯(lián)規(guī)則，導(dǎo)致稀有項(xiàng)關(guān)聯(lián)規(guī)則無法被發(fā)現(xiàn)，從而影響分類的準(zhǔn)確性和實(shí)用性。提出一種多支持度關(guān)聯(lián)規(guī)則分類算法MS-CBAR(Multiple Supports-Classification Based on Association Rules)，將多最小項(xiàng)目支持度模型應(yīng)用于關(guān)聯(lián)分類，以有效挖掘稀有項(xiàng)。該算法為數(shù)據(jù)庫中的規(guī)則項(xiàng)提供了用戶可定義的最小項(xiàng)目支持度。MS-CBAR算法使用項(xiàng)的最小項(xiàng)支持度閾值、類的最小類支持度值和規(guī)則項(xiàng)的最小支持度值決定分類規(guī)則是否頻繁。生成分類規(guī)則集后，使用最高優(yōu)先度規(guī)則覆蓋法基于規(guī)則集建立分類器。實(shí)驗(yàn)表明，所提算法在包含稀有項(xiàng)目及稀有類的數(shù)據(jù)集中準(zhǔn)確率高于傳統(tǒng)關(guān)聯(lián)分類算法及其相關(guān)算法，表現(xiàn)更穩(wěn)定。

數(shù)據(jù)挖掘 多最小項(xiàng)目支持度 基于關(guān)聯(lián)的分類算法 MS-CBAR

0 引 言

分類規(guī)則挖掘和關(guān)聯(lián)規(guī)則挖掘是兩種重要的數(shù)據(jù)挖掘技術(shù)。關(guān)聯(lián)規(guī)則[1]挖掘旨在發(fā)現(xiàn)數(shù)據(jù)庫中滿足最小項(xiàng)目支持度和最小置信度閾值的所有頻繁規(guī)則。分類規(guī)則[2]挖掘使用訓(xùn)練集構(gòu)建分類器預(yù)測新數(shù)據(jù)對象的類標(biāo)簽。

基于關(guān)聯(lián)的分類算法CBA(Classification Based on Associations)[3]將分類規(guī)則挖掘與關(guān)聯(lián)規(guī)則挖掘結(jié)合，構(gòu)建更為準(zhǔn)確的分類器。CBA分兩步建立分類器：第一步使用CBA-RG(CBA-Rule Generator)算法挖掘滿足最小項(xiàng)目支持度和最小置信度閾值的所有類關(guān)聯(lián)規(guī)則；第二步在CBA-RG算法生成的類關(guān)聯(lián)規(guī)則上建立分類器。實(shí)驗(yàn)表明，CBA算法比C4.5算法的準(zhǔn)確率更高。由于每個(gè)事務(wù)中的不同項(xiàng)和不同類可能重要程度不同，而CBA算法對數(shù)據(jù)庫中的事務(wù)采用單一最小項(xiàng)支持度閾值，因而限制了算法的實(shí)際應(yīng)用。例如對包含100個(gè)項(xiàng)目、2個(gè)類(健康和疾病)、10 000個(gè)事務(wù)的衛(wèi)生狀況數(shù)據(jù)集，“疾病”稀有類的真實(shí)支持度為1%，稀有項(xiàng)“發(fā)熱”真實(shí)支持度為2%。如果將最小項(xiàng)支持度設(shè)置為20%，稀有項(xiàng)“發(fā)熱”和稀有類“疾病”將被剪枝，與其相關(guān)的規(guī)則無法被發(fā)掘。而稀有項(xiàng)“發(fā)熱”和稀有類“疾病”對研究健康狀況有重要作用。為了發(fā)掘稀有項(xiàng)和稀有類，我們可以將最小項(xiàng)支持度設(shè)置為0.5%，但是會(huì)引起項(xiàng)組合爆炸，耗費(fèi)大量計(jì)算資源，得到諸多無意義的關(guān)聯(lián)規(guī)則，即“稀有項(xiàng)”問題。

稀有項(xiàng)問題會(huì)產(chǎn)生低質(zhì)量的類關(guān)聯(lián)規(guī)則集。如果類關(guān)聯(lián)規(guī)則集不包含稀有項(xiàng)，那么基于類關(guān)聯(lián)規(guī)則集建立的分類器無法覆蓋測試集中包含稀有項(xiàng)的事務(wù)，影響了分類器的準(zhǔn)確性。合適的類關(guān)聯(lián)規(guī)則集是影響關(guān)聯(lián)分類器準(zhǔn)確性的關(guān)鍵因素。

為了提高CBA算法的分類準(zhǔn)確性，文獻(xiàn)[4]利用FP-Growth算法建立類關(guān)聯(lián)分布樹FP-tree，該算法采用分類規(guī)則樹結(jié)構(gòu)有效地存儲(chǔ)關(guān)聯(lián)規(guī)則并基于置信度、相關(guān)性和數(shù)據(jù)庫覆蓋來剪枝。分類的具體執(zhí)行采用加權(quán)值來分析。文獻(xiàn)[5]通過整合關(guān)聯(lián)規(guī)則分類和傳統(tǒng)的基于規(guī)則分類的優(yōu)點(diǎn)，提出一種預(yù)測關(guān)聯(lián)算法。該算法在規(guī)則生成時(shí)采用貪心算法策略，采用Laplace準(zhǔn)確性評價(jià)規(guī)則，在預(yù)測時(shí)應(yīng)用最優(yōu)的規(guī)則，避免產(chǎn)生冗余的規(guī)則。同時(shí)，采用一種動(dòng)態(tài)方法避免在規(guī)則生成時(shí)的重復(fù)計(jì)算，有效避免過擬合，產(chǎn)生所有候選項(xiàng)集的效率較高。

不同于上述文獻(xiàn)[4-5]，本文從解決稀有項(xiàng)問題出發(fā)，提出了一種新的使用多支持度MS(Multiple Supports)[6]的關(guān)聯(lián)規(guī)則分類算法，稱為多支持度關(guān)聯(lián)分類規(guī)則算法MS-CBAR，提高分類器的準(zhǔn)確性。算法為每個(gè)類和每個(gè)項(xiàng)目提供用戶可定義的最小支持度，且不會(huì)產(chǎn)生大量無意義的類關(guān)聯(lián)規(guī)則。

1 基于關(guān)聯(lián)的分類算法

基于關(guān)聯(lián)的CBA分類算法分兩步建立分類器。第一步使用規(guī)則生成算法挖掘滿足最小項(xiàng)目支持度和最小置信度閾值的所有類關(guān)聯(lián)規(guī)則；第二步使用算法生成的類關(guān)聯(lián)規(guī)則建立分類器。

設(shè)T為一個(gè)含有m個(gè)事務(wù)的數(shù)據(jù)集。每個(gè)事務(wù)都有一個(gè)分類y。設(shè)I={i1,i2,…,in}為T中所有項(xiàng)目的集合，Y為所有分類標(biāo)識(shí)，且有I∩Y=?，一個(gè)分類關(guān)聯(lián)規(guī)則是指如下形式的關(guān)系：

X→yX?Iy∈Y

X稱為規(guī)則前件，y為規(guī)則后件。支持度和置信度的定義和Apriori[1]算法一致。分類關(guān)聯(lián)規(guī)則挖掘是指生成完整的滿足用戶指定的最小支持度minsup(minimum support)和最小置信度minconf(minimum confidence)限制的CAR集合。

1.1 生成分類關(guān)聯(lián)規(guī)則

CBA-RG的關(guān)鍵操作是找出所有支持度高于最小支持度閾值的規(guī)則項(xiàng)。一個(gè)規(guī)則項(xiàng)可以表示成如下形式：

(condset,y)

condset→y

上述規(guī)則的支持度為：

其中n為T中事務(wù)的總數(shù)量，置信度為：

滿足最小支持度的規(guī)則項(xiàng)稱為頻繁規(guī)則項(xiàng)，其余的稱為非頻繁規(guī)則項(xiàng)。

生成分類關(guān)聯(lián)規(guī)則的算法為CAR-Apriori算法。CAR-Apriori算法需要多次遍歷數(shù)據(jù)來生成所有頻繁規(guī)則項(xiàng)。在第一次遍歷中，算法計(jì)算每個(gè)1-規(guī)則項(xiàng)(即在條件集中只包含一個(gè)項(xiàng)目的規(guī)則項(xiàng))的支持計(jì)數(shù)(算法L1行)。所有1-候選規(guī)則項(xiàng)的集合為：

C1={({i},y)|i∈I,y∈Y}

C1只是簡單地將I中的每個(gè)項(xiàng)目和類標(biāo)相關(guān)聯(lián)。通過循環(huán)遍歷，生成k-候選規(guī)則項(xiàng)的集合Ck。在對數(shù)據(jù)集的掃描過程中更新每個(gè)k-候選規(guī)則項(xiàng)的真實(shí)支持計(jì)數(shù)。數(shù)據(jù)掃描結(jié)束后，將具有相同分類的規(guī)則項(xiàng)通過合并其條件集進(jìn)行合并，算法決定Ck中候選k-規(guī)則項(xiàng)是否頻繁。

1.2 建立分類器

我們使用文獻(xiàn)[3]的方法建立分類器。令CBA-RG步驟生成的分類關(guān)聯(lián)規(guī)則集為S，訓(xùn)練數(shù)據(jù)集為D。建立分類器的思想是從S中選擇一個(gè)可以覆蓋數(shù)據(jù)集D的規(guī)則集L(?S)，L中的規(guī)則的選擇時(shí)基于S中各個(gè)規(guī)則的排序，另外L中包含一個(gè)默認(rèn)類。

1.3 CBA算法的不足

在CBA算法中，單一最小項(xiàng)目支持度可能無法滿足需求。在實(shí)際的分類數(shù)據(jù)集中的類分布可能非常不均勻，一個(gè)類占據(jù)數(shù)據(jù)集中大多數(shù)數(shù)據(jù)，而另外一個(gè)類占比很小。單一最小項(xiàng)支持度使得包含小數(shù)據(jù)集的稀有項(xiàng)的CAR無法被發(fā)現(xiàn)，影響基于CAR集構(gòu)建的分類器的準(zhǔn)確性。為挖掘包含稀有項(xiàng)的CAR，同時(shí)避免生成大量無意義的規(guī)則，本文提出了采用多支持度關(guān)聯(lián)分類規(guī)則算法。該算法可使用：

(1) 多最小分類支持度，用戶可以針對不同的類分別指定不同的最小支持度；

(2) 多最小項(xiàng)支持度，用戶可以對每個(gè)項(xiàng)指定一個(gè)最小支持度值(可以是分類項(xiàng)或者非分類項(xiàng))。

2 多支持度關(guān)聯(lián)規(guī)則分類算法

2.1 相關(guān)定義

定義1設(shè)I={i1,i2, …,in}為項(xiàng)目集，MIS(ip)表示項(xiàng)ip的最小項(xiàng)支持度MIS(Minimum Item Support)值。項(xiàng)集A={i1,i2,…,ik}(1≤k≤n)的MIS定義為[6]：

MIS(A)=min[MIS(i1),MIS(i2),…,MIS(ik)]

在Apriori算法中，只有一個(gè)最小項(xiàng)支持度，所有頻繁模式集都滿足向下封閉性。即一個(gè)項(xiàng)集是頻繁的，那么它的所有子集也都是頻繁的。在多最小項(xiàng)目支持度模型算法中，向下封閉性就不再適用，即一個(gè)頻繁項(xiàng)集的某些子集可能是非頻繁的。

根據(jù)文獻(xiàn)[6]提出的排序封閉性規(guī)則，假設(shè)項(xiàng)集中的所有項(xiàng)按照各自的MIS值升序排列，該項(xiàng)集任何超集的MIS值都等于該項(xiàng)集第一項(xiàng)的MIS值。如果低于其第一項(xiàng)的MIS值，該項(xiàng)目集是非頻繁的，其任何超集都不會(huì)是頻繁的。

基于上述性質(zhì)，MS-Apriori可以通過減少搜索空間來挖掘所有符合多最小項(xiàng)目支持度的頻繁項(xiàng)集。MS-Apriori 中的所有項(xiàng)先根據(jù)MIS值升序排列再剪枝。同時(shí)，由于某些項(xiàng)集的支持度是不確定的，MS-Apriori還需要計(jì)算所有頻繁項(xiàng)集子集的支持度。

通過為各項(xiàng)指定不同最小項(xiàng)目支持度，為只包含頻繁項(xiàng)目的規(guī)則項(xiàng)指定高最小項(xiàng)目支持度，為包含稀有項(xiàng)目的規(guī)則指定較低的最小項(xiàng)目支持度。對稀有類，同理。

2.2 MS-CBAR算法描述

MS-CBAR算法分兩步建立分類器。具體的過程說明如下。

輸出：頻繁規(guī)則項(xiàng)集Lk

L2 L1= {{i}|i∈I, rulesupCount (i) ≥MRS(i)}；

L3 for (k=2;Lk-1≠?;k++)

L4 ifk=2 then

L5C2=level2_candidate_gen (L1)

L6 elseCk= mscbar_candidate_gen (Lk-1)

L8 for eachc∈Ckdo

L9 mrs = get-MRS(c)

L10 if rulesupCount(c) ≥ mrs then

L11 insertcintoLk;

L12 end

L13 end

L14 return ∪Lk

在多最小項(xiàng)目支持度概念中，向下封閉性不再適用，頻繁規(guī)則項(xiàng)集的子集不一定是頻繁的。為了生成完整的候選規(guī)則集，本文提出采用多最小項(xiàng)支持度生成兩個(gè)候選集。

算法2level2_candidate_gen (L1)

輸出：候選2-規(guī)則集C2

L1C2=?

L2 for each rule-item (ia,y1) inL1in the same order do

L3 for each rule-item (ib,y1) inL1that is after (ia,y1) do

L4 ifia≠ibthen

L5C2= ∪ ({ia,ib},y1);

L6 end

L7end

算法3mscbar_candidate_gen(Lk-1)

輸出：候選k-規(guī)則集Ck，k>2

L1Ck=?;

L5 else

L7 end

L8 returnCk

MS-CBAR采用候選生成與測試方法來發(fā)現(xiàn)所有頻繁規(guī)則項(xiàng)，需要證明候選生成方法的完整性。MS-CBAR算法采用多支持度的概念，所有頻繁規(guī)則項(xiàng)必須滿足排序封閉性。頻繁規(guī)則項(xiàng)α的任何子規(guī)則項(xiàng)β也是頻繁規(guī)則項(xiàng)，如果滿足MRS(β) =MRS(α)。若rulesupCount(β) ≥MRS(α)，rulesupCount(β)也滿足MRS(β) =MRS(α)，β也是頻繁項(xiàng)集。該屬性確保侯選生成與測試的方法是可行的，所有k-候選規(guī)則項(xiàng)都可以由(k-1)-子規(guī)則項(xiàng)生成。

2) 第二步是基于類關(guān)聯(lián)規(guī)則集建立分類器的過程。從每個(gè)分區(qū)匯總所有頻繁規(guī)則項(xiàng)及其頻繁項(xiàng)計(jì)數(shù)。最后，根據(jù)頻繁規(guī)則項(xiàng)及其相應(yīng)計(jì)數(shù)組建分類器。構(gòu)建分類器算法如下：

算法4分類器

輸入：規(guī)則集S，訓(xùn)練數(shù)據(jù)集D

輸出：規(guī)則集列表(分類器)L

L1S= sort(S);

//根據(jù)優(yōu)先度>對S中的規(guī)則排序

L2L=φ;

L3 for each ruler∈Sin sequence do

L4 ifD≠? ANDr在D中至少正確覆蓋一個(gè)事務(wù) then

L5 從D中刪除所有被r覆蓋的事務(wù);

L6 將r添加至L的尾部;

L7 end

L8 end

L9 將測試集中計(jì)數(shù)最多的類標(biāo)簽作為默認(rèn)類加入L的尾部。

其中，規(guī)則排序的定義如下。

定義4對于兩個(gè)規(guī)則，ri和rj，當(dāng)滿足以下條件時(shí)，ri>rj：

(1)ri比rj具有更高的置信度；

(2)ri比rj具有相同的置信度，ri比rj具有更高的支持度；

(3)ri與rj具有相同的置信度和支持度，產(chǎn)生較早的規(guī)則，排名較高。

最終的L具有以下的形式：

L=

其中，ri∈S，如果b>a則ra?rb。在進(jìn)行測試數(shù)據(jù)分類時(shí)，第一個(gè)能夠覆蓋測試用例的類作為這個(gè)用例的分類。如果任何一個(gè)規(guī)則都無法覆蓋該用例，那么用例屬于默認(rèn)類(default_class)。

3 實(shí)驗(yàn)評估

3.1 實(shí)驗(yàn)準(zhǔn)備

為了驗(yàn)證本文算法的有效性，本文從UCI機(jī)器學(xué)習(xí)庫網(wǎng)站上選擇了10個(gè)數(shù)據(jù)集，其中5個(gè)含有稀有項(xiàng)或稀有類。Annealing為退火數(shù)據(jù)集，稀有類為“1”；Breast Cancer為乳腺癌數(shù)據(jù)集，稀有類為“Malignant”；Diabetes為糖尿病數(shù)據(jù)集；German Credit為德國信用數(shù)據(jù)集，稀有類為“Bad”；Horse為馬絞痛數(shù)據(jù)集；Iris為鳶尾花數(shù)據(jù)集；Lymphography為淋巴系造影術(shù)數(shù)據(jù)集，稀有類為“fibrosis”；Vehicle為車輛輪廓數(shù)據(jù)集；Waveform為波形發(fā)射器數(shù)據(jù)集；Zoo為動(dòng)物園數(shù)據(jù)集，稀有類為“5”。這10個(gè)數(shù)據(jù)集均適合于多重變量分析與分類準(zhǔn)確性研究。各數(shù)據(jù)集的屬性如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集屬性

實(shí)驗(yàn)運(yùn)行在一臺(tái)macOS Sierra系統(tǒng)的MacBook Pro上，處理器為2.5 GHz Intel Core i7，內(nèi)存為16 GB。算法使用Java語言實(shí)現(xiàn)。在實(shí)驗(yàn)中，將C4.5、CBA算法和基于CBA算法改進(jìn)的CMAR算法加入對比實(shí)驗(yàn)。C4.5算法使用機(jī)器學(xué)習(xí)軟件WEKA 3.8.0實(shí)現(xiàn)；CBA和CMAR和CPAR算法采用其各自文獻(xiàn)中的實(shí)現(xiàn)方式。在所有實(shí)驗(yàn)中，采用K折交叉驗(yàn)證來計(jì)算所提出的方法的準(zhǔn)確性。將準(zhǔn)確性定義為：

其中Acc表示準(zhǔn)確性，本實(shí)驗(yàn)中取k=10。

為了全面衡量MS-CBAR分類器的性能，除準(zhǔn)確性指標(biāo)，還有查準(zhǔn)率(Precision，P)、查全率(Recall，R)、F1值以及宏平均等指標(biāo)。

查準(zhǔn)率(P)定義為：

查全率(R)定義為：

F1值定義為：

宏平均查準(zhǔn)率(MacroP)：

宏平均查全率(MacroR)：

宏平均F1(MacroF1)：

為了在MS-CBAR中的每個(gè)項(xiàng)上產(chǎn)生最小項(xiàng)值，采用文獻(xiàn)[6]中提出的方法，考慮項(xiàng)的實(shí)際出現(xiàn)頻率作為MIS值分配的基礎(chǔ)。方程表述如下：

M(ip)=σ×f(ip) 0≤ip≤1

f(ip)表示項(xiàng)ip∈I在數(shù)據(jù)庫中出現(xiàn)的次數(shù)，MRSall表示所有項(xiàng)中的最小MIS值。σ(0≤σ≤1)可以用于控制在挖掘過程中MIS值的作用。如果σ設(shè)置為0，所有項(xiàng)具有相同的MIS值(即MRSall)，會(huì)產(chǎn)生與傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘相同的結(jié)果。如果σ設(shè)置為1且M(ip) ≥MRSall，f(ip)就是ip的MIS值。

對于稀有類cls，我們將其MCS值定義為：

MS-CBAR算法中，稀有類和稀有項(xiàng)目的MCS及MIS值如表2所示。除稀有類以外的項(xiàng)目MIS值為1%，MCS值為10%。MS-CBAR算法的置信度閾值設(shè)置為50%。

表2 包含稀有項(xiàng)目數(shù)據(jù)集的MIS/MCS值

對于CBA算法，設(shè)置支持度閾值為1%，置信度閾值為50%，不限制規(guī)則數(shù)。CMAR算法的支持度和置信度閾值與CBA算法相同。數(shù)據(jù)集覆蓋閾值為4，置信度差別閾值為20%。

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

本文首先選用10個(gè)數(shù)據(jù)集樣本分別運(yùn)行C4.5、CBA、CMAR 、CPAR和MS-CBAR 5種分類算法。其中，C4.5算法是經(jīng)典的分類決策樹算法, 用信息增益率來選擇屬性, 在決策樹構(gòu)造過程中進(jìn)行剪枝，防止過擬合現(xiàn)象發(fā)生；CBA算法用關(guān)聯(lián)規(guī)則挖掘算法發(fā)現(xiàn)頻繁規(guī)則項(xiàng)，再基于規(guī)則項(xiàng)構(gòu)建分類器；CMAR算法在CBA算法基礎(chǔ)上使用FP-tree提升分類規(guī)則生成效率，并基于置信度、相關(guān)性和數(shù)據(jù)庫覆蓋剪枝。CPAR算法則在CBA基礎(chǔ)上提出預(yù)測關(guān)聯(lián)算法，預(yù)測時(shí)應(yīng)用最優(yōu)的規(guī)則，避免產(chǎn)生冗余的規(guī)則。本文提出的MS-CBAR算法則利用多支持度模型改進(jìn)頻繁規(guī)則項(xiàng)的生成過程，提高分類器的準(zhǔn)確性。

從表3中可以看出，本文所提出的算法在10個(gè)數(shù)據(jù)單獨(dú)表現(xiàn)并非最優(yōu)，但平均準(zhǔn)確度最高平均分類準(zhǔn)確率最高。對于包含稀疏項(xiàng)的數(shù)據(jù)集準(zhǔn)確率比其他算法高。對于不包含稀疏項(xiàng)的數(shù)據(jù)集來說，由于數(shù)據(jù)集中數(shù)據(jù)樣本分布的不均衡，在不同數(shù)據(jù)集的性能也不同。同時(shí)，由于設(shè)置多支持度閾值，可能在部分?jǐn)?shù)據(jù)集當(dāng)中不同閾值的設(shè)定也會(huì)影響分類的準(zhǔn)確率。

表3 各分類器準(zhǔn)確性 %

對于5種分類算法在包含稀有項(xiàng)的5個(gè)數(shù)據(jù)集中的準(zhǔn)確性如圖1所示。可以看出，在5個(gè)包含稀有項(xiàng)目、稀有類的數(shù)據(jù)集中，本文所提出算法的準(zhǔn)確度高于C4.5、CBA、CMAR和CPAR算法。在其他數(shù)據(jù)集中，MS-CBAR算法表現(xiàn)穩(wěn)定，其準(zhǔn)確性整體優(yōu)于CBA算法，與CMAR準(zhǔn)確性接近。在分類時(shí)準(zhǔn)確率有所提升，但是提升幅度不大，由于數(shù)據(jù)集當(dāng)中的稀有項(xiàng)數(shù)據(jù)并非大量存在，本文算法在包含稀有項(xiàng)的數(shù)據(jù)集中準(zhǔn)確率最優(yōu)。

圖1 包含稀有項(xiàng)目的數(shù)據(jù)集分類器對比

為了驗(yàn)證本文算法的有效性，本文通過對MacroP、MacroR、MacroF1分別進(jìn)行分析，從表4可以看出，在多分類的問題上，本文提出的算法對于帶有稀疏項(xiàng)的數(shù)據(jù)分類效果更好。

表4 各分類器宏平均查準(zhǔn)率，宏平均查全率和宏F1在各數(shù)據(jù)集上的對比 %

4 結(jié) 語

在CBA算法中，稀有項(xiàng)問題使單個(gè)最小項(xiàng)目支持度很難發(fā)現(xiàn)包含稀有項(xiàng)的規(guī)則。本文提出將多最小項(xiàng)目支持度模型整合進(jìn)分類器的算法-MS-CBAR算法。與傳統(tǒng)多最小項(xiàng)目支持度方法不同，本文提出使用三個(gè)因素-項(xiàng)的MIS值、類的MCS值、規(guī)則項(xiàng)的MRS值-決定分類規(guī)則。實(shí)驗(yàn)結(jié)果顯示，當(dāng)數(shù)據(jù)集中存在稀有項(xiàng)時(shí)，MS-CBAR算法表現(xiàn)更好。

在下一步的研究中，我們可以采用本文提出的算法需要生成候選規(guī)則項(xiàng)集，但是在生成頻繁規(guī)則項(xiàng)集階段采用決策樹學(xué)習(xí)的方法，考慮定義在特征空間上與類空間上的條件概率。根據(jù)損失函數(shù)最小化的原則建立決策樹，無需生成候選規(guī)則項(xiàng)集，節(jié)約存儲(chǔ)空間，提升算法效率。

[1] Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//Proc.20th int. conf. very large data bases,VLDB.1994,1215:487-499.

[2] Quinlan J R.C4.5:programs for machine learning[M].Morgan Kaufmann Publishers Inc.1993.

[3] Liu B,Hsu W,Ma Y.Integrating classification and association rule mining[C]//International Conference on Knowledge Discovery and Data Mining.AAAI Press,1998:80-86.

[4] Li W,Han J,Pei J.CMAR:Accurate and Efficient Classification Based on Multiple Class-Association Rules[C]//IEEE International Conference on Data Mining.2001:19-21.

[5] Han J,Yin X.CPAR:Classification based on Predictive Association Rules[J].SDM,2003:331-335.

[6] Liu B.Mining association rules with multiple minimum supports[C]//ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM,1970:337-341.

[7] Liu B,Ma Y,Wong C K.Classification Using Association Rules:Weaknesses and Enhancements[J].Massive Computing,2001,2:591-605.

[8] Koh Y S,Ravana S D.Unsupervised Rare Pattern Mining:A Survey[J].ACM Transactions on Knowledge Discovery from Data (TKDD),2016,10(4):45.

[9] Pang-Ning Tan,Michael Steinbach,Vipin Kumar.數(shù)據(jù)挖掘?qū)д揫M].范明,范宏建,譯.人民郵電出版社,2011.

[10] 吳信東.數(shù)據(jù)挖掘十大算法[M].清華大學(xué)出版社,2013.

[11] 劉兵.Web數(shù)據(jù)挖掘[M].俞勇,譯.2版.清華大學(xué)出版社,2013.

[12] 王秀枝,安建成.基于支持度和置信度智能優(yōu)化的關(guān)聯(lián)分類算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(11):184-186.

[13] 薛福亮,馬莉.利用動(dòng)態(tài)產(chǎn)品分類樹改進(jìn)的關(guān)聯(lián)規(guī)則推薦方法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(4):135-141.

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

[15] Rai D,Verma K S,Thoke A.Classification Algorithm based on MS Apriori for Rare Classes[J].International Journal of Computer Applications,2012,48(22):52-56.

[16] 李學(xué)明,楊陽,秦東霞,等.基于頻繁閉項(xiàng)集的新關(guān)聯(lián)分類算法ACCF[J].電子科技大學(xué)學(xué)報(bào),2012,41(1):104-109.

[17] 吳小波,徐維祥.多支持度關(guān)聯(lián)規(guī)則在網(wǎng)絡(luò)使用挖掘中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(31):164-167.

[18] 劉華婷,郭仁祥,姜浩.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件,2009,26(1):146-149.

ACLASSIFICATIONALGORITHMBASEDONASSOCIATIONRULESWITHMULTIPLESUPPORTS

Huang Yadong Liu Yuan

(SchoolofDigitalMedia,JiangnanUniversity,Wuxi214122,Jiangsu,China)

Traditional association classification algorithm uses single minimum item support to mining association rules, resulting in rare item association rules hard to find, thus affecting the accuracy of the classifier and practicality. Therefore, we propose a multiple support association rule classification MS-CBAR algorithm (Multiple Supports-Classification Based on Association Rules). Besides, the multi-minimum project support model is applied to association classification to effectively exploit the rare items. This algorithm provided user-definable minimum item support for both rule items and classes in the database. Then, the MS-CBAR algorithm adopted the minimum item support threshold, the minimum class support value of the class and the minimum support value of the rule items to determine whether the classification rules are frequent. Finally, after generating the classification rule set, the top priority rule coverage method was used to build the classifier based on the rule set. Experimental result demonstrates the proposed algorithm is more accurate than traditional association classification algorithms in data sets with rare items and rare classes. And its related algorithms are more stable.

Data mining Multiple minimum item support Classification algorithm based on association MS-CBAR

TP391

A

10.3969/j.issn.1000-386x.2017.09.048

2016-11-23。國家科技支撐計(jì)劃項(xiàng)目(2015BAH54F00)；國家自然科學(xué)基金項(xiàng)目(61672264)；國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB0800305)。黃亞東，碩士，主研領(lǐng)域：數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)。劉淵，教授。