［黎文娟 周忠眉］

1 引言

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

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

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

針對提升度和增比率度量存在的問題，本文提出的改進算法IACD（Improved association classification algorithm based on Cosine Degree）在度量項集與類別的相關性時使用了一種新的度量——余弦度量，余弦度量僅受項集和類別支持度影響不受數據總量的影響，能更好地反映項集與類別之間的關系。本文算法有以下幾個特點。

（1）提取規(guī)則時同時考慮了規(guī)則的置信度和余弦度量兩種度量以提高規(guī)則質量。

（2）提出了一種新的規(guī)則強度對規(guī)則進行排序、剪枝以減少冗余規(guī)則的數量。

（3）預測時選取最優(yōu)的K條規(guī)則計算規(guī)則強度，避免出現新實例被單條規(guī)則誤判的情況。

實驗結果表明IACD 算法在多個數據集上平均分類準確率高于幾種改進的關聯(lián)分類算法。

2 相關理論

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

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

3 IACD 分類算法

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

3.1 IACD 算法主要步驟

3.1.1 規(guī)則挖掘

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

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

3.1.2 未知實例預測

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

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

表1 顯示了一組數據集和兩種度量提升度以及余弦度量的評價結果。

表1 訓練數據集

在D1和D2兩個數據集中，XCi明顯大于因此項集X 和類標簽Ci是正相關的，但是根據公式計算提升度可以發(fā)現，在D2中項集X 和類標簽Ci變成不相關的，這顯然與事實不符，而在D3中，XCi明顯小于和所以項集X 和類標簽Ci應該是負相關的，可是提升度計算得出的結果是正相關的。同理在D4中，XCi、這三者是一樣的，因此項集X 和類標簽Ci是不相關的，但是提升度計算得出卻是強正相關的。

從上面幾個例子可以看出，提升度受數據總量的影響非常大，使用提升度判斷項集與類別的相關性會存在失真的情況，而使用本文中的余弦度量可以真實地判斷出項集與類別之間的相關性。

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

圖1 IACD 算法步驟

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

4 實驗及結果分析

4.1 實驗設計

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

表2 實驗所用的數據集

4.2 實驗結果及分析

實驗參數設置如下：在IACD 算法中，設置置信度閾值為0.80，支持度閾值為0.05，余弦度量閾值閾值為0.7。其 他 對 比 算 法：CBA、CMAR、CPAR、CCCS、ACSER的分類準確率均來自參考文獻。

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

5 總結

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

表3 IACD 算法與多種算法的準確率對比