模糊关联分类器(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个模糊区间对应的高斯隶属度函数。
| $ A\left( {{x_{k,j}}} \right) = \exp {\left[ { - \left( {\frac{{{x_{k,j}} - {c_{i,j}}}}{{2{\delta _{i,j}}}}} \right)} \right]^2};(1 \le i \le s,1 \le j \le N) $ | (1) |
其中:δi, j表示第j(1≤j≤N)个属性上第i(1≤i≤s)个模糊区间的范围。
更新高斯隶属度函数参数的基本思想：采用Min-max标准化方法将DB上的s个聚类中心和db中的数据标准化，计算db中每个标准化数据Xm(1≤m≤L)与s个聚类中心的欧氏距离，得到与样本Xm距离最近的第win个聚类中心记为Cwin，Cwin与Xm之间的距离记作dmin，若dmin大于阈值ρ，则生成一个新的类簇，否则将样本Xm并入Cwin所在类簇，由式(2)和(3)更新Cwin在N个数量属性上的投影及Cwin所属类簇在N个数量属性上确定的模糊区间范围。
| $ {{c'}_{win,j}} = {c_{win,j}} + {\eta _{win}} \times ({x_{k,j}} - {c_{win,j}});1 \le j \le N $ | (2) |
其中:ηwin=0.5/kwin，cwin, j表示第win个聚类中心第j个分量原始值，c′win, j表示第win个聚类中心第j个分量更新后的值。
| $ \begin{array}{c} ({k_{win}} + 1) \times \delta _{win,j}^{'2} = {k_{win}} \times \delta _{win,j}^2 + ({k_{win}} + 1) \times \Delta c_{win,j}^2 + \\ {({c_{win,j}} - {x_{k,j}})^2} \end{array} $ | (3) |
| $ \Delta {c_{win,j}}{\rm{ = }}{{c'}_{win,j}} - {c_{win,j}};1 \le j \le N $ | (4) |
基于eVQ聚类算法的高斯隶属度函数更新方法详细描述如下：
输入 增量数据集db，原始数据集DB上生成的s个类簇中心点，s×N个模糊区间对应的高斯隶属度函数参数ci, j, δi, j(1≤i≤s, 1≤j≤N)，确定类簇数目的阈值ρ。
输出 更新后的s′个类簇中心点以及s′×N个模糊区间对应的高斯隶属度函数参数c′i, j, δ′i, j(1≤i≤s, 1≤j≤N)。
For k=1, 2, …, s
将Ck标准化为Ck
End For
For m=1, 2, …, L
从db中取一个增量数据样本Xm=[xm, 1, xm, 2, …, xm, N], 将Xm标准化为Xm
For k=1, 2, …, s
dk=‖Xm-Ck‖
End For
从{d1, d2, …, ds}中选取最小值dmin，得到与Xm距离最近的第win个聚类中心记作Cwin
If dmin>ρ，Then
s=s+1; Cs=Xm; ks=1
else
将样本Xm并入Cwin所在类簇，kwin=kwin+1
For j=1, 2, …, N
用式(2)把第win个聚类中心在第j个属性上的投影更新为cwin, j′；
用式(3)把第win个聚类中心在第j个属性上确定的模糊区间范围更新为δwin, j′。
End For
End If
End For
1.2 基于UWEP算法的增量模糊频繁项挖掘设A表示任给的训练数据集，LAk为A上长度为k的模糊频繁项集合，LA为A上的所有模糊频繁项集合，CAk表示数据集A上长度为k的模糊候选项集合，supAk(I)表示k-模糊项I在数据集A上的模糊支持度，ChangedFItem表示发生变化的高斯隶属度函数对应的1-模糊项集合，其中的每一模糊项记为CItem，minsup表示最小模糊支持度。
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及其超集。
步骤2 经步骤1处理后，若LDB=∅，则基于Apriori算法生成DB∪db的模糊频繁项集LDB∪db；否则按照下面4种情况逐一处理Cdbk中的每个候选模糊项。
步骤2.1 I(I∈Cdbk)在DB上频繁并且在db上不频繁，若supDBk(I)+supdbk(I)>minsup，则将I并入LDB∪db，否则从LDB中删除I及其超集；
步骤2.2 I(I∈Cdbk)在DB上频繁并且在db上频繁，将I并入LDB∪db；
步骤2.3 I(I∈Cdbk)在DB上不频繁并且在db上频繁，计算supDBk(I)，若supDBk(I)+supdbk(I)>minsup，则将I并入LDB∪db；
步骤2.4 I(I∈Cdbk)在DB、db上均不频繁并且I中包含的任意1-模糊项属于ChangedFItem，计算I在DB∪db上的支持度supDB∪dbk(I)，若supDB∪dbk(I)>minsup，将I并入LDB∪db。
模糊关联分类规则库的增量更新过程为：
步骤1 由新模糊频繁项集合中带有类标签的模糊频繁项生成新分类规则集RuleBasenew。
步骤2 删除初始FAC的分类规则集RuleBase中不属于RuleBasenew的FACR，将RuleBasenew中不属于RuleBase的FACR加入到RuleBase。
步骤3 采用文献[4]中以FCORR和FACR前件长度为度量方式的规则库精简方法对RuleBase进行裁剪得到更新后的模糊关联分类规则库RuleBase′。
增量更新与裁剪初始分类规则库RuleBase的具体算法描述如下：
输入 模糊关联分类规则库RuleBase，RuleBasenew。
输出 精简后的分类规则库RuleBase′。
For RuleBase中每个模糊关联分类规则R
If R ∉ RuleBasenew, Then
从RuleBase中删除R
End If
End For
For RuleBasenew中每个模糊关联分类规则Rnew
If Rnew ∉ RuleBase，Then
将Rnew加入到RuleBase中
End If
End For
在RuleBase中扫描不同类别中每种长度的FACR，将具有最大FCORR的FACR加入规则集RuleBase′，RuleBase′中最长规则的长度记作Len。
Do until Len=2
For每个模糊关联分类规则RLen(RLen∈RuleBase′)
If RLen-1∈RuleBase′并且RLen的前件包含RLen-1的前件
If FCORR(RLen-1)>FCORR(RLen)，Then
从RuleBase′中删除RLen
End If
End If
Len=Len-1
End For
End Do
RuleBase′中最长规则的长度记作Len′
Do until i=Len′
For每个模糊关联分类规则Ri(Ri∈RuleBase′)
If Ri+1∈RuleBase′并且Ri+1的前件包含Ri的前件
If FCORR(Ri+1)>FCORR(Ri)，Then
从RuleBase′中删除Ri
End If
End If
i=i+1
End For
End Do
2 算法复杂度分析与实验结果 2.1 算法复杂度分析设初始数据集DB与增量后数据集DB∪db的模糊项个数均为m，DB包含的模糊事务数量为M，DB∪db的模糊事务数为M+L，DB∪db上模糊1-频繁项的个数为k，DB∪db中模糊频繁项的最大长度为q。本文的增量模糊关联分类器建模方法记为I-FAC，传统批量模糊关联分类建模方法记为B-FAC，当db并入DB时，B-FAC需要在数据集DB∪db上重新训练分类器，无法继承DB上已有的分类规则。下面仅分析两种方法在增量学习过程中的复杂度。I-FAC和B-FAC均采用文中的eVQ聚类算法生成隶属度函数，两者在模糊预处理步骤的时间和空间复杂度均为Ο((M+L)·m)。I-FAC和B-FAC在分类规则库的更新和精简步骤的时空复杂度与生成模糊频繁项的复杂度线性相关。两种方法生成模糊频繁项时空复杂度如下：I-FAC扫描数据集的时间复杂度为Ο((M+L)·m)。B-FAC采用Apriori算法，其时间复杂度为Ο((M+L)·m·q)。从生成模糊频繁项数目角度分析，DB∪db上生成的模糊频繁项总数最多为C=ck1+ck2+…+ckq。最坏情况下，B-FAC的时间复杂度为Ο(C)。设I-FAC从DB继承的模糊频繁项数目与总模糊频繁项数的比值为α(0≤α≤1)，则I-FAC的最坏时间复杂度为Ο((1-α)·C)。B-FAC的内存空间开销为存储候选模糊频繁项集，其最坏复杂度为Ο(C)。而I-FAC除了存储候选模糊频繁项集外，还需在内存中存储DB∪db上所有隶属度不为0的模糊隶属度值和事务标识，其最坏空间复杂度为Ο(C+(M+L)·m)。
2.2 实验结果为了验证文中增量模糊关联分类器建模方法的有效性，实验选取UCI(http://archive.ics.uci.edu/ml/datasets.html)机器学习数据集中的4个数据集进行测试，数据集的详细信息如表 1所示。
|
表 1 实验数据集 Table 1 Experimental data sets |
实验中以最少类别样本在训练样本集中出现频率的0.1倍为最小模糊支持度, 采用多类别规则投票方式[4]为分类推理引擎。eVQ算法中阈值ρ按式(5)[14]计算：
| $ \rho = fac * \left( {\sqrt p /\sqrt 2 } \right) $ | (5) |
其中：p为训练样本集维数，fac为调节因子，文中在实验过程中以获得理想的类簇个数和较高的分类精度为指标调整参数fac的值，从而确定阈值ρ。各个数据集上eVQ聚类算法的阈值ρ及fac取值如表 2所示。实验环境：CentOS Linux release 7.0.1406，C语言，gcc4.8.2编译器，CPU 3.4 GHz，1 GB内存。
|
|
表 2 各数据集参数设置 Table 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在分类精度和训练时间上对比结果 Table 3 Comparison results of B-FAC and I-FAC in classification accuracy and training time |
|
|
表 4 保留的模糊频繁项数目与生成的模糊频繁项总数 Table 4 The number of frequent items reserved and the number of frequent items generated |
解释性为评价模糊关联分类器的另一个重要指标。该指标通常以分类器中包含的规则数目以及所有分类规则前件长度(包含的模糊项个数)来表示。表 5为B-FAC与I-FAC生成的分类规则库中FACR个数和规则前件长度对比结果，表 5中所列数据为6次实验结果的均值。
|
|
表 5 B-FAC与I-FAC的FACR个数和规则前件长度对比 Table 5 The number of FACR and the length of fuzzy items of rule antecedent in B-FAC and I-FAC |
从表 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所示。
|
|
表 6 I-FAC与NI-FAC、I-FCM分类精度对比 Table 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建模重要环节。下一步将研究其他增量聚类算法对本文方法的影响，研究基于遗传优化的规则库增量更新方法，进一步提高模糊关联分类器的分类精度和解释性。
| [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. DOI:10.1109/TFUZZ.2011.2147794 |
| [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. DOI:10.1016/j.eswa.2014.09.021 |
| [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. DOI:10.1016/j.eswa.2007.04.005 |
| [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. DOI:10.1109/TFUZZ.2008.925904 |
| [11] | ANGELOV P, LUGHOFER E, ZHOU X. Evolving fuzzy classifiers using different model architectures[J]. Fuzzy Sets and Systems, 2008, 159(23): 3160-3182. DOI:10.1016/j.fss.2008.06.019 |
| [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. DOI:10.1016/j.patcog.2007.07.019 |
| [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. |