［黎文娟 周忠眉］

1 引言

目前人工智能算法中比較流行的算法都是在大量數(shù)據(jù)的基礎(chǔ)上進(jìn)行分類的算法研究。帶標(biāo)簽的大量數(shù)據(jù)是進(jìn)行分類的基礎(chǔ)。大多數(shù)的人工智能算法都對(duì)計(jì)算機(jī)的運(yùn)算能力和運(yùn)算速度有很高的要求。一個(gè)好的分類算法希望能有比較準(zhǔn)確的分類的同時(shí)能夠盡量少占用系統(tǒng)資源和時(shí)間。關(guān)聯(lián)分類算法具有這兩方面的優(yōu)點(diǎn)。關(guān)聯(lián)分類算法雖然算法復(fù)雜度不高，但能夠挖掘出數(shù)據(jù)集中的大量關(guān)聯(lián)規(guī)則從而得到很好的分類準(zhǔn)確度。

關(guān)聯(lián)分類算法是大數(shù)據(jù)與人工智能領(lǐng)域的一種重要的分類算法[1～3]。主要原理是通過對(duì)帶標(biāo)簽的數(shù)據(jù)集進(jìn)行學(xué)習(xí)，挖掘關(guān)聯(lián)規(guī)則構(gòu)建分類器模型來對(duì)待預(yù)測(cè)實(shí)例進(jìn)行分類。目前已經(jīng)提出了許多基于關(guān)聯(lián)規(guī)則挖掘的分類算法，如CBA[4]、MCAR[5]、CMAR[6]算法。這些分類算法能挖掘出大量的規(guī)則并且具有較高的分類準(zhǔn)確率[7～10]，因而得到了廣泛地關(guān)注。

關(guān)聯(lián)分類算法雖然具有較好的分類效果，但是也存在以下一些不足：CBA、CMAR 算法都是基于支持度和置信度度量挖掘關(guān)聯(lián)規(guī)則，沒有考慮項(xiàng)集與類別之間的相關(guān)性，并且產(chǎn)生的規(guī)則數(shù)量龐大，其中有許多質(zhì)量不高的規(guī)則容易導(dǎo)致對(duì)預(yù)測(cè)實(shí)例的誤判。針對(duì)此問題許多學(xué)者對(duì)關(guān)聯(lián)分類算法進(jìn)行了改進(jìn)。Arunasalam.B 等人提出使用補(bǔ)類支持度CCS 度量[11]項(xiàng)集與類別之間的相關(guān)性，使用提升度對(duì)規(guī)則剪枝，能更有效地挖掘關(guān)聯(lián)規(guī)則。提出的CCCS 算法在多個(gè)數(shù)據(jù)集上有效地提高了分類準(zhǔn)確率。王衛(wèi)平等人在CCCS 算法的基礎(chǔ)上提出了改進(jìn)算法ACSER[12]，ACSER算法不僅考慮了項(xiàng)集在補(bǔ)類的支持度還考慮了項(xiàng)集在本類的支持度，使用增比率來度量項(xiàng)集與類之間的關(guān)系，有效地提高了規(guī)則質(zhì)量并比CCCS 算法具有更高的分類準(zhǔn)確率。雖然提升度、增比率能有效度量項(xiàng)集與類別之間的相關(guān)性，但提升度和增比率受數(shù)據(jù)集數(shù)據(jù)總量的影響非常大，其值波動(dòng)范圍很大不穩(wěn)定，因而在實(shí)際運(yùn)用中難以有效確定提升度和增比率的閾值，導(dǎo)致在一些數(shù)據(jù)集上分類準(zhǔn)確率不理想。

針對(duì)提升度和增比率度量存在的問題，本文提出的改進(jìn)算法IACD（Improved association classification algorithm based on Cosine Degree）在度量項(xiàng)集與類別的相關(guān)性時(shí)使用了一種新的度量——余弦度量，余弦度量?jī)H受項(xiàng)集和類別支持度影響不受數(shù)據(jù)總量的影響，能更好地反映項(xiàng)集與類別之間的關(guān)系。本文算法有以下幾個(gè)特點(diǎn)。

（1）提取規(guī)則時(shí)同時(shí)考慮了規(guī)則的置信度和余弦度量?jī)煞N度量以提高規(guī)則質(zhì)量。

（2）提出了一種新的規(guī)則強(qiáng)度對(duì)規(guī)則進(jìn)行排序、剪枝以減少冗余規(guī)則的數(shù)量。

（3）預(yù)測(cè)時(shí)選取最優(yōu)的K條規(guī)則計(jì)算規(guī)則強(qiáng)度，避免出現(xiàn)新實(shí)例被單條規(guī)則誤判的情況。

實(shí)驗(yàn)結(jié)果表明IACD 算法在多個(gè)數(shù)據(jù)集上平均分類準(zhǔn)確率高于幾種改進(jìn)的關(guān)聯(lián)分類算法。

2 相關(guān)理論

lift用來度量項(xiàng)集X與類Ci之間的關(guān)聯(lián)程度，lift值為1 代表項(xiàng)集X與類Ci之間相互獨(dú)立，lift值越大代表項(xiàng)集X與類Ci之間關(guān)聯(lián)程度越高，一條規(guī)則的值受訓(xùn)練集實(shí)例數(shù)目影響很大，其取值范圍在。

Cosine同樣用來度量項(xiàng)集X與類Ci之間的關(guān)聯(lián)程度，值為0.5 代表項(xiàng)集X與類Ci不相關(guān)。Cosine與lift值的區(qū)別在于Cosine對(duì)分母開了根號(hào)，其度量值僅受支持度的影響，不受數(shù)據(jù)集實(shí)例數(shù)的影響,具有零不變性且其取值范圍在。

3 IACD 分類算法

本節(jié)首先介紹了IACD 算法的各個(gè)主要步驟，其次詳細(xì)說明IACD 算法使用余弦度量的優(yōu)勢(shì)，最后給出算法的偽代碼。

3.1 IACD 算法主要步驟

3.1.1 規(guī)則挖掘

IACD 算法采用類apriori 算法根據(jù)支持度挖掘頻繁項(xiàng)集，其次對(duì)其中每一個(gè)頻繁項(xiàng)集計(jì)算到各類的置信度，生成滿足置信度閾值的候選規(guī)則。接著計(jì)算每一條候選規(guī)則的余弦度量，滿足余弦度量閾值的候選規(guī)則加入規(guī)則集。

剪枝時(shí)，IACD 算法計(jì)算規(guī)則集中每一條規(guī)則的Cos strength強(qiáng)度，然后按照Cos strength強(qiáng)度對(duì)所有規(guī)則排序，如果該規(guī)則覆蓋的所有實(shí)例均已被優(yōu)先級(jí)較高的實(shí)例正確分類，則剪枝掉該規(guī)則。

3.1.2 未知實(shí)例預(yù)測(cè)

IACD 算法在分類新實(shí)例時(shí)，掃描規(guī)則集，將規(guī)則集中與新實(shí)例匹配的規(guī)則最優(yōu)K條規(guī)則取出，然后把這些規(guī)則按照類標(biāo)簽劃分，并計(jì)算每一條規(guī)則的Cos strength規(guī)則強(qiáng)度，最后對(duì)每個(gè)類標(biāo)簽所屬的規(guī)則計(jì)算平均強(qiáng)度，將平均強(qiáng)度最大的類標(biāo)簽賦予新實(shí)例。

3.2 余弦度量的優(yōu)勢(shì)及算法偽代碼

表1 顯示了一組數(shù)據(jù)集和兩種度量提升度以及余弦度量的評(píng)價(jià)結(jié)果。

表1 訓(xùn)練數(shù)據(jù)集

在D1和D2兩個(gè)數(shù)據(jù)集中，XCi明顯大于因此項(xiàng)集X 和類標(biāo)簽Ci是正相關(guān)的，但是根據(jù)公式計(jì)算提升度可以發(fā)現(xiàn)，在D2中項(xiàng)集X 和類標(biāo)簽Ci變成不相關(guān)的，這顯然與事實(shí)不符，而在D3中，XCi明顯小于和所以項(xiàng)集X 和類標(biāo)簽Ci應(yīng)該是負(fù)相關(guān)的，可是提升度計(jì)算得出的結(jié)果是正相關(guān)的。同理在D4中，XCi、這三者是一樣的，因此項(xiàng)集X 和類標(biāo)簽Ci是不相關(guān)的，但是提升度計(jì)算得出卻是強(qiáng)正相關(guān)的。

從上面幾個(gè)例子可以看出，提升度受數(shù)據(jù)總量的影響非常大，使用提升度判斷項(xiàng)集與類別的相關(guān)性會(huì)存在失真的情況，而使用本文中的余弦度量可以真實(shí)地判斷出項(xiàng)集與類別之間的相關(guān)性。

IACD 算法的偽代碼如圖1 所示。

圖1 IACD 算法步驟

其中，第4步是挖掘頻繁項(xiàng)集，第5步是生成關(guān)聯(lián)規(guī)則，第6 步則是對(duì)規(guī)則集剪枝，第7 步是對(duì)規(guī)則集進(jìn)行排序。

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)使用的實(shí)驗(yàn)環(huán)境搭載Microsoft Windows10（64 bit）操作系統(tǒng)，運(yùn)行Java 8.0 編程環(huán)境下進(jìn)行，實(shí)驗(yàn)利用了16組具有不同特點(diǎn)的UCI 數(shù)據(jù)集：austral、Breast、cleve、Diabetes、heart、pima、labor、Iris、horse、glass、sonar、tic-tac、wine、Led7、vehicle、zoo，這些數(shù)據(jù)集都是大數(shù)據(jù)與人工智能方面的經(jīng)典抽象數(shù)據(jù)集。數(shù)據(jù)集如表2 所示。表2 分別給出了每組數(shù)據(jù)集的屬性數(shù)目、類別數(shù)目及實(shí)例總數(shù)。實(shí)驗(yàn)中，對(duì)每組數(shù)據(jù)集實(shí)驗(yàn)均采用10 折交叉驗(yàn)證方法，以減小隨機(jī)性。本實(shí)驗(yàn)采用分類準(zhǔn)確率來評(píng)價(jià)所有算法的分類性能。

表2 實(shí)驗(yàn)所用的數(shù)據(jù)集

4.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)參數(shù)設(shè)置如下：在IACD 算法中，設(shè)置置信度閾值為0.80，支持度閾值為0.05，余弦度量閾值閾值為0.7。其 他 對(duì) 比 算 法：CBA、CMAR、CPAR、CCCS、ACSER的分類準(zhǔn)確率均來自參考文獻(xiàn)。

實(shí)驗(yàn)結(jié)果如表3 所示，從實(shí)驗(yàn)結(jié)果可以看出，在所使用的16 個(gè)數(shù)據(jù)集上，IACD 算法在10 個(gè)數(shù)據(jù)集上分類準(zhǔn)確率高于其他所有對(duì)比算法，同時(shí)IACD 算法較其他算法取得最高的平均分類準(zhǔn)確率。因此可以得出結(jié)論余弦度量有效地度量項(xiàng)集與類別之間的關(guān)系，提高了規(guī)則質(zhì)量。并且在多種數(shù)據(jù)集的準(zhǔn)確率都比較高，具有一定的通用性。

5 總結(jié)

針對(duì)基于支持度和置信度度量的關(guān)聯(lián)分類算法無法度量類別和項(xiàng)集之間的相關(guān)性的問題，本文提出了基于余弦度量關(guān)聯(lián)分類的改進(jìn)算法IACD。IACD 算法在挖掘關(guān)聯(lián)規(guī)則時(shí)使用余弦度量來衡量項(xiàng)集與類別間的相關(guān)性以提高生成規(guī)則的質(zhì)量并減少冗余規(guī)則的數(shù)量。實(shí)驗(yàn)結(jié)果從測(cè)試的幾個(gè)不同特點(diǎn)的典型數(shù)據(jù)集來看，IACD 算法在多個(gè)數(shù)據(jù)集上比幾種經(jīng)典的關(guān)聯(lián)分類改進(jìn)算法具有更高的分類準(zhǔn)確率。

表3 IACD 算法與多種算法的準(zhǔn)確率對(duì)比