知识聚类技术

2008年10月沈阳航空工业学院学报Oet. 2008第25卷第5期Joumal of Shenyang Institute of Aeronautical EngineeringVol. 25 No.5文章编号:1007 - 1385(2008)05 -0058 -05知识聚类技术，季锋苗霄霄(沈阳航空工业学院知识工程中心,辽宁沈阳100)4摘要:随着知识管理的不断深人,知识库所 包容的知识内容越来越多,如何建立知识的分类体系,构建合理的知识关联显得尤为重要。知识豪类是- -种 无指导的自动分类方法,在知识的组织和管理中发挥着重要作用,不仅可以有效地节约知识库优化的人力资源，而且还可以更有效的反映知识间的本质联系。为此主要探讨了知识豪类的基本过程,包括知识特征的选取、相似度的计算和豪类算法最后介绍了作者的- -些相关工作。关键词:知识管理;知识豪类;知识库中圈分类号:TP391.1文献标识码:A .随着互联网的不断发展,信息激增和信息超;的知识聚类更具有实用的研究价值。载给用户带来了巨大的压力和焦虑。单纯的面向1聚类分析技术文献和网络资源的信息组织形式已经远远不能满足用户对有效知识的获取和利用。用户更多的是聚类分析是数据挖掘技术中的重要组成部分，需要有价值和意义的情报和知识内容,所以对现它能够在数据中发现令人感兴趣的分布模式。聚类有的信息组织方法的扩充和发展已经上升到知识过程就是将-群( set)物理的或抽象的对象,根据它组织的层面,通过挖掘信息内部更深层次的知识们之间的相似程度,分为若干组( group),其中相似内容,为用户提供更好的知识管理服务。的对象构成-组。一个聚类( cluster),又称簇,就是所谓知识组织就是将知识精炼的过程,是知由彼此相似的一组对象所构成的集合,不同聚类中识管理的重要环节之一。文献[1]提到了七种组对象通常是不相似的。聚类分析就是从给定的数据织方法,包括知识表示、知识重组、知识聚类、知识集中搜索数据对象之间所存在的有价值联系。而在存检、知识编辑、知识布局和知识监控。本文主要许多应用中,一个聚类中所有对象常常可以被当作介绍有关知识对象按其属性类别加以集中整序或-个对象来进行处理或分析。整合的知识聚类过程。作为统计学的一个分支,聚类分析已有多年的人工的知识聚类方法多种多样,包括以学科历史,这些研究主要集中在基于距离的聚类分析方聚类、以主题概念聚类、以人聚类、以用聚类和以面。许多统计软件包,诸如:S - Plus, SPSS和SAS,时空聚类等。人工的知识聚类可以保证知识主题都包含基于k -均值、k -中心等诸多聚类分析方法。划分的合理性、准确性,但在互联网信息(主要是在机器学习中,聚类分析属于一种无指导的学习方网页内容信息)爆炸式增长的前提下,需要支付法。与分类学习不同,无指导学习不依靠事先确定大量的人力资源,另外知识的分类体系的调整是的数据类别,以及标有数据类别的学习训练样本集一个不断迭代的过程,其间还面临对知识分类体合。正因为如此,聚类分析是一种观察式学习法系不断地进行细化和扩充,难以避免人员支出和(eaming by obervation) ,而不是示例式学习法( tea时间支出的无限制增长。而知识聚类技术可将采ming by example)。聚类分析己被应用到许多领域，集到的知识进行无指导的自动分析,有效地将知其中包括:模式识别、数据分析、市场分析等领域,特识按规定的分类标准进行划分,保证了划分的快别是“中国煤化工的一个重要手段速性和准确率。与人工的知识聚类相比,无指导发挥TYHCNMHG收稿日期:2008-03-252知识聚类作者简介:浮锋( 1981 -),男,辽宁葫芦岛人,助教，主要研究方向:信息检索,E - mail:jiduo_ 1@ 163. com。知识聚类是对采集的原始知识集合进行划分的第5期季铎等:知识聚类技术59- -种方法将-一个知识集划分成不同的小类。同类方法可以改善性能。目前,特征选取的研究主要知识要尽量“紧密" ,而类与类之间的知识要尽量“疏是针对文本分类的问题，利用特征与类别间的关远”,目的是发现知识之间最本质的“抱团”性质。当系进行特征的选取,如:互信息、信息增益,X2统对知识进行特征描述之后,知识库中的知识就被投计等()],特征与文本类别相关性高则被保留,不.影为特征空间中的点集，当选定点间的相似性测度相关则被抛弃。而在知识聚类的任务中没有类别函数后,知识聚类的结果即被确定。因此知识聚类信息可以利用,因此就需要采用无指导方法进行可以分为图1中的几个步骤: .特征的选取。基于文档频度的特征选择方法无需任何类别信息,针对每个特征计算包含这个特征的文档的[特餐表示 ][相似性黄皮 ][类][出数目,如果包含某个特征的文档数较低,说明该特征所含的信息量较低,它对区分不同的文档作用圈1聚类过程不是很大,可设定给定阈值过滤此种特征。但该2.1知识的特征选择假设在现实生活中却不- -定成立,因为某个特征知识的特征选择- -般事由领域专家决定使用在多个文档中都出现,反而表明它对区分并没有哪些特征来深刻地刻画知识的本质性质和结构。太大的帮助。这和文档频度方法所基于的假设刚特征选择的结果是-一个输出矩阵,每-行代表一好相反。但即便如此,这个方法在实际应用中仍个知识,每一列代表- 一个特征指标变量。特征选然取得了良好的性能。取的优劣将直接影响以后的知识聚类的分析和决2.2知识的相似性计算策。合理的特征选取方案应当使得同类知识在特给出知识间的相互关系,即两个知识样本间征空间中相距较近，异类知识则相距较远。的相似度或距离。相似度-般定义为界于[0,1]特征选取的方法可以定义如下:给定候选特.之间的一个值,是知识聚类的基础。相似度计算征集合,从中选择某个子集,可以使最终的系统性方法是否反映知识本质间的相关性,将直接决定能最好的子集。特征选取方法基于独立性假设,知识聚类性能的好坏。图2中,不同的知识库A根据某个预先定义评价优劣的准则,从候选特征和B上分别采用不同的相似点计算方法,在A分集合中选取最有信息量的特征2。特征选取方布中基于几何距离相似度的方法最好,而在B分法基于独立性假设,根据给定的评价准则,对每个布中基于余弦距离的聚类结果要好于几何距离。特征分别进行评价,并根据评价的分值按由大到因此,在不同的知识库中需要通过大量的实验找小进行排序,去除得分最小的特征。利用这种方到符合当前样本集合的相似度计算方法”。常法，系统不仅可以对高维的空间进行降维,并且在用的计算方法有Minkowski 距离和Cosine距离某些情况之下(降维程度控制得当，刚好把噪音等,以下仅给出相似度计算公式,更详细内容请参数据去除，而保留所有的有效特征)可以使聚类考有关文献。性能得到改善,也就是说,当去除噪音的收益比特(1)Minkowski距离征选取导致的信息损失来得大的时候,特征选取Minkowski距离是几何上的标准度量单位,定.%|❻几何距离弦距离A205中国煤化工J点分布AHYHCNMHG图2相似度对聚类结果的影响6(沈阳航空工业学院学报第25卷义如下。当p=2的时,得到的是欧几里德距离。每一次改进之后的分组方案都较前一次更好, 而L,(d.,d) =(2 |4. -4.)”(1)所谓“好”的标准就是同一分组中的记录越近越好,而不同分组中的记录越远越好。基于划分的(2)Cosine距离聚类算法主要有K - Means算法、K - Medians算Cosine距离是两向量间夹角的余弦,Cosine法CLARANS算法。距离的一个特性就是它不依赖于表示向量的长(2)层次方法( Hierarchical Method)度。这种特性使得包含有不同特征频度的知识被这种方法对给定的数据集进行层次的分解，等同地看待,其定义如下:直到某种条件满足为止。具体又可分为“自底向cos(u ,02)上”和“自顶向下”两种方案。代表算法有:U●U2BIRCH算法引和CURE算法等。(3)基于模型的方法( Model - Based Meth-2 (weight(u,1)●weight(0,1))od)=基于模型的方法给每一个聚类假定-一个模wigh(n,I".N Seigh(o.r型,然后去寻找能够很好的满足这个模型的数据(2)集[5,9]。这样一个模型可能是数据点在空间中的(3) Kullback - Leibler( KL)距离密度分布函数或者其他。它的一个潜在的假定就KL距离即相对熵,用于比较两个分布的不是:目标数据集是由一系列的概率分布所决定的。同。如果把知识的特征向量看成是两个分布,则可通常有两种方法:统计的方法和神经网络的方法。以用KL距离来表示两分布的相似度。当需要计算(4)基于密度的方法( Density - Based Meth-知识相似度时,一般使用对称的KL距离,其定义如下式:基于密度的方法与其他方法的-一个根本区别是:它不是基于各种各样的距离的,而是基于密度S(x)(d,dj) =(P(t1d,) -P(r1 d)的,这样就能克服基于距离的算法只能发现球型o P(t1d.)聚类的缺点。这个方法的指导思想就是只要-个(3)logP(tI )区域中的点的密度大过某个阙值,就把它加到与2.3聚类算法之相近的聚类中去。代表算法有:DBSCAN算聚类算法是知识聚类中的关键环节。聚类算法[")和OPTICS算法等。法的输出一般是一个聚类谱系图，由粗到细地反(5)混合方法( Mixture Method)映了知识库中知识的分类情况;或者直接给出具该方法是将不同的方法进行融合,以此来获体的知识分类方案,包括总分类数,每类具体包含得更优的性能。Clustering by Commttee (CBC)$]那些知识等等。因此在很多实际应用中需要根据主要观点就是通过两步进行聚类,首先采用复杂所涉及的数据类型、聚类的目的以及具体应用要度较低的方法生成类内紧密相关的小类Commit,求来选择合适的聚类算法。然后在采用传统的方法进行聚类输出。DEN-聚类算法可以分为以下几类:划分法、层次CLUE (Density basted Clustering) 就是结合了划分法、基于密度的方法、基于模型的方法和混合法方法、层次方法和局部方法的一个综合方法。等[4-6,10]。STING方法也结合了基于网格的方法和自上而下(1)划分方法( Pritoning Method)的方法。给定-一个有N个元组或者记录的数据集,划2.4知识聚类的结果表示分方法将构造K个分组(K