论文部分内容阅读
〔摘 要〕本文采用模糊聚类技术,结合《中国图书馆分类法》,尝试建立一种新型的文献自动分类机制。文章采用模块化技术,提出整套系统的设计流程和关键点的设计,并分析了其优缺点。目的是为文献的自动分类探索一种新的思路和方法。
〔关键词〕自动分类;模糊C均值;图书馆专家系统
〔中图分类号〕G254 〔文献标识码〕B 〔文章编号〕1008-0821(2009)09-0166-03
Application of Fuzzy Clustering Technology in
Literature Automatic Classification SystemChu Cunkun Li Tao
(Library,Taishan medical college,Taian 271000,China)
〔Abstract〕In this paper,based on fuzzy clustering technology,combined with“Chinese Library Classification”,the author tried to establish a new mechanism for automatic classification of literature.The article adopts modular technology,the entire system to the design process and the key points of the design and analysis of its advantages and disadvantages.This paper documents for the automatic classification explored a new way of thinking and methods.
〔Key words〕automatic classification;fuzzy c-means;library expert system
自1960年Maron在Journal of ASM发表了有关自动分类的第一篇论文,随后许多著名的情报学家如K.Sparch,G.Salton及R.M.Needham等都在这一领域进行了卓有成效的研究[1]。到目前为止,自动分类在国外大体经历了3个发展阶段:第一阶段(1958-1964)主要进行自动分类的可行性研究;第二阶段(1965-1974)进行自动分类的实验研究;第三阶段1975-至今)进入实用化阶段。但是由于分类方法的不同,这些软件并不能在我国通用。我国的自动分类工作经历了2个阶段,1981年候汉清老师首次对自动分类进行了探讨[2];1991年后以李欣老师为代表的一批人开始了试验软件的研发[3],然而到现在为止,虽然有一些自动化分类软件诞生,但是离社会化、商品化还有一定的距离,尚处于第二阶。究其原因一是开发技术难度比较大,普通图书馆技术人员难以胜任,二是少量开发出的软件推广难度比较大,辛辛苦苦开发出的软件由于各种原因不能被广泛应用,没有信心继续研究。本文尝试将一种广泛使用于图像处理领域的分类算法——模糊聚类技术移植到文献自动分类中来,借以探索新的研发途径。
1 模糊聚类技术简介及移植思路
模糊聚类技术是一种智能分类技术,目前广泛应用在数据挖掘、图像分割、模式识别等领域并取的了良好的效果。它非常适合处理事物内在的不确定性,而且对噪声不敏感;它利用多值逻辑来描述复杂系统,能以更接近人的思维方式准确地对事物进行分类[4]。
模糊聚类技术的典型算法——模糊C均值算法(fuzzy c-means,FCM)是一种较典型的逐点修改迭代的动态聚类算法,其要点是以误差平方和为准则函数。逐点修改聚类中心:一个元素按某一原则,归属于某一组类后,就要重新计算这个组类的均值,并且以新的均值作为凝聚中心点进行下一次元素聚类;逐批修改聚类中心:在全部元素样本按某一组的类中心分类之后,再计算修改各类的均值,作为下一次分类的聚类中心点。
其核心思想是[5]:算法把n个向量xj(1,2,…,n)分为c个组Ci(i=1,2,…,c),并求每组的聚类中心,使得非相似性(或距离)指标的价值函数(或目标函数)达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时,价值函数定义为:
J=∑Ni=1∑Cj=1(μij)mxi-υj2
其中:uik=1+∑Cj=1j≠ixk-υi2xk-υj21/m-1-1(1)
υi=∑Nk=1(μik)m•xk∑Nk=1(μik)m(2)
图书自动分类系统的核心部分是推理机。其任务是模拟分类专家的思维过程,控制并执行对问题的求解。它能根据当前已知的事实,利用知识库中的知识,按一定的推理方法和控制策略进行推理,最后得到分类结果[6]。
结合FCM算法的特点,本文图书自动分类系统推理机的推理流程如下:
第一步:给定分类数C,初始化加权指数m及容许误差εmax,令迭代计数变量p=1;
第二步:初始化聚类中心υi,i=1,2,…,c;
第三步:按式(1)计算隶属度uik,k=1,2,…,C;i=1,2,…,N;
第四步:按式(2)修正所有的聚类中心υk(p+1),k=1,2,…C;
第五步:计算误差:ε=J(p+1)-Jp;
第六步:如果ε<εmax或者p>N则算法结束;否则p=p+1,转向第三步。
算法结束后,可以按下述两种方法对所有的样本分类:
方法一:若ujk>ujk,k=1,2,…,c;i≠k,则将xj归入第i类;
方法二:若xj-vi2 具体推理流程图如图1所示。其中参数C指的是分类数,Ci指第i级共有多少类;j参数控制分类精度,指共分到多少级;m是模糊指数,控制模糊聚类算法的指数,一般取2.0。N是模糊聚类算法的最大循环次数,防止进入死循环。ε参数为一个极小值,控制聚类精度,同时控制分类的精确程度。内循环为FCM算法,外循环控制分类的精度。
2009年9月第29卷第9期现?代?情?报Journal of Modern InformationSep.,2009Vol.29 No.92009年9月第29卷第9期模糊聚类技术在文献自动分类系统中的应用Sep.,2009Vol.29 No.9
2 基于模糊聚类技术的自动分类技术的实现
2.1 总体思路
鉴于本自动分类系统主要面向图书馆工作人员和图书分类的专家,因此该软件的总体设计思想是人机界面友好、系统功能强、分类要快速准确、具有自动学习功能。软件要以菜单驱动,利用词的类分、词语间的关系、词和范畴之间的关系的分类规则通过模糊聚类技术的典型算法——模糊C均值(fuzzy c-means,FCM)算法处理对图书进行自图1 推理流程图
动分类,得到正确的类名和类号,同时给出恰当的解释。
2.2 系统的构成
图书自动分类系统由以下几个部分组成:人机接口及与其他数据库的接口、图书分类知识库、推理机、数据库、解释机、图书分类知识获取机制。其系统框架见图2。图书自动分类系统通过人工输入及从图书馆现有数据库中导入图书文献信息,然后推理机将图书文献信息与知识库中的规则进行匹配、推理、求解,得出此图书文献的分类号,最后由解释机将整个分类的过程输出给用户。
图2 图书自动分类系统的组成
用户接口是系统与一般用户间的界面,由一组程序及相应的硬件组成,用于完成输入输出工作。图书分类专家通过它输入知识,更新、完善知识库;一般用户通过它输入已知事实以及向系统提出的询问;系统通过它输出运行结果、回答用户的询问或者向用户索取进一步的事实。如今,用户界面通常采用友好的WINDOW界面。与数据库的接口是为了充分利用图书馆已经建好的数据库中的有效信息,以尽可能的减少用户的输入量。为了能与多种数据库兼容,与其他数据库的接口通常采用ODBC作为数据库访问的应用程序编程接口,并使用结构化查询语言SQL作为其数据库的访问语言。
知识库存放着作为图书分类标准的知识本体以及相关的规则,如各种推理、判断规则等,用于某种结论的推理、问题的求解,以及对于推理、求解知识的各种控制知识。除此之外,图书分类知识库还包括一些必要的管理功能,主要用于对知识条目的查询、检索、增删、修改、扩充等操作。知识表示是知识库建立的前提。专家系统问题的求解是以知识为基础的。如何将已获得的有关知识以计算机内部代码形式加以合理地描述、存储,以使有效地利用这些知识便是知识表示。知识表示方法有许多种,包括规则、语义网、框架、脚本等[7]。采用何种方法表示分类专家知识的依据其特点而定。《中图法》分类规则作为整个知识库的主要部分,是较为典型的树型结构体系,对知识的组织采用的是从一般到具体、从宽到窄层层划分的方式。因此采用产生式表示法较为有效。
推理机的构成参加本文第二部分模糊聚类技术简介及移植思路。
数据库用于存放人机接口及与数据库接口提供的初始图书文献信息事实以及系统运行过程中得到的中间结果、最终结果、运行信息(如推出结果的知识链)等等。数据库的内容是动态的,在系统开始运行时,它存放的是人机接口及与数据库接口提供的初始事实;在推理过程中它存放每一步推理所得到的结果。推理机根据数据库的内容从知识库选择合适的知识进行推理,然后又把推出的结果存入数据库中。因此,数据库是推理机不可缺少的一个工作场地,同时由于它可记录推理过程中的各有关信息,又为解释机构提供了回答用户咨询的依据。
解释机负责对推理的结果作出必要的解释,以便向用户说明推理过程,使用户接受推理的结果。它由一组程序组成,能跟踪并记录推理过程,当分类结束需要给出解释时它将推理过程通过人机接口输出给用户。
知识获取分人工获取和自动获取。它为知识库的建立、修改知识库中已有的知识和扩充新的知识提供手段。在专家与系统交互过程中,发现需要修改、删除或增加的知识及由此引起的一切必要的改动,都要利用这部分。它是保证系统灵活性的必要部分,直接影响系统的生命力。
2.3 核心程序VC++编程实现
for(i=0;i {
for(j=0;j {
ftemp=0;
for(k=0;k {
ftemp+=pow(adomatrixu[i*nnumpattern+k],fweightm)*adipattern[k*ndimension+j];
}
adocenter[i*ndimension+j]=ftemp;
ftemp=0;
? for(k=0;k {
ftemp+=pow(adomatrixu[i*nnumpattern+k],fweightm);
}
? adocenter[i*ndimension+j]/=ftemp;∥写入聚类中心
}
}
ncycle++;
nProcess=ncycle;
dDelta=delta;
}while(ncycledthreshold);
? sndPlaySound(″d:bird.wav″,SNDASYNC);
return 0;
3 实验结果
分类系统系统完成后,将泰山医学院图书馆R类中随机抽取3 000种图书文献做样本进行分类测试,其中单主题文献1 945种,多主题文献1 055种。通过测试来验证本系统对于主题类型模式相对简单的文献和比较复杂的文献分类准确性,根据在每个推理环节都得出的结果,最终来验证分类效果。
结果对于单主题类型图书的分类精确度达91.3%,对于多主题分类精度62.5%。可见对于单主题类型的图书该系统有较优异的表现,但是对于多主题的文献的分类,表现一般,有待于算法的改进。
4 讨 论
自动分类对于信息处理具有极其重要的意义。随着Web2.0技术发展,网上信息泛滥严重,如果不加以有效整理,人们将难以有效利用,而这是人工无法完成的,我们必须借助自动搜索和自动分类技术对信息进行提取、加工、组织利用。从自动分类研究的发展来看,基于学习的自动分类法有较强的生命力,模糊聚类技术有较强的智能性,故该方案有较大的发展前途。但是难点在于知识库的建立,建立的模式是什么?是基于本体的还是基于树形结构的,以及索引表的建立方法和层次。本系统的优势在于首次尝试将FCM算法移植到图书自动分类系统,可以在一定程度上推动自动分类研究的发展,进一步可以为未来网络文献的自动挖掘、分类探索出一条有益路径。
作者认为基于知识本体的知识库会使分类的准确度会有很大的提高,在未来的发展中具有很 大的潜力,是未来发展的一个方向。
参考文献
[1]Golub K,Hamon T,Ardo A.Automated Classification of Textual Documents Based on a Controlled Vocabulary in Engineering[J].Knowledge Organization,2007,34(4):247-263.
[2]侯汉清.分类法的发展趋势简论[J].情报科学,1981,(1):58-68,30.
[3]李欣,陈星,阎慧,等.图书分类专家系统设计[J].现代图书情报技术,1991,(4):46-47.
[4]Shen S,Sandham W,Granat M,et al.MRI fuzzy segmentation of brain tissue using neighborhood attraction with neural-network optimization[J].IEEE Trans Inf Technol Biomed,2005,9(3):459-67.
[5]罗述谦,周果宏.医学图像处理与分析[M].北京:科学出版社,2003:93.
[6]Yi K.Automated Text Classification Using Library Classification Schemes:Trends,Issues,and Challenges[J].International Cataloging & Bibliographic Control,2007,36(4):78-82.
[7]张惠.图书自动分类专家系统的研究[J].佛山科学技术学院学报:自然科学版,2001,19(2):37-40.
〔关键词〕自动分类;模糊C均值;图书馆专家系统
〔中图分类号〕G254 〔文献标识码〕B 〔文章编号〕1008-0821(2009)09-0166-03
Application of Fuzzy Clustering Technology in
Literature Automatic Classification SystemChu Cunkun Li Tao
(Library,Taishan medical college,Taian 271000,China)
〔Abstract〕In this paper,based on fuzzy clustering technology,combined with“Chinese Library Classification”,the author tried to establish a new mechanism for automatic classification of literature.The article adopts modular technology,the entire system to the design process and the key points of the design and analysis of its advantages and disadvantages.This paper documents for the automatic classification explored a new way of thinking and methods.
〔Key words〕automatic classification;fuzzy c-means;library expert system
自1960年Maron在Journal of ASM发表了有关自动分类的第一篇论文,随后许多著名的情报学家如K.Sparch,G.Salton及R.M.Needham等都在这一领域进行了卓有成效的研究[1]。到目前为止,自动分类在国外大体经历了3个发展阶段:第一阶段(1958-1964)主要进行自动分类的可行性研究;第二阶段(1965-1974)进行自动分类的实验研究;第三阶段1975-至今)进入实用化阶段。但是由于分类方法的不同,这些软件并不能在我国通用。我国的自动分类工作经历了2个阶段,1981年候汉清老师首次对自动分类进行了探讨[2];1991年后以李欣老师为代表的一批人开始了试验软件的研发[3],然而到现在为止,虽然有一些自动化分类软件诞生,但是离社会化、商品化还有一定的距离,尚处于第二阶。究其原因一是开发技术难度比较大,普通图书馆技术人员难以胜任,二是少量开发出的软件推广难度比较大,辛辛苦苦开发出的软件由于各种原因不能被广泛应用,没有信心继续研究。本文尝试将一种广泛使用于图像处理领域的分类算法——模糊聚类技术移植到文献自动分类中来,借以探索新的研发途径。
1 模糊聚类技术简介及移植思路
模糊聚类技术是一种智能分类技术,目前广泛应用在数据挖掘、图像分割、模式识别等领域并取的了良好的效果。它非常适合处理事物内在的不确定性,而且对噪声不敏感;它利用多值逻辑来描述复杂系统,能以更接近人的思维方式准确地对事物进行分类[4]。
模糊聚类技术的典型算法——模糊C均值算法(fuzzy c-means,FCM)是一种较典型的逐点修改迭代的动态聚类算法,其要点是以误差平方和为准则函数。逐点修改聚类中心:一个元素按某一原则,归属于某一组类后,就要重新计算这个组类的均值,并且以新的均值作为凝聚中心点进行下一次元素聚类;逐批修改聚类中心:在全部元素样本按某一组的类中心分类之后,再计算修改各类的均值,作为下一次分类的聚类中心点。
其核心思想是[5]:算法把n个向量xj(1,2,…,n)分为c个组Ci(i=1,2,…,c),并求每组的聚类中心,使得非相似性(或距离)指标的价值函数(或目标函数)达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时,价值函数定义为:
J=∑Ni=1∑Cj=1(μij)mxi-υj2
其中:uik=1+∑Cj=1j≠ixk-υi2xk-υj21/m-1-1(1)
υi=∑Nk=1(μik)m•xk∑Nk=1(μik)m(2)
图书自动分类系统的核心部分是推理机。其任务是模拟分类专家的思维过程,控制并执行对问题的求解。它能根据当前已知的事实,利用知识库中的知识,按一定的推理方法和控制策略进行推理,最后得到分类结果[6]。
结合FCM算法的特点,本文图书自动分类系统推理机的推理流程如下:
第一步:给定分类数C,初始化加权指数m及容许误差εmax,令迭代计数变量p=1;
第二步:初始化聚类中心υi,i=1,2,…,c;
第三步:按式(1)计算隶属度uik,k=1,2,…,C;i=1,2,…,N;
第四步:按式(2)修正所有的聚类中心υk(p+1),k=1,2,…C;
第五步:计算误差:ε=J(p+1)-Jp;
第六步:如果ε<εmax或者p>N则算法结束;否则p=p+1,转向第三步。
算法结束后,可以按下述两种方法对所有的样本分类:
方法一:若ujk>ujk,k=1,2,…,c;i≠k,则将xj归入第i类;
方法二:若xj-vi2
2009年9月第29卷第9期现?代?情?报Journal of Modern InformationSep.,2009Vol.29 No.92009年9月第29卷第9期模糊聚类技术在文献自动分类系统中的应用Sep.,2009Vol.29 No.9
2 基于模糊聚类技术的自动分类技术的实现
2.1 总体思路
鉴于本自动分类系统主要面向图书馆工作人员和图书分类的专家,因此该软件的总体设计思想是人机界面友好、系统功能强、分类要快速准确、具有自动学习功能。软件要以菜单驱动,利用词的类分、词语间的关系、词和范畴之间的关系的分类规则通过模糊聚类技术的典型算法——模糊C均值(fuzzy c-means,FCM)算法处理对图书进行自图1 推理流程图
动分类,得到正确的类名和类号,同时给出恰当的解释。
2.2 系统的构成
图书自动分类系统由以下几个部分组成:人机接口及与其他数据库的接口、图书分类知识库、推理机、数据库、解释机、图书分类知识获取机制。其系统框架见图2。图书自动分类系统通过人工输入及从图书馆现有数据库中导入图书文献信息,然后推理机将图书文献信息与知识库中的规则进行匹配、推理、求解,得出此图书文献的分类号,最后由解释机将整个分类的过程输出给用户。
图2 图书自动分类系统的组成
用户接口是系统与一般用户间的界面,由一组程序及相应的硬件组成,用于完成输入输出工作。图书分类专家通过它输入知识,更新、完善知识库;一般用户通过它输入已知事实以及向系统提出的询问;系统通过它输出运行结果、回答用户的询问或者向用户索取进一步的事实。如今,用户界面通常采用友好的WINDOW界面。与数据库的接口是为了充分利用图书馆已经建好的数据库中的有效信息,以尽可能的减少用户的输入量。为了能与多种数据库兼容,与其他数据库的接口通常采用ODBC作为数据库访问的应用程序编程接口,并使用结构化查询语言SQL作为其数据库的访问语言。
知识库存放着作为图书分类标准的知识本体以及相关的规则,如各种推理、判断规则等,用于某种结论的推理、问题的求解,以及对于推理、求解知识的各种控制知识。除此之外,图书分类知识库还包括一些必要的管理功能,主要用于对知识条目的查询、检索、增删、修改、扩充等操作。知识表示是知识库建立的前提。专家系统问题的求解是以知识为基础的。如何将已获得的有关知识以计算机内部代码形式加以合理地描述、存储,以使有效地利用这些知识便是知识表示。知识表示方法有许多种,包括规则、语义网、框架、脚本等[7]。采用何种方法表示分类专家知识的依据其特点而定。《中图法》分类规则作为整个知识库的主要部分,是较为典型的树型结构体系,对知识的组织采用的是从一般到具体、从宽到窄层层划分的方式。因此采用产生式表示法较为有效。
推理机的构成参加本文第二部分模糊聚类技术简介及移植思路。
数据库用于存放人机接口及与数据库接口提供的初始图书文献信息事实以及系统运行过程中得到的中间结果、最终结果、运行信息(如推出结果的知识链)等等。数据库的内容是动态的,在系统开始运行时,它存放的是人机接口及与数据库接口提供的初始事实;在推理过程中它存放每一步推理所得到的结果。推理机根据数据库的内容从知识库选择合适的知识进行推理,然后又把推出的结果存入数据库中。因此,数据库是推理机不可缺少的一个工作场地,同时由于它可记录推理过程中的各有关信息,又为解释机构提供了回答用户咨询的依据。
解释机负责对推理的结果作出必要的解释,以便向用户说明推理过程,使用户接受推理的结果。它由一组程序组成,能跟踪并记录推理过程,当分类结束需要给出解释时它将推理过程通过人机接口输出给用户。
知识获取分人工获取和自动获取。它为知识库的建立、修改知识库中已有的知识和扩充新的知识提供手段。在专家与系统交互过程中,发现需要修改、删除或增加的知识及由此引起的一切必要的改动,都要利用这部分。它是保证系统灵活性的必要部分,直接影响系统的生命力。
2.3 核心程序VC++编程实现
for(i=0;i
for(j=0;j
ftemp=0;
for(k=0;k
ftemp+=pow(adomatrixu[i*nnumpattern+k],fweightm)*adipattern[k*ndimension+j];
}
adocenter[i*ndimension+j]=ftemp;
ftemp=0;
? for(k=0;k
ftemp+=pow(adomatrixu[i*nnumpattern+k],fweightm);
}
? adocenter[i*ndimension+j]/=ftemp;∥写入聚类中心
}
}
ncycle++;
nProcess=ncycle;
dDelta=delta;
}while(ncycle
? sndPlaySound(″d:bird.wav″,SNDASYNC);
return 0;
3 实验结果
分类系统系统完成后,将泰山医学院图书馆R类中随机抽取3 000种图书文献做样本进行分类测试,其中单主题文献1 945种,多主题文献1 055种。通过测试来验证本系统对于主题类型模式相对简单的文献和比较复杂的文献分类准确性,根据在每个推理环节都得出的结果,最终来验证分类效果。
结果对于单主题类型图书的分类精确度达91.3%,对于多主题分类精度62.5%。可见对于单主题类型的图书该系统有较优异的表现,但是对于多主题的文献的分类,表现一般,有待于算法的改进。
4 讨 论
自动分类对于信息处理具有极其重要的意义。随着Web2.0技术发展,网上信息泛滥严重,如果不加以有效整理,人们将难以有效利用,而这是人工无法完成的,我们必须借助自动搜索和自动分类技术对信息进行提取、加工、组织利用。从自动分类研究的发展来看,基于学习的自动分类法有较强的生命力,模糊聚类技术有较强的智能性,故该方案有较大的发展前途。但是难点在于知识库的建立,建立的模式是什么?是基于本体的还是基于树形结构的,以及索引表的建立方法和层次。本系统的优势在于首次尝试将FCM算法移植到图书自动分类系统,可以在一定程度上推动自动分类研究的发展,进一步可以为未来网络文献的自动挖掘、分类探索出一条有益路径。
作者认为基于知识本体的知识库会使分类的准确度会有很大的提高,在未来的发展中具有很 大的潜力,是未来发展的一个方向。
参考文献
[1]Golub K,Hamon T,Ardo A.Automated Classification of Textual Documents Based on a Controlled Vocabulary in Engineering[J].Knowledge Organization,2007,34(4):247-263.
[2]侯汉清.分类法的发展趋势简论[J].情报科学,1981,(1):58-68,30.
[3]李欣,陈星,阎慧,等.图书分类专家系统设计[J].现代图书情报技术,1991,(4):46-47.
[4]Shen S,Sandham W,Granat M,et al.MRI fuzzy segmentation of brain tissue using neighborhood attraction with neural-network optimization[J].IEEE Trans Inf Technol Biomed,2005,9(3):459-67.
[5]罗述谦,周果宏.医学图像处理与分析[M].北京:科学出版社,2003:93.
[6]Yi K.Automated Text Classification Using Library Classification Schemes:Trends,Issues,and Challenges[J].International Cataloging & Bibliographic Control,2007,36(4):78-82.
[7]张惠.图书自动分类专家系统的研究[J].佛山科学技术学院学报:自然科学版,2001,19(2):37-40.