基于模糊概念相似性与模糊熵度量的模糊分类算法

冯兴华，刘晓东＊，刘亚清

（1.大连理工大学 控制科学与工程学院，辽宁 大连 116024；2.大连海事大学 信息科学技术学院，辽宁 大连 116026）

0 引 言

利用IF－THEN 规则的分类方法的优势在于给出分类结果的同时还能够给出分类的语义解释［1］.为了克服数据中存在的不确定性和含糊性等，基于模糊规则的分类方法被提出，并被大量研究［2］.例如，Wang等［3］提出了基于关联规则的模糊分类器，而Alcala等［4］提出了针对高维数据的模糊关联规则分类方法；Huhn等［5］提出了名为FURIA 的分类方法，此方法先产生经典分类规则集，然后用梯形模糊集对分类规则进行模糊化，最后用得到的模糊规则集对数据进行分类.最近，一种由支持向量机诱导分类规则的方法［6］被提出，该方法主要考虑了支持向量机的分类边界及训练样本的分布.很多利用模糊规则分类的方法都是基于模糊概念的.然而，恰当地确定模糊概念的隶属函数是非常困难的，即使是领域内专家也很难做到［7］.采用不同的隶属函数对最终分类结果影响很大；而用不同的隶属函数，相同的分类算法也会给出不同的分类结果.这在一定程度上影响了模糊分类器的设计.

基于上述分析，本文在AFS（axiomatic fuzzy set）理论框架下提出一种基于模糊概念相似性与模糊熵度量的分类算法；并在8组来自UCI［8］数据库的实验数据上和其他7 种分类算法进行比较，以证明该算法的可靠性和优越性.

1 AFS理论相关知识

设X是一个数据集，即X＝｛x1，x2，…，xN｝.其中xi＝｛xi，1，xi，2，…，xi，n｝，xi，j表示样本xi在第j个属性上的取值，i＝1，2，…，N，j＝1，2，…，n.在每个属性上，取定若干个简单的模糊概念形成模糊概念集合M.

文献［9］证明了如果如下定义EM上的运算∧和∨，则（EM，∧，∨）是完全分配格：任意

其中U是指标集I与J的不交并.

设X为数据集，M是X上的概念集，对于任意的概念集合AM及x∈X，定义X的子集A≥（x）：

式中：x≥Ay表示对于任意的模糊概念m∈A，x隶属于m的程度大于或者等于y隶属于m的程度；A≥（x）完全由概念集合A中的概念的语义及样本集合X的分布决定.

定义1［9－10］设集合M是一个概念集合，（EM，∧，∨）是完全分配格，则对于任意的x∈X，模糊概念的隶属函数定义为

上面定义的模糊概念的隶属函数完全由概念的语义及样本数据的分布决定.因为格（EM，∧，∨）对逻辑运算∧、∨封闭，所以对于EM中的任何概念的隶属函数都可以由上述定义得到.

2 基于模糊规则的分类算法

首先描述指导概念聚合过程的模糊概念选择函数，然后给出产生模糊IF－THEN 规则集的聚合算法，最后介绍模糊规则集的剪枝算法及利用模糊规则集对样本的分类过程.

2.1 选择函数

（1）模糊概念的相似性

设α、β是两个模糊概念，Jaccard相似性［11］在AFS理论框架下表示为

其中∨、∧分别由式（1）和（2）给出.μα∧β（x）和μα∨β（x）分别表示样本x隶属于模糊概念α∧β和α∨β的隶属度，由式（4）给出.

（2）模糊熵

α是一个模糊概念，Λ是一个模糊概念集合，Λ＝｛β1，β2，…，βk｝.Λ对α的一个划分记为Λ｜α，定义为Λ｜α＝｛β1 ∧α，β2 ∧α，…，βk∧α｝.信息熵是衡量一个集合的混乱程度的常用度量.为了衡量划分Λ｜α中βi∧α与其他部分的相异程度，定义βi∧α与其他部分之间的模糊熵为

（3）选择函数

如下定义选择函数f（α，βi）：

式（6）所示的选择函数评价模糊概念α对模糊概念βi的描述能力.一方面考虑了α与βi的相似性，另一方面考虑在用Λ对α划分时，βi∧α与其他部分的相异性.一般而言，α与βi越相似，并且模糊划分Λ｜α中βi∧α与其他部分的相异性越大，选择函数f（α，βi）的值越大.

在分类问题中，Λ＝｛β1，β2，…，βk｝可以表示决策属性上的类别概念集，βi表示第i类.这种情况下，式（6）就可以用来衡量模糊概念α对类别βi的描述能力.而基于规则的分类方法就是要找到条件属性上的概念α来描述决策属性上的类别概念βi.也就是说，α不但要和βi相似，又要使βi∧α和βj∧α（j≠i）较好地区分开.

下面用图1所示的例子来例证所定义的选择函数的合理性.图1所示的是一个两类别分类问题，包含100个样本，两类的决策概念分别用β1、β2表示，即决策属性上的决策概念集为Λ＝｛β1，β2｝.α1、α2、α3、α4是4个条件属性上的模糊概念.表1给出了α1、α2、α3、α4分别对β1 的选择函数值.

在图1中，与α3相比，第一类的50个样本在α2上的隶属度与β1 更为相似，但是α2对第一类样本与第二类样本的区分度并不大.从与β1 的相似性与对两类样本的区分程度两方面来考虑的话，α3对β1 的描述能力更强.也就是说，α3比α2更适合作为β1 的规则前件.从表1中的数据可以看到f（α3，β1）＝－0.10，f（α2，β1）＝－0.22，这说明本文定义的选择函数给出的选择结论与本文的直观分析完全一致.

图1 模糊概念的隶属度函数Fig.1 The membership functions of fuzzy concepts

表1 选择函数在不同模糊概念上的取值Tab.1 The selection index values on different fuzzy concepts

比较α1与α4的隶属度函数可以看到，虽然α1与α4都可以将两类样本很好地区分开，但是α4与目标类别β1 相似性非常小.这说明与α4相比，α1能更好描述β1.

从表1给出的各个模糊概念对β1 的选择函数值可以看到，f（α1，β1）＞f（α3，β1）＞f（α2，β1）＞f（α4，β1）.这与从图1中得到的直观分析结果一致.

2.2 分类算法

本文提出的分类算法利用IF－THEN 规则对样本进行分类，其中每一条分类规则都具有如下形式：IFα，THENβ.α表示条件属性上的模糊概念，β表示决策属性上的概念（模糊或非模糊）.每一条IF－THEN 规则都是前件和后件之间的关系的体现.

一般情况下，如果分类规则集的前件过于简单，往往不能得到较好的分类精度；如果过于复杂，则意味着有可能发生了过度训练.本文通过简单概念的聚合得到恰当的规则前件.通过概念聚合［12］，简单概念被聚合为复杂概念，以便更好地描述规则后件，从而提高分类精度.

概念聚合包含3 个部分：目标概念、候选概念，以及逻辑算子.模糊概念的聚合是通过概念的逻辑运算完成的.如前文所述，在AFS理论中定义了两种模糊概念的逻辑算子，分别是“or”∨（如式（1）所示）和“and”∧（如式（2）所示）.通过逻辑算子将目标概念与候选概念聚合为新的模糊概念，聚合得到的模糊概念的隶属度由式（4）给出.

分类问题涉及的数据可以规范为如下形式：设X＝｛x1，x2，…，xN｝表示样本集合，A1，A2，…，An表示样本集上的n个条件属性，C表示决策属性.在条件属性Ai上取ki个简单模糊概念，用T（Ai）＝｛mi1，mi2，…，miki｝表示Ai上的简单概念集合，T（C）＝｛β1，β2，…，βc｝表示决策属性上的决策概念集合，即T（C）中的每一个概念表示样本集的一个类别.

模糊分类规则构建算法为每一个类别通过聚合找到最合适的描述概念.以第一类为例的算法如图2所示.由图2给出的算法可以得到一个规则集，其中的每一条规则的前件是输出Result中的一个模糊概念，后件是第一类的决策概念β1.

在图2中，Ξ表示目标概念集；Θ表示待候选概念集；Ω表示简单概念集；Ψ表示算子集；Θ#Ω表示候选概念集.

算法的时间复杂度为O（N｜Ω0｜），其中N为训练样本的个数，｜Ω0｜为初始简单概念的个数.算法的最大计算量来自于聚合过程（见图2），在每次循环过程中，用L个目标概念和至多｜Ω0｜＋T个候选概念进行聚合，聚合过程循环length次.而L、T和length三个参数由用户给出，是固定的数值，在下一节的实验中分别设置为3、2和5.所以时间复杂度为O（N｜Ω0｜）.

2.3 推理过程

从图2所示算法直接得到的模糊规则集可能包含冗余和分类能力差的规则.因此，需要将这样的规则从规则集中剔除以提高规则集的分类准确率和分类效率.这里采用一种剪枝方法来修剪规则集，这种方法只需要规则集和训练样本集的参与.具体过程如下：

步骤1 对规则集中的每一条规则进行如下过程：删除该规则，用剩余规则对训练样本进行分类并记录分类准确率及该条规则.

步骤2 找到步骤1中得到的准确率中的最高准确率对应的规则，真正将之删除.

步骤3 重复步骤1及步骤2直到如果要真正删除某条规则，规则集对训练样本的分类准确率将出现下降为止.

剪枝后的规则集就是最终用于分类的规则集.当需要对新样本x进行分类时，用式（4）计算该样本在每一条规则的前件上的隶属度.样本x将被分配到规则r所表示的类，如果x在规则r的前件上取得最大的隶属度值.

3 实验结果及分析

用8组来自UCI的数据对提出的分类算法进行验证.表2给出了这8组数据的基本信息.在这8组数据上，对本文分类方法和其他7种分类方法做了比较.这7 种方法是C4.5［13］、Decision Table （DTable）［14］、Fast Effective Rule Induction （JRip）［15］、 Nearest－neighbor－like Algorithm（NNge）［16］、OneR［17］、PART Decision List （PART）［18］，以 及 Ripple－down Rule Learner（Ridor）［19］.上述7种分类方法由分类工具箱Weka［20］实现且各个分类器均采用工具箱指定的默认参数.在本文提出的分类方法中，3个参数分别为L＝3，T＝2，length＝5.另外，为简单起见在每个数据集的各个条件属性上取3个简单模糊概念，每一个简单模糊概念都有一个明确的含义：离第i个分割点较近.第一个分割点取为属性的最小值；第二个分割点取为属性均值；第三个分割点取为属性的最大值，所有概念的隶属函数由式（4）给出.

在实验中，对每一个分类数据均采用10折交叉验证法来评估分类算法分类准确率.实验得到的分类准确率如表3所示.由表3可以看出，本文提出的分类算法（在表3中用AFS表示）能给出最好的分类结果，8组数据上的平均准确率最高.为了进一步分析本文提出的算法与其他7种分类算法之间的差异，采用统计分析的方法对这8种分类算法得到的结果做出分析.

表2 来自UCI数据库的8组数据的基本信息Tab.2 The descriptions of datasets from UCI repository

首先，用Friedman检验法［21］来检验这8 种分类器在8组实验数据上得到的分类结果是否存在显著差异；如果这些分类结果存在显著差异，进一步采用Holm 检验法［21］来检验本文提出的算法是否和其他方法存在显著差异.

表3 不同分类方法的比较分析Tab.3 A comparative analysis of different classification methods

Friedman检验法的零假设为多个分类方法得到的分类结果不存在显著差异.在每一个数据集上，按照各个分类方法得到的分类准确率将其排序，每一个分类方法将得到一个序数值（如果分类准确率一样，则均分序数值）.以下假设有k个分类方法，实验数据有N组.用rji表示第j种分类方法在第i个数据上的序数值，则Rj＝（1／N）∑irji表示第j种分类方法在N组实验数据上的平均序数值.Friedman检验的统计量为

该统计量服从自由度为k－1的卡方分布.如果k和N比较小，则使用下面的统计量：

统计量FF服从自由度为（k－1）和（k－1）·（N－1）的F分布.

本文所做的实验中k＝8，N＝8，FF＝2.57，在显著性水平α＝0.05下统计量的值超过了临界值.所以，可以拒绝零假设，即这8种方法在8组数据上得到的分类结果存在显著差异.然后，用Holm 测试来分析本文方法和其他7种方法之间是否存在显著差异.分析的结果显示，在显著水平α＝0.1时，本文方法在8组实验数据上的分类结果显著好于DTable方法和OneR 方法.虽然本文的方法不是显著好于其他5种方法，但是表3列出的序数值说明，本文的方法取得了最小的均序值，即本文提出的分类算法能得到最好的分类准确率.

4 结 语

本文提出了一种产生模糊分类规则的方法.该方法通过简单模糊概念的聚合产生模糊分类规则的前件.一个基于模糊概念相似性与模糊熵的选择函数指导概念的聚合过程.用AFS理论来处理模糊概念的逻辑运算，并给出其隶属函数.在AFS理论框架下，模糊概念的隶属函数完全由概念的语义和样本数据的分布决定，不需要背景知识的参与.

在8组来自UCI数据库的数据上和7 种经典分类方法做了比较.实验结果显示，本文提出的分类算法能得到最好的分类精度，其分类准确率显著地高于DTable方法和OneR 方法.

在以后的工作中，将研究概念聚合的过程，设计新的算法以提高规则集的分类效果.另一个可以扩展的工作是对规则集的结构的分析，这也可帮助改进聚合算法.

［1］ Alsabti K，Ranka S，Singh V.CLOUDS：A decision tree classifier for large datasets ［C］／／Conference of Knowledge Discovery and Data Mining.New York：AAAI Press，1998：2－8.

［2］ Cano J，Herrera F，Lozano M.Evolutionary stratified training set selection for extracting classification rules with trade off precision interpretability ［J］.Data and Knowledge Engineering，2007，60（1）：90－108.

［3］ WANG Xin，LIU Xiao－dong，Pedrycz W.Mining axiomatic fuzzy set association rules for classification problems ［J］.European Journal of Operational Research，2012，218（1）：202－210.

［4］ Alcala F J，Alcala R，Herrera F.A fuzzy association rule－based classification model for highdimensional problems with genetic rule selection and lateral tuning ［J］.IEEE Transactions on Fuzzy Systems，2011，19（5）：857－872.

［5］ Huhn J，Hullermeier E.FURIA：An algorithm for unordered fuzzy rule induction［J］.Data Mining and Knowledge Discovery，2009，19（3）：293－319.

［6］ ZHU Peng－fei，HU Qing－hua.Rule extraction from support vector machines based on consistent region covering reduction［J］.Knowledge－Based Systems，2013，42（1）：1－8.

［7］ Chandra B，Varghese P P.Fuzzy SLIQ decision tree algorithm ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B：Cybernetics，2008，38（5）：1294－1301.

［8］ Merz C J，Murphy P M.UCI repository for machine learning data－bases ［Z］.Irvine：Department of Information and Computer Science，University of California，1996.

［9］ LIU Xiao－dong.The fuzzy theory based on AFS algebras and AFS structure ［J］.Journal of Mathematical Analysis and Applications，1998，217（2）：459－478.

［10］ LIU Xiao－dong，WANG Wei，CHAI Tian－you.The fuzzy clustering analysis based on AFS theory［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B：Cybernetics，2005，35（5）：1013－1027.

［11］ Tan P N，Steinbach M，Kumar V.Introduction to Data Mining［M］.MA：Addison－Wesley，2005.

［12］ HUANG Zhi－heng，Gedeon T D，Nikravesh M.Pattern trees induction：A new machine learning method［J］.IEEE Transactions on Fuzzy Systems，2008，16（4）：958－970.

［13］ Quinlan J R.C4.5：Programs for Machine Learning［M］.San Mateo：Morgan Kaufmann，1993.

［14］ Kohavi R.The power of decision tables ［C］／／European Conference on Machine Learning.Heraclion：Springer，1995：174－189.

［15］ Cohen W W.Fast effective rule induction［C］／／The Twelfth International Conference on Machine Learning.California：Morgan Kaufmann，1995：115－123.

［16］ Roy S.Nearest Neighbor with Generalization［M］.Christchurch：University of Canterbury，2002.

［17］ Holte R C.Very simple classification rules perform well on most commonly used datasets［J］.Machine Learning，1993，11（1）：63－91.

［18］ Frank E，Witten I H.Generating accurate rule sets without global optimization ［C］／／The Fifteenth International Conference on Machine Learning.Wisconsin：Morgan Kaufmann，1998：144－151.

［19］ Gaines B R，Compton P.Induction of ripple－down rules applied to modeling large databases ［J］.Journal of Intelligent Information Systems，1995，5（3）：211－228.

［20］ Witten I H，Frank E.Data Mining：Practical Machine Learning Tools and Techniques［M］.San Mateo：Morgan Kaufmann，2005.

［21］ Demsar J.Statistical comparisons of classifiers over multiple data sets ［J］.Journal of Machine Learning，2006，7（1）：1－30.