基于概念格的分类规则提取算法及其应用

《基于概念格的分类规则提取算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于概念格的分类规则提取算法及其应用8胡立华张继福张素兰太原科技大学计算机科学与技术学院太原030024摘要：概念格是形式背景分析中的核心数据结构，分类规则是数据挖掘一项很重要的任务。本文首先给出了一种分类概念格渐进式构造算法，并在此算法基础上给出了分类规则的提取算法，理论表明了分类概念格要比一般概念格构造的效率高、复杂度小．最后采用恒星天体光谱数据作为形式背景，验证了分类概念格的有效性及分类规则提取的准确性。关键词：概念格分类概念格分类规则最小上界天体光谱数据1引言概念在哲学中被理解为由内涵和外延两个部分所组成的思想单元，基于概念的这一哲学理解，德国的RWille教授于198

2、2年提出了形式概念分析(formalCOllC印tanalysis)⋯，用于概念的发现、排序和显示。在形式概念分析中，概念的外延被表示为属于这个概念的所有对象的集合，而内涵则表示为所有这些对象所共有的特征(或属性)集合，从而实现了对概念的哲学理解的形式化。概念格从本质上描述了对象和特征(属性)之间的关系，表明了概念之间的泛化和例化关系，而其相应的Hasse图则实现了对数据的可视化。概念格以其知识表示的直观、简洁和完备特点而受到研究者的关注，并已在软件工程、知识工程、知识发现等领域得到了广泛的应用∞1。概念格中的每一个节点代表了训练集的子空间，因此非常适合分类规则的提取。但是，在

3、基于概念格的分类规则的提取过程中，往往存在一些冗余规则，这些规则会影响到分类的有效性和准确率。因此，可以通过一定的策略来消除这些冗余规则以提高分类的准确率。本文以概念格作为基础，通过分析了概念格和分类规则之间的关系，给出了一种分类概念格渐进式构造算法，并在此算法基础上给出了分类规则的提取算法，理论表明了分类概念格要比一般概念格构造的效率高、复杂度小。最后采用恒星天体光谱数据作为形式背景，采用VB和Oracle9i为开发工具，设计与实现了基于概念格的恒星光谱数据分类规则挖掘系统，从而验证了分类概念格的有效性及分类规则提取的准确性。2基本概念定义1：一个形式背景定义为三元组K=(O

4、，D，R)，其中。为对象集，D为属性集，R是。与D之间存在的一个二元偏序关系，由这个二元偏序关系可以形成一个概念格L。定30．：由形式背景K构造出的概念格记为L，L中的每个节点称为一个序偶(即概念)，记为C(A，B)，其中AEP(O)称为概念格的外延，B∈P(D)称为概念格的内涵。定Y,3：概念格L对于关系R是完备的，即对于L中的任一节点c(A，B)，满足以下两个条件：(1)“B)=A=B’={a∈OIVbeB，aRbl(2)f’(A)=B=A7=(b∈DIVaEA，aRb)+基金资助：国家自然科学基金(60573075)项目资助。222计算机技术与应用进展·2006定义4：设

5、Cl=(Al，B1)和c2=(A2，B2)是概念格L的两个不同的结点，cl

6、=child(C2)；称c2是Ci的父节点，也可以称C2是ci的父概念，记为C2=father(CI)。3基于分类规则的概念格渐进式构造算法因为分类要由类标号属性确定。因此分类概念格的形式背景与一般概念格的形式背景有所不同，如下定义：定义5．分类形式背景定义为三元组FK=(O，DluD2，R)，其4=o为对象集，Dl为条件属性集，D2为类标

7、号属性集，R是O与DIuD2之间存在的_个二元偏序关系，由这个二元偏序关系可以形成一个分类概念格FL。在一般概念格的渐进式构造过程中，生成的节点有可能不包含类标号属性，此类节点对分类规则的提取没有任何作用，只会增加构造格的时间。因此，在概念格的分类规则提取的过程中，应该将此类节点删除。定义6．在一般概念格中，如果节点C(A，B)不包含类标号属性cIa，即cL畦B，则C(A，B)称为虚节点。定义7．在～般概念格中，如果任一节点C(A，B)的内涵包含类标号属性cla，即cla∈B，则称节点C(A，B)为候选节点。定理．虚节点的父节点仍然是虚节点。证明：分类概念格FL中任一虚节点C(

8、A，B)，若节点C存在父节点Cl(Al，B1)，由定义4可知，BlcB。在概念格的分类提取规则中，若节点c不包含类标号属性，即类标号属性c1醒B，则cl醒Bl，由定义7可知，虚节点C的父节点C，仍然是虚节点。从上面的定义可知，一般概念格的节点可以分为两种节点：虚节点或候选节点。虚节点对概念格分类规则的提取没有任何影响，因此，概念格中的虚节点可以看作分类概念格中的冗余信息。基于上述分析，分类概念格的构造方法是：分类概念格从分类形式背景中构造出来，在分类概念格的渐进式构造过程中，如果生成了虚节点