一种基于概念格的复合分类器算法

概念格[1], 也称为Galois格, 是建立在偏序集上的具有完备性的一种序结构。概念格反映对象和属性之间的联系以及概念之间的泛化和例化关系。在概念层次结构上容易建立数据之间的依赖或因果关系模型, 因此概念格被认为是进行数据分析的有力工具。目前, 概念格已被应用于知识发现、软件工程、信息检索、语义学和经济学等领域。而分类是数据挖掘的重要任务。由于概念格节点体现了概念内涵和外延的统一, 所以非常适合于用来发现规则型知识。现有不少文献讨论了从概念格上提取规则[2,3,4,5,6]。基于概念格的分类算法与传统的分类算法 (例如决策树、朴素贝叶斯算法、支撑向量机以及神经网络等) 相比有其自身的优势[2,3,4,5,6], 但是仍然有许多不足, 例如在去噪以及参数设定方面[7]。不同的分类方法具有不同的决策平面且适合不同的情况。因此, 近年来研究者将精力集中在结合不同的分类算法来产生新的分类算法, 以便能够结合不同分类算法各自的优点来改善分类精度。这种复合分类器的主要代表有朴素贝叶斯树学习 (NBTree) [8]和懒贝叶斯规则学习算法 (LBR) [9]。尽管这两种方法在一定程度上提高了分类精度, 但是受到本地搜索原理限制将会阻止进一步搜索有意义的、有用的规则。

本文将概念格与传统分类器 (本文使用朴素贝叶斯分类器) 相结合得到了一种新的复合分类器 (GNB) 。实验表明算法可行有效且极大地提高了分类精度。

1 概念格

定义1一个形式背景是一个三元组K= (U, D, R) , 其中U为对象集;D为属性集;R为U和D之间的二元关系, R⊆U×D。

定义2若H1= (O1, D1) 满足D1=f (O1) , O1=g (D1) , 则称H1为形式背景K的一个概念。其中O1称为概念外延且O1⊆U, D1为概念内涵且

。通常用Extent (H1) 和Intent (H1) 分别表示概念H1的外延和内涵。

定义2-4设H1= (O1, D1) 和H2= (O2, D2) 是形式背景K= (U, D, R) 上的任意两个概念, 若D1⊆D2 (等价地, O2⊆O1) 记为 (O1, D1) ≤ (O2, D2) 称 (O2, D2) 为 (O1, D1) 的子概念。

2 复合分类器——GNB[10]

2.1 前后关系规则[8]

复合分类器的一个主要方法就是使用前后关系规则 (contextual rule) 代替了传统的分类规则 (normal classification rule) 来进行分类。在机器学习理论中, 一个分类规则采取如下的形式:, 其中Pi (1≤i≤r) 每个是对象的一个属性, Cj是类标签。这样一个规则的表示如果对象具有所有的属性Pi (1≤i≤r) 则它被分为Cj类。

将上述分类规则普遍化, 可定义前后关系规则, 形式如下:

其中CLSi是一个基本分类器。这样一个前后关系规则含义为如果对象满足所有的属性Pi (1≤i≤r) , 则使用基本分类器CLSi来对该对象进行分类。Cj也可以被看作一个分类器, 它将对象分为Cj类。如果把Cj看成一个分类器则显然普通分类规则是前后关系规则的一个特例。

2.2 概念格与基本分类器结合

一个前后关系规则就是形如r:H→C L S, 其中H是一个形式概念, C L S是一个基本分类器。这个基本分类器是由概念H的外延所引导的, 即在概念的外延上调用简单分类器 (这里用的朴素贝叶斯分类器) 对其进行训练学习, 从而得到一个基本分类器。概念H的外延是由每个对象的唯一标号或者标识所表示。将概念H的外延所对应的每个对象的唯一标号或标识所对应的形式样本挑出来作为简单分类器的训练样本。对该样本训练完后, 学习到的知识存入基本分类器C L S中。所以前后关系规则也可写成:ifintent (H1) then CLS。且用acc (r) 来表示前后关系分类器r:H→CLS的准确度。在算法实现中, 采用k次交叉验证中的leave-one-out来估计前后关系规则的准确度。

对一个前后关系分类器r1:H1→CLS和一个对象x, 如果满足intent (H1) ⊆f ({x}) 则说r1被对象x所激活。当r1被对象x所激活, CLS1可被用来预测对象x的类别, 被预测的类别用r1 (x) 来表示。

在概念格与基本分类器的结合中可以看到每个概念是训练样本空间的一个子空间。这些子空间相互间是有重叠的, 这一点不同于决策树。在决策树中, 每个叶子节点形成样例空间的一个划分。

2.3 训练算法

训练算法从根节点也就是包含所有样本的节点开始, 在每个概念节点上嵌入朴素贝叶斯分类器学习形成规则, 以便后面的分类算法调用。

步骤1:初始化规则集, RuleSeti=F, i=0, 1…, D;

步骤2:将rRoot:{ (U, D) }→nil加入RuleSet0中;

步骤3:FORi=0到D-1, DO

步骤4:FOR对RuleSeti中的每个前后关系规则rRoot:H→nil, DO

步骤5:寻找训练样本集即Extent (H) , 并在Extent (H) 上调用朴素贝叶斯分类器进行学习, 将学习到的知识存入CLS;

步骤6:将规则r从H→nil更新为H→CLS;

步骤7:计算H的所有直接产生子概念:

步骤8:FOR对每个子概念Hs, DO

步骤9:将Hs→nil插入到Rule et||intent||中;

步骤10:ENDFOR

步骤11:ENDFOR

步骤12:ENDFOR

2.4 分类算法

由前面的训练算法形成了前后关系规则集。也就是由形如r:H→CLS所组成的复合分类器。现给定一个未知类别的对象使用投票策略用来预测对象的类别。

步骤1:标记所有被该未知对象激活的前后关系分类器。通常情况下, 很多分类器将会被一个任意给定的对象所激活。

步骤2:对于任意两个被激活的前后关系规则r1:H1→CLS和r2:H2→CLS, 如果满足Intent (H1) ⊆Intent (H2) 则清除r1的被激活标志。

步骤3:对于任何一个被激活的前后关系规则r1, 如果还存在另一个被激活的前后关系规则r2并且r2的统计准确度比r1高, 则清除r1的被激活标志。

步骤4:使用被激活的规则集对输入数据集实施大多数投票策略。当被激活的规则所获得的大多数投票相等时, 用被选举中的且有最高准确度的前后关系分类器来进行预测对象的类别。

3 实验结果

算法是在Windows XP系统上采用MATLAB语言来实现的。实验所用的数据集是从UCI机器学习数据库[11]中下载的经典数据挖掘数据集Monks数据集。

结果表明, 同嵌入其概念节点上的朴素贝叶斯分类器相比较, GNB算法在Monks数据集上的分类效果得到了极大的提高。

4 结语

本文提出了一种基于概念格的复合分类器算法。基于概念格层次结构, 算法在每个概念节点上嵌入朴素贝叶斯分类器得到前后关系规则 (contextual rule) 并用多数投票策略来对新对象进行分类。实验结果表明算法极大地提高了分类精度。后续工作研究的重点是解决如何在保证分类精度的前提下尽量缩短分类时间。

摘要：目前概念格分类算法主要集中在利用其生成算法进行规则提取, 而已有的基于树形结构的复合分类器因受到本地搜索原理的限制其分类精度很难再提高。本文突破了这两种限制, 以概念格为分类模型提出了一种基于概念格的复合分类器算法。实验表明该算法极大地提高了分类精度。

关键词：概念格,复合分类器,前后关系规则

参考文献

[1] Wille R.Restructuringg Lattice Theory:An Approach Based on Hierarchies ofConcepts[M].In I.Rival (ed.) OrderedSets:1982:445～470.

[2] Njiwoua P, Mephu-Nguifo EM.For-warding the Choice of Bias LEGAL-F:Using Feature Selection to Reducethe Complexity of LEGAL[C].TiburgUniversity, The Netherlands:Proceed-ings of BENELEARN-97, LK andNFOLAB, 1997:89～90.

[3] Sahami M.Learning Classification RuleUsing Lattices[C].Heraclion, Crete, Greece:Nada L, Stefan W.In:Proceed-ings of ECML’95, 1995:343～346.

[4] Carpineto C, Romano G.Galois:AnOrder-Theoretic Approach to Con-ceptual Clustering[C].Amherst:In Pro-ceeding of ICML’93.1993:33～40.

[5] Cole R, Eklund PW.Scalability in FormalConcept Analysis[J].ComputationalIntelligence, 1999, 15 (1) .

[6] Godin R.Incremental Concept For-mation Algorithm Based on Galois Lattice[J].Computational Intelligence, 1995, 11 (2) :246～267.

[7] 王燕, 李明.基于扩展概念格的分类规则获取算法[J].计算机应用, 2007, 27 (10) :2376～2378.

[8] Kohavi R.Scaling up the accuracy ofNave-Bayes classifiers:A decision-tree hybrid[C].Menlo P, CA:InProceedings of the Second Interna-tional Conference on Knowledge Dis-covery and Data Mining, The AAAIPress, 1996:202～207.

[9] Zheng Z, and Webb GI.Lazy Learn-ing of Bayesian Rules[J].MachineLearning, 2000, 41 (1) :53～84.

[10] Xie Z, Hsu W, Liu Z, et al.ConceptLattice Based Composite Classifiers forHigh Predictability[J].Journal of Ex-perimental and Theoretical ArtificialIntelligence, 2002, 14:143～156.

[11] Murphy PM, Aha DW.UCI Re-pository of Machine Learning Databases[E B].http://www.ics.uci.edu/~mlearn.