基于演進向量量化聚類的增量模糊關聯分類方法

霍緯綱，屈 峰，程 震

(中國民航大學 計算機科學與技術學院，天津 300300)

基于演進向量量化聚類的增量模糊關聯分類方法

霍緯綱*，屈 峰，程 震

(中國民航大學 計算機科學與技術學院，天津 300300)

為了提高動態數據集上模糊關聯分類器(FAC)的建模效率，提出了一種基于演進向量量化(eVQ)聚類的增量模糊關聯分類方法。首先，采用eVQ聚類算法增量更新數量屬性上的高斯隸屬度函數參數；然后，擴展早剪枝更新(UWEP)算法，使之適用于增量挖掘模糊頻繁項；最后，以模糊相關度(FCORR)和分類規則前件長度為度量方式裁剪并更新模糊關聯分類規則庫。在4個UCI標準數據集上的實驗結果表明, 與批量模糊關聯分類建模方法相比，所提方法能夠在保證分類精度和解釋性的前提下，減少模糊關聯分類器的訓練時間；基于eVQ的高斯隸屬度函數的增量更新有助于提高動態數據集上模糊關聯分類器的分類精度。

增量學習；模糊關聯分類；演進向量量化聚類；早剪枝更新；高斯隸屬度函數

0 引言

模糊關聯分類器(Fuzzy Associative Classifier, FAC)是數據挖掘領域重要的分類方法之一[1]，因其較高的分類準確度和較好的解釋性受到了研究人員的關注[2-7]。文獻[2]采用多間隔離散化方法確定模糊區間，然后基于改進的FP-Growth算法挖掘模糊頻繁項，生成模糊關聯分類規則(Fuzzy Associative Classification Rule，FACR); 文獻[3]將信息熵的概念引入到數據模糊化的過程中，采用規則覆蓋方法篩選模糊關聯分類規則; 文獻[4]以模糊相關度(Fuzzy CORRelation, FCORR)作為衡量分類規則質量的標準對分類規則庫進行精簡以提高FAC的解釋性; 文獻[5]將AdaBoost.M1W集成學習算法應用于FAC構建過程中以提高FAC在多類不平衡數據情形下的分類性能; 在應用方面，文獻[6]基于模糊關聯分類器進行民用飛機超限事件診斷; 文獻[7]使用模糊關聯分類模型進行遙感圖像分類。上述方法用于在靜態數據集上建立高效的模糊關聯分類模型，對于動態數據集，當有新數據加入到初始數據集時，上述批量模糊關聯分類建模方法需要在更新后的數據集上重新訓練FAC，這種重復學習產生的時空開銷降低了FAC的構建效率。目前對FAC的增量更新研究工作相對較少。

FAC是一類基于規則的模糊分類器。針對如何在流動態數據上構建模糊分類器，研究者們做了很多工作[8-11]。文獻[8]基于eVQ(evolving Vector Quantization)聚類算法和T-S(Takagi-Sugeno)模型提出了一種數據驅動的在線模糊回歸模型FLEXFIS(Flexible Fuzzy Inference System)。文獻[9]基于FLEXFIS提出模糊分類模型FLEXFIS-Class，該模型單模結構中規則的前件與T-S模糊系統的規則前件相同，規則的后件為類標簽；多模結構為每種類別樣本訓練一個T-S模糊回歸模型，其規則前件與單模結構中規則的前件相同，規則的后件是分類超平面。文獻[10]提出了基于eTS(evolving T-S fuzzy system)的模糊分類模型eClass，該模型與FLEXFIS-Class相比最大特點在于，以規則年齡(Rule Age)為指標識別數據概念偏移，根據數據概念偏移情況自動調整分類模型參數及其結構。文獻[11]從局部學習模糊分類規則后件函數參數、處理流數據中概念漂移和異常點等方面提高eClass和FLEXFIS-Class兩類在線模糊分類模型的分類準確率和魯棒性。由于流數據具有實時、連續、有序、無限等特征[12]，上述在線模糊分類模型在增量學習過程中不需要考慮使用初始數據集而只是采用最新時間窗口中的數據修正分類器。

與上述流動態數據上模糊分類模型不同，本文在增量學習過程中綜合考慮初始數據集和新加入的數據，從隸屬度函數和模糊關聯分類規則庫兩個方面實現FAC的增量更新。該方法的基本思想：初始訓練階段，使用eVQ聚類算法生成數量屬性的高斯隸屬度函數，基于Apriori算法挖掘模糊頻繁項并生成模糊關聯分類規則庫。增量學習階段，利用eVQ聚類算法自身的進化機制更新高斯隸屬度函數參數，然后對早剪枝更新(Update With Early Pruning, UWEP)算法進行擴展，增量挖掘模糊頻繁項。最后以FCORR和分類規則前件長度作為度量方式裁剪更新模糊關聯分類規則庫。

1 基于eVQ的增量模糊關聯分類器構建

1.1 高斯隸屬度函數增量更新

由數量屬性的隸屬度函數表示的模糊區間決定了FAC的分類精度，所以確定隸屬度函數是FAC建模的一項重要預處理工作。文中采用eVQ聚類算法對初始數據集進行聚類分析，將聚類中心點投影到各個數量屬性，得到單個數量屬性的高斯隸屬度函數參數。當新數據加入時，再由eVQ聚類算法實現各個數量屬性的高斯隸屬度函數增量更新。

設初始訓練集DB=[XY],X=[xk, j]M×N表示在N個數量屬性上的M個取值，Y=[yk]M×1為類別屬性上的M個取值。增量數據集記為db=[X′Y′],其中X′=[xk, j]L×N，Y′=[yk]L×1，DB∪db表示DB與db合并后的數據集。在DB上由eVQ聚類算法生成s個類簇，第i個類簇中心點記作Ci=[ci,1,ci,2,…,ci,N](1≤i≤s)，ci, j表示第i個類簇中心點在第j個數量屬性上投影，ki表示第i個類簇中數據樣本個數，采用式(1)表示第j個屬性上第i個模糊區間對應的高斯隸屬度函數。

(1)

其中:δi, j表示第j(1≤j≤N)個屬性上第i(1≤i≤s)個模糊區間的范圍。

(2)

(cwin, j-xk, j)2

(3)

Δcwin, j=cwin, j′-cwin, j; 1≤j≤N

(4)

基于eVQ聚類算法的高斯隸屬度函數更新方法詳細描述如下：

輸入 增量數據集db，原始數據集DB上生成的s個類簇中心點，s×N個模糊區間對應的高斯隸屬度函數參數ci, j,δi, j(1≤i≤s,1≤j≤N)，確定類簇數目的閾值ρ。

Fork=1,2,…,s

End For

Form=1,2,…,L

Fork=1,2,…,s

End For

Ifdmin>ρ，Then

else

Forj=1,2,…,N

用式(2)把第win個聚類中心在第j個屬性上的投影更新為cwin, j′；

用式(3)把第win個聚類中心在第j個屬性上確定的模糊區間范圍更新為δwin, j′。

End For

End If

End For

1.2 基于UWEP算法的增量模糊頻繁項挖掘

UWEP(Update With Early Pruning)[13]是一種針對布爾型頻繁項的增量挖掘算法，本文對UWEP算法進行擴展，使其可以增量挖掘模糊頻繁項，主要擴展點為：1)通過閾值θ篩選出各個屬性上變化較明顯的模糊集，從LDB中剔除由這些模糊集生成的模糊1-頻繁項及其相應的超集；2)同一數量屬性擴展而來的模糊項不能被組合生成模糊頻繁項。算法主要步驟如下：

步驟1 計算s×N個模糊區間對應的高斯隸屬度函數參數ci, j的變化范圍Δci, j(1≤i≤s,1≤j≤N)，若Δci, j大于預設閾值θ，則將參數ci, j對應的高斯隸屬度函數所表示的1-模糊項CItem加入ChangedFItem中，若CItem∈LDB，則從LDB中刪除CItem及其超集。

模糊關聯分類規則庫的增量更新過程為：

步驟1 由新模糊頻繁項集合中帶有類標簽的模糊頻繁項生成新分類規則集RuleBasenew。

步驟2 刪除初始FAC的分類規則集RuleBase中不屬于RuleBasenew的FACR，將RuleBasenew中不屬于RuleBase的FACR加入到RuleBase。

步驟3 采用文獻[4]中以FCORR和FACR前件長度為度量方式的規則庫精簡方法對RuleBase進行裁剪得到更新后的模糊關聯分類規則庫RuleBase′。

增量更新與裁剪初始分類規則庫RuleBase的具體算法描述如下：

輸入 模糊關聯分類規則庫RuleBase，RuleBasenew。

輸出 精簡后的分類規則庫RuleBase′。

ForRuleBase中每個模糊關聯分類規則R

IfR?RuleBasenew, Then

從RuleBase中刪除R

End If

End For

ForRuleBasenew中每個模糊關聯分類規則Rnew

IfRnew?RuleBase，Then

將Rnew加入到RuleBase中

End If

End For

在RuleBase中掃描不同類別中每種長度的FACR，將具有最大FCORR的FACR加入規則集RuleBase′，RuleBase′中最長規則的長度記作Len。

Do untilLen=2

For 每個模糊關聯分類規則RLen(RLen∈RuleBase′)

IfRLen-1∈RuleBase′并且RLen的前件包含RLen-1的前件

IfFCORR(RLen-1)>FCORR(RLen)，Then

從RuleBase′中刪除RLen

End If

End If

Len=Len-1

End For

End Do

RuleBase′中最長規則的長度記作Len′

Do untili=Len′

For 每個模糊關聯分類規則Ri(Ri∈RuleBase′)

IfRi+1∈RuleBase′并且Ri+1的前件包含Ri的前件

IfFCORR(Ri+1)>FCORR(Ri)，Then

從RuleBase′中刪除Ri

End If

End If

i=i+1

End For

End Do

2 算法復雜度分析與實驗結果

2.1 算法復雜度分析

2.2 實驗結果

為了驗證文中增量模糊關聯分類器建模方法的有效性，實驗選取UCI(http://archive.ics.uci.edu/ml/datasets.html)機器學習數據集中的4個數據集進行測試，數據集的詳細信息如表1所示。

實驗中以最少類別樣本在訓練樣本集中出現頻率的0.1倍為最小模糊支持度, 采用多類別規則投票方式[4]為分類推理引擎。eVQ算法中閾值ρ按式(5)[14]計算：

(5)

其中：p為訓練樣本集維數，fac為調節因子，文中在實驗過程中以獲得理想的類簇個數和較高的分類精度為指標調整參數fac的值，從而確定閾值ρ。各個數據集上eVQ聚類算法的閾值ρ及fac取值如表2所示。實驗環境：CentOS Linux release 7.0.1406，C語言，gcc4.8.2編譯器，CPU 3.4 GHz，1 GB內存。

表2 各數據集參數設置Tab. 2 Parameter setting for experimental data sets

I-FAC與B-FAC對比分析，將表1中所列每個數據集隨機等分為6部分，選擇3部分作為DB，2部分作為db，剩余部分作為測試集，UWEP算法閾值θ設為1，采用6-交叉驗證方式評估分類模型。B-FAC與I-FAC在分類精度與訓練時間兩方面的實驗結果如表3所示。從表3中不難發現，B-FAC與I-FAC的分類準確率相當，I-FAC的訓練時間低于B-FAC，因此本文所提方法能夠在保證分類準確率的前提下，降低模糊關聯分類器在動態數據集上的訓練時間。主要原因分析如下：FAC構建過程的主要時間開銷是挖掘模糊頻繁項。當db加入到DB時，I-FAC首先從LDB中繼承部分模糊頻繁項，然后生成由db的加入而變得頻繁的模糊項。表4中列出了I-FAC在4個標準數據集上繼承的模糊頻繁項個數和DB∪db上生成的模糊頻繁項總數，從表4可知I-FAC在增量挖掘模糊頻繁項過程中從LDB中繼承了大量模糊頻繁項，所以I-FAC能明顯減少分類器的訓練時間。

表3 B-FAC與I-FAC在分類精度和訓練時間上對比結果Tab. 3 Comparison results of B-FAC and I-FAC in classification accuracy and training time

表4 保留的模糊頻繁項數目與生成的模糊頻繁項總數Tab. 4 The number of frequent items reserved and the number of frequent items generated

解釋性為評價模糊關聯分類器的另一個重要指標。該指標通常以分類器中包含的規則數目以及所有分類規則前件長度(包含的模糊項個數)來表示。表5為B-FAC與I-FAC生成的分類規則庫中FACR個數和規則前件長度對比結果，表5中所列數據為6次實驗結果的均值。

從表5可知，I-FAC與B-FAC的解釋性相當，因此I-FAC在保持分類精度的同時并沒有以損失解釋性為代價。

為了驗證文中基于eVQ增量更新高斯隸屬度函數的有效性，將表1所列的每個數據集隨機分成10份，隨機選取3份作為初始訓練集，剩余7份作為增量訓練集，全部10份作為測試集。采用下面三種方式對初始訓練集上的FAC增量更新：

1) 用初始訓練集上的高斯隸屬度函數對增量訓練集模糊化，采用1.2節的方法增量挖掘模糊頻繁項，更新并裁剪初始訓練集上的分類規則庫，該方法記為NI-FAC。

2) 由文中1.1節、1.2節描述的方法增量更新高斯隸屬度函數及FAC。

3) 采用增量FCM聚類算法[15]對初始訓練集和增量訓練集模糊化處理，基于文中1.2節的方法生成并更新FAC，該方法記作I-FCM。

上述三種模糊預處理方式的分類準確率對比結果如表6所示。

表5 B-FAC與I-FAC的FACR個數和規則前件長度對比Tab. 5 The number of FACR and the length of fuzzy items of rule antecedent in B-FAC and I-FAC

表6 I-FAC與NI-FAC、I-FCM分類精度對比Tab. 6 Comparison of I-FAC，NI-FAC and I-FCM in classification accuracy

從表6可知，I-FAC的分類準確率明顯高于NI-FAC。這主要是因為當新數據加入原始數據集時，整個訓練數據集分布會發生變化，I-FAC在增量學習階段更新了高斯隸屬度函數參數，使得由其表示的模糊區間更加合理。除Breast數據集外，I-FAC分類準確率均高于I-FCM。而且在數據集Heart和Pima上，NI-FAC的分類準確率也高于I-FCM，這是因為eVQ聚類機制本身具有增量學習的能力，由其獲得高斯隸屬度函數能較好地表示樣本對其所屬類別的隸屬關系。

3 結語

本文提出了一種適用于動態數據集上的模糊關聯分類器建模方法。該方法采用eVQ聚類算法更新高斯隸屬度函數，通過預先設定的閾值θ確定需要保留的模糊頻繁項，擴展了UWEP方法，使之能用于增量挖掘模糊頻繁項。實驗結果表明文中方法能夠在保證分類精度和解釋性的同時降低模糊關聯分類器的訓練時間，而且高斯隸屬度函數更新是增量FAC建模重要環節。下一步將研究其他增量聚類算法對本文方法的影響，研究基于遺傳優化的規則庫增量更新方法，進一步提高模糊關聯分類器的分類精度和解釋性。

References)

[1] ALCALA-FDEZ J, ALCALA R, HERRERA F. A fuzzy association rule-based classification model for high-dimensional problems with genetic rule selection and lateral tuning[J]. IEEE Transactions on Fuzzy Systems, 2011, 19(5): 857-872.

[2] ANTONELLI M, DUCANGE P, MARCELLONI F, et al. A novel associative classification model based on a fuzzy frequent pattern mining algorithm[J]. Expert Systems with Applications, 2015, 42(4):2086-2097.

[3] MA Y, CHEN G, WEI Q. A novel fuzzy associative classifier based on information gain and rule-covering[C]// Proceedings of the 2013 Joint IFSA World Congress and NAFIPS Annual Meeting. Piscataway, NJ: IEEE, 2013: 490-495.

[4] PACH F P, GYENESEI A, ABONYI J. Compact fuzzy association rule-based classifier[J]. Expert Systems with Applications, 2008, 34(4): 2406-2416.

[5] 霍緯綱, 高小霞.一種適用于多類不平衡數據集的模糊關聯分類方法[J].控制與決策, 2012,27(12):1833-1838.(HUO W G, GAO X X. A fuzzy associative classification method for multi-class imbalanced datasets[J]. Control and Decision, 2012, 27(12): 1833-1838.

[6] 高小霞, 霍緯綱, 馮興杰.基于模糊關聯分類器的民機超限事件診斷方法[J].北京航空航天大學學報,2014,40(10):1366-1371.(GAO X X, HUO W G,FENG X J. Civil aircraft’s exceedance event diagnosis method based on fuzzy associative classifier[J]. Journal of Beijing University of Aeronautics and Astronautics, 2014, 40(10): 1366-1371.

[7] 董杰, 沈國杰.一種基于模糊關聯分類的遙感圖像分類方法[J].計算機研究與發展,2012,49(7):1500-1506.(DONG J, SHEN G J. Remote sensing image classification based on fuzzy associative classification[J]. Journal of Computer Research and Development, 2012, 49(7): 1500-1506.

[8] LUGHOFER E, KLEMENT E P. FLEXFIS: a variant for incremental learning of Takagi-Sugeno fuzzy systems[C]// Proceedings of the 14th IEEE International Conference on Fuzzy Systems. Piscataway, NJ: IEEE, 2005: 915-920.

[9] LUGHOFER E, ANGELOV P, ZHOU X. Evolving single-and multi-model fuzzy classifiers with FLEXFIS-Class[C]// Proceedings of the 2007 IEEE International Fuzzy Systems Conference. Piscataway, NJ: IEEE, 2007:1-6.

[10] ANGELOV P P, ZHOU X. Evolving fuzzy-rule-based classifiers from data streams[J].IEEE Transactions on Fuzzy Systems, 2008, 16(6):1462-1475.

[11] ANGELOV P, LUGHOFER E, ZHOU X. Evolving fuzzy classifiers using different model architectures[J]. Fuzzy Sets and Systems, 2008,159(23):3160-3182.

[12] 張杰, 趙峰. 流數據概念漂移的檢測算法[J].控制與決策,2013,28(1):29-35.(ZHANG J, ZHAO F. Detecting algorithm of concept drift from stream data[J]. Control and Decision, 2013, 28(1): 29-35.

[13] AYAN N F, TANSEL A U, ARKUN E. An efficient algorithm to update large itemsets with early pruning[C]// Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 1999:287-291.

[14] LUGHOFER E.Extensions of vector quantization for incremental clustering[J].Pattern Recognition, 2008,41(3):995-1011.

[15] HORE P, HALL L O, GOLDGOF D B. Single pass fuzzy c means[C]// Proceedings of the 2007 IEEE International Conference on Fuzzy Systems. Piscataway, NJ: IEEE, 2007: 240-246.

This work is partially supported by the National Natural Science Foundation of China (61301245), the Joint Fund of National Natural Science Foundation of China and Civil Aviation Administration of China (U1633110).

HUOWeigang, born in 1978, Ph. D., associate professor. His research include data mining, fuzzy classification.

QUFeng, born in 1988, M.S. candidate. His research include data mining.

CHENGZhen, born in 1991, M.S. candidate. His research include data mining.

Incrementalfuzzyassociativeclassificationmethodbasedonevolvingvectorquantizationclusteringalgorithm

HUO Weigang*, QU Feng, CHENG Zhen

(CollegeofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China)

In order to improve the efficiency of building Fuzzy Associative Classifier (FAC) on the dynamic data sets, an incremental fuzzy associative classification method based on eVQ (evolving Vector Quantization) clustering algorithm was proposed. Firstly, eVQ clustering algorithm was adopted to incrementally update the parameters of Gauss membership functions of quantitative attributes. Secondly, Update With Early Pruning (UWEP) algorithm was extended to incrementally mine fuzzy frequent itemsets. Finally, Fuzzy CORRelation (FCORR) of Fuzzy Associative Classification Rule (FACR) and the length of antecedent of FACR were regarded as measures to prune and update fuzzy associative classification rule base. The experimental results on four UCI benchmark data sets show that compared with the batch fuzzy association classification modeling method, the proposed method can reduce the time of training the FAC in the premise of not decreasing the accuracy and interpretability. The Gauss membership function updating method based on eVQ clustering algorithm contributes to improve the classification accuracy of the FAC on the dynamic data sets.

incremental learning; fuzzy associative classification; evolving Vector Quantization (eVQ) cluster; Update With Early Pruning (UWEP); Gauss membership function

2017- 05- 16;

2017- 06- 20。

國家自然科學基金資助項目(61301245);國家自然科學基金委員會與中國民用航空局聯合資助項目(U1633110)。

霍緯綱(1978—)，男，山西洪洞人，副教授，博士，CCF會員，主要研究方向：數據挖掘、模糊分類； 屈峰(1988—)，男，遼寧沈陽人，碩士研究生，主要研究方向：數據挖掘； 程震(1991—)，男，江蘇沛縣人，碩士研究生，主要研究方向：數據挖掘。

1001- 9081(2017)11- 3075- 05

10.11772/j.issn.1001- 9081.2017.11.3075

(*通信作者電子郵箱wghuo@cauc.edu.cn)

TP311

A