（管理科学与工程专业论文）基于层次聚类的科技项目分类与查重研究.pdf

内容摘要 科教兴国是我国的一项重要基本国策。国家每年都会投入大量的人力、物力、财力等 资源用于各类科技项目的研究与开展。科技项目的立项、研究过程直至最终产生的科研成 果所带来的科学价值、经济价值以及社会价值都直接影响着科学技术以及社会的发展。随 着国家以及各地方政府对科技项目投入的经费逐年增加，科技投入范围的逐步扩大，我国 的科学技术生产力得到了快速发展，但是随之而来的还有种种管理上的难题。 对科技项目的正确评估审查是保证国家资源能够得到科学合理配置的重要手段之一。 因为不同领域的科技活动分别具有不同的科技特征，所以如果能采用科学合理的科技项目 分类模型对科技申报项目进行分类处理，就可以为不同领域项目的财务评审、风险评估等 等提供基本的分类依据，而在此基础上所建立的各类科技项目的评审模型也会变得更加有 针对性，从而加强了科技项目评审的科学性与准确性。 基于层次聚类的科技项目分类模型在对项目进行聚类处理时，首先通过比较项目申报 书的关键词词频统计向量对项目之间的相似度进行计算；然后将所得的相似度分布曲线用 最小二乘法对其进行拟合，并求得曲线的拐点作为层次聚类的阈值参数；最后使用层次聚 类算法在不同的粒度下逐层聚类，构造成层次树形结构，实现了不同粒度下的项目分类。 在对科技项目进行同类项目查找时，运用广度优先搜索算法对聚类处理所得到的层次 树进行搜索，可以极大地提高相似项目查找的速度和效率，也可以高效、准确地查找出高 于相似警戒阈值的类似项目，向项目评审者提供预警，防止同类科技项目重复立项，造成 国家资源配置上的浪费。 关键词：层次聚类相似度度量信息粒度最小二乘法 a b s t r a c t t oi n v i g o r a t et h ec o u n t r yt h r o u g hs c i e n c ea n de d u c a t i o ni sab a s i cs t r a t e g yo fo u r c o u n t r y al a r g en u m b e ro fh u m a nr e s o u r c e s 。m a t e r i a lr e s o u r c e sa n df i n a n c i a lr e s o u r c e sa r e p u ti n t od i f f e r e n tk i n d so fr e s e a r c ha n dd e v e l o p m e n ti no u rc o u n t r y s c i e n t i f i c ，e c o n o m i ca n d s o c i a lv a l u ec o m i n gf r o ms c i e n t i f i ca n dt e c h n o l o g i c a lp r o j e c th a sd i r e c ta n di m p o r t a n te f f e c t o nt h ed e v e l o p m e n to fs & ta n ds o c i e t y w i t hm o r ea n dm o r eo u t l a yp u ti n t ot h es & t p r o j e c t sa l lo v e ro u rc o u n t r ya n de x p a n s i o n o ft h ei n p u t ，t h es c i e n t i f i ca n dt e c h n o l o g i c a l p r o d u c t i v i t yh a v eb e e ni m p r o v e df a s ta n dt h e r e f o r ew ee n c o u n t e rm a n yp r o b l e m si n m a n a g e m e n t t h ee v a l u a t i o na n de x a m i n a t i o no fs & t p r o j e c t si sa ni m p o r t a n tw a yt od i s t r i b u t e n a t i o n a lr e s o u r c e ss c i e n t i f i c a l l y s & ta c t i v i t i e si nd i f f e r e n tf i e l d sh a v ed i f f e r e n t c h a r a c t e r i s t i c s c l a s s i f y i n gt h es & tp r o j e c t sw i t hs c i e n t i f i ca n dr e a s o n a b l em e t h o dc a n p r o v i d eb a s i sf o rf i n a n c i a la n dr i s ke v a l u a t i o ni nd i f f e r e n tf i e l d s a 1 lk i n d so fm o d e l sw i l l b e c o m em o r ep e r t i n e n t s c i e n t i f i ca n da c c u r a t et ot h es & tp r o j e c t se v a l u a t i o n t h es c i e n t i f i ca n dt e c h n o l o g i c a lp r o j e c tc l a s s i f y i n gm o d e lb a s e do nh i e r a r c h i c a l c l u s t e r i n gf i r s t l yc a l c u l a t et h es i m i l a r i t yo ft h ep r o j e c t st h r o u g hm a k i n gc o m p a r i s o nb e t w e e n t h e i re i g e n v e c t o r sc o m p o s e do ft h ek e y w o r d sf r e q u e n c ys t a t i s t i c a li n f o r m a t i o n s e c o n d l yi t u s et h el e a s t s q u a r em e t h o dt of i tt h es i m i l a r i t yd i s t r i b u t i o nc u r v ea n dg e tt h ei n f l e c t i o n p o i n t so ft h i sc u r v e l a s t l yi tb u i l d sah i e r a r c h i c a lt r e et h r o u g ht h eh i e r a r c h i c a lc l u s t e r i n g m e t h o da n dr e a l i z e sp r o j e c tc l a s s i f i c a t i o nw i t hd i f i e r e n tg r a n u l a r i t y w h e ns e a r c h i n gs i m i l a rp r o j e c t s ，s e a r c h i n gt h eh i e r a r c h i c a lt r e eg e tf r o mc l u s t e r i n gb y u s i n gb r e a d t h - f i r s ts e a r c ha l g o r i t h mc a ni m p r o v e t h es p e e da n de f f i c i e n c yg r e a t l y i ta l s oc a n f i n do u te x a c t l yt h es i m i l a rp r o j e c t sw h o s es i m i l a rt h r e s h o l da r eh i g h e rt h a nt h eg u a r d t h r e s h o l da n dp r e v e n tt h es i m i l a rp r o j e c t sb e i n ge s t a b l i s h e dr e p e a t e d l y ，w h i c hm a k e saw a s t e o nr e s o u r c ed i s t r i b u t i o n k e yw o r d ：h i e r a r c h i c a lc l u s t e r i n g ；s i m i l a r i t ym e a s u r e m e n t ；g r a n u l a r i t y ；l e a s t - s q u a r e m e t h o d n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人己经发表或撰写过的研究成果，也不包含为获得天津财经大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：疑歙 签字日期：沙。8 年r 月7 日 学位论文版权使用授权书 本学位论文作者完全了解天津财经大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权天津财经大学可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：殳每免 导师签名：少计氐 1 夕 签字日期：沁g 年上月7 日签字日期：磁年j 月7 日 学位论文作者毕业后去向： 工作单位：电话： 通讯地址：邮编： 第1 章导论 1 1 研究的目的和意义 科技项目的开展是实施我国科技计划的一种具体表现形式，项目的立项、研究过程及 最终产生的科学价值、经济价值和社会价值都对科学技术及社会的发展有着直接影响。因 此，国家每年都投入了大量的人力、物力、财力资源用于各类科技项目的研究。近年来， 国家以及各地方政府对科技项目投入的经费逐年增加，科技投入范围也逐步扩大，大大促 进了我国的科学技术生产力的发展，加快了社会的进步。但是随之而来的种种管理上的难 题也摆在了科技项目主管部门的眼前。 目前我国对科技项目的扶助计划主要包括8 6 3 计划、9 7 3 计划、星火计划、火炬计划、 科技型中小企业技术创新基金等，各地方政府也分别建立了不同的基金计划来支持地方科 技发展和国家科技发展。在每年的科技项目资格审查时，科技项目主管部门需要对大量的 科技申报项目进行严格的资格审核，审核合格后才能够立项并进行后期的监管。对科技项 目的审核主要包括对于申报科技项目单位的财务状况审核、财务风险预测、团队能力审核、 立项风险评估等等。由于不同领域的科技项目拥有不同的科技活动特征，如果采用千篇一 律的评审方法来处理所有的科技项目，势必会忽略不同类型的科技活动的特征，使得评价 结果产生错误的导向，进而造成错误的资源配置，并最终影响到整个社会的科技发展。如 何能够更公平有效地对申报项目进行审核，合理分配经费资源成为了亟待解决的一个问 题。 在进行项目评审前，有必要根据科技项目申报书所提供的项目应用领域、主要研发内 容、技术路线、项目成果等信息对科技项目进行分类处理，从而为项目的分类评审提供依 据。在对项目进行分类的基础上，对不同类别项目的财务状况特征、财务风险特征、团队 能力特征、风险监控特征等进行分析和总结，建立财务状况审核、财务风险预测、团队能 力审核、立项风险评估等项目评审模型，为专家对项目的评估、比较提供准确可靠的决策 支持，加强科技项目评审的科学性与准确性。 此外，在对科技项目进行查重处理时，仅仅依靠专家对以往大量的历史项目的记忆和 经验来判断，显然存在着效率低下、科学性缺失等种种问题。在对科技项目进行科学合理 分类的基础上，可以高效、准确地找出与其有同类可比性的历史项目，为专家对项目的评 估、比较提供准确可靠的参考数据，减轻专家的负担，也可以从一定程度上尽力减少项目 ， 1 评审过程中的主观性和不公平性，提高评审的效率。在对新申报的项目进行分类的同时， 也可以迅速准确地将其同历史项目进行比较查重，防止同类相似项目重复立项，造成资源 配置上的浪费。 在对科技项目按领域分类后，还可以对历年的项目申报、资金投入、项目开展等情况 进行统计分析，从而对近年的科技发展趋势得到全面掌握，并将其与国家的的科技发展规 划战略联系起来，为科技项目工作的开展提供依据，有利于国家科技领域发展战略目标的 实现。 1 。2 国内外的研究现状 对科技项目分类的主要依据来自项目申报书中所包括的各项文本信息，也就是说对科 技项目的分类实际上就是对项目申报书中进行文本分类处理。自动文本分类是文本挖掘中 的一个重要内容，它是指按照预先设定的分类体系，根据文本的内容通过自动文本系统为 文本集合中的每个文本确定一个类别，帮助人们更好地寻找所需的信息和知识。自动文本 分类是人工智能技术和信息获取( i n f o r m a t i o nr e t r i e v a l ) 技术相结合的研究领域，是进 行基于内容的自动信息管理的核心技术。 国外在文本自动分类这一领域起步较早。上世纪五十年代，h p l u h n 在文本分类这一 领域进行了开创性研究，他提出了词频统计思想，主要用于自动分类。1 9 6 0 年，m a r o o n 发 表有关自动分类的第一篇论文。1 9 6 2 年，博科( h b o r k o ) 等人提出利用因子分析法进行文 献的自动分类。之后，k s p a r c k 、g s a l t o n 以及r m n e e d h a m 、m e l e s k 、k s j o n e s 等众 多学者在这一领域进行了更为深入的研究工作。这些方法主要是从文本的词频统计分析、 句法分析以及语义分析三个层次上进行研究。其中，以基于词频统计分析的自动分类试验 较为成功。但是这些分类方法大都只是停留在理论方面的探讨，很少投入到实际的应用当 中。到了上世纪八十年代，自动文本分类则主要是以知识工程的方法为主，根据领域专家 给出的文本分类经验知识，构建知识库、规则库以及文本分类器，作为计算机自动进行文 本分类的依据。日本庆应义塾大学文学系的图书情报专业和同本i b m 东京基础研究所合作 开发了一个自动分类专家系统，该专家系统实现了图书资料的自动分类。进入九十年代， 基于统计的自动文本分类方法成为了主流，它在准确率和稳定性方面都具有非常明显的优 势。基于统计方法的自动文本分类模型如图1 1 所示，系统使用训练样本进行特征选择和 。刘斌，黄铁军，程军等一种新的基于统计的自动文本分类方法川中文信息学报，2 0 0 2 年第1 6 卷第6 期：1 9 2 分类器训练。系统根据选择的特征形式化待分类的输入样本，然后输入到分类器进行类别 判定，最终得到输入样本的类别。 图1 1 基于统计方法的自动文本分类模型 资料来源：刘斌，黄铁军，程军一种新的基于统计的自动文本分类方法2 0 0 2 年第1 6 卷第6 期：1 9 基于统计方法的自动文本分类方法首先要将待分类的文本信息以计算机可以理解并 进行处理的形式进行形式化表示。目前，主要应用的文本信息形式化表示方式主要包括语 义网络方法、框架模型方法、本体表示法等等。 ” ： 上世纪八十年代分类器构使用的多为基于知识工程的规则方法，现在主要使用的是基 于统计学习的方法和基于机器学习的方法，主要包括决策树、关联规则、聚类分析、k 近惫 邻、贝叶斯方法、基于数据库的算法、支持向量机、神经网络、粗糙集、模糊逻辑、符号 规则学习、归纳学习算法和休眠专家方法等等。，。? 其中，聚类分析是在对文本提取特征属性后，选取划分法、层次法、基于密度的方法、 基于网格的方法和基于模型的方法当中一种或几种方法对文本进行特征分类，它是对数据 建模从而简化数据的一种方法，力求能够简单、稳定、低代价地逼近人类的分析判断能力。 模糊逻辑提供处理由于模糊而不是随机产生的不精确，不确定性的算法，粗糙集则处理由 于不可分辨关系所导致的不确定性，神经网络用于模式分类与聚类，而遗传算法则用于优 化和搜索。 m i y a m o t os f f ：2 0 0 1 年提出了一种基于模糊多集( f u z z ym u l t i s e t s ) 的文档软聚类方 法，并成功地应用在了信息检索过程中； f u z z y a r t 的软聚类算法，则取得了比基于f c m 更有效的结果；a n u p a mj o s h i 等人提出了一种鲁棒性较好的模糊聚类的方法。 与国外相比，国内对中文文本聚类的研究起步较晚，在上世纪九十年代中期才开始自 动文本分类领域的研究。哈尔滨工业大学、东北大学、山西大学、上海交通大学等对于文 本的处理如摘要、分类、分词等进行了研究，并且己经取得了初步的成果，但对于文本聚 。刘斌，黄铁军，程军等一种新的基于统计的自动文本分类方法【j 1 中文信息学报，2 0 0 2 年第1 6 卷第6 期：1 9 3 类大多仍处于探讨的阶段。2 0 0 2 年，中科院的陈宁等人提出了基于模糊概念图的聚类方法， 李家福等人于同年提出模糊c 一均值算法( f u z z yc m e a n s ，f c m ) 来解决汉语文本聚类的问题， 之后黄钢石等人又于2 0 0 4 年提出了一种基于球型模糊c 一均值算法来实现对中文文本的聚 类问题。复旦大学和中科院计算所对t r e c 测试中的分类任务进行了长时间的跟和深入地 研究，北京大学和清华大学较早在搜索引擎“天网”上研究网页分类技术。支持向量机也 是近年来国内研究较多的一种文本分类方法，但是它的训练收敛速度较慢，而且还需要大 量的存储资源和很高的计算能力，存在着一定的制约性。 当今世界处在一个信息爆发的时代。科技的进步，尤其是信息产业的快速发展，把我 们带入了一个崭新的信息时代。随着文本信息的快速增长，文本自动分类已经成为组织和 处理大量文档数据的关键技术，在各个领域得到了极其广泛的应用。使用数据挖掘手段对 文本进行自动分类，并对其进行类别特征信息描述，已经逐渐成为趋势。但是，随着信息 量的猛增，人们对于文本分类和搜索的准确率和查全率等方面的要求越来越高，因而对文 本分类技术的科学性和准确性的要求页越来越高，如何构造一个高效准确的文本分类系 统，从中提取有价值的知识，进一步提高信息的利用率，已经成为文本挖掘的一个主要研 究方向。 1 3 本文的创新之处及内容安排 1 3 1 本文的创新之处及研究方法 ( 1 ) 文本相似度计算 对项目信息进行形式化表示，构造项目基本信息本体，学科领域本体，项目承担人本 体、项目承担单位本体，在此基础上建立项目本体相似度计算模型，并且使用最小二乘法 对模型进行修订。 ( 2 ) 项目聚类 基于项目相似度，对项目进行聚类处理，借用粒度概念，使用改进的层次聚类方法和 k 中心点算法相结合进行平衡迭代归约和聚类，建立聚类层次树，同时支持增量聚类处理。 阈值的选取不再仅仅依靠以往经验，而是建立文本相似度取值曲线，使用最小二乘法 对曲线进行拟合，并求出曲线的拐点。鉴于在曲线的拐点处，曲线趋势特征发生了明显变 化，将拐点处取值作为阈值，减少聚类的迭代次数，改善聚类的效果。 ( 3 ) 项目查重 4 以改进的广度优先搜索算法对聚类结果层次树进行搜索，通过不同相似阈值的选取， 在不同的粒度上，选取与目标项目存在不同程度相似性的同类项目。 1 3 2 本文的内容安排 本文主要由以下研究内容组成： ( 1 ) 对科技项目申报书中的信息进行分析和研究，采用本体知识表示方法对其进行 描述，将其表示为计算机可以理解的形式，为科技项目的相似度比较模型提供数据依据。 ( 2 ) 对现有的聚类算法进行分析比较，选取适用的聚类算法； ( 3 ) 构建科技项目的相似度比较模型，并使用最小二乘法对其进行修订； ( 4 ) 建立项目相似度取值曲线，使用最小二乘法对曲线进行拟合，并求出曲线的拐 点，将拐点处取值作为阈值，然后使用基于粒度原理的层次聚类算法对项目进行聚类，并 对增量聚类算法进行研究，实现相似项目的比较与查重。 第2 章科技项目的本体表示 2 1 科技项目的知识获取 对科技项目信息进行管理是科技项目立项、项目实施和保障科技经费有效使用和科技 项目顺利完成的基础。科技项目的信息来源主要是科技项目申报书，它是实现科技项目分 类的主要依据，我们需要先将科技项目申报书中的大量文字性内容进行标准化处理，将其 以计算器可以理解的方式形式化，为文本分类提供基础的数据。科技项目申报书中的各类 信息大都属于说明性知识，主要包括项目基本信息、项目承担人信息和项目承担单位信息。 项目基本信息是对项目整体的基本描述，主要包括项目名称、项目性质、应用产业领域、 技术来源、开发内容、等等。项目承担人信息主要包括个人的一些基本信息以及同承担项 目相关的一些学术背景信息：姓名、学历、专业、承担任务、以往项目概况等等。项目承 担单位信息主要包括项目承担单位的单位名称、单位性质、以往项目概况等信息。 2 2 确定概念间的联系 本体( o n t o l o g y ) 来源于哲学概念，原意为客观存在的一个系统的解释或说明，反映了 客观现实的抽象本质。n e c h e s 等人将本体的概念引入了人工智能界，他们将本体定义为“给 出构成相关领域词汇的基本术语和关系，以及利用这些术语和关系构成的规定这些词汇外 延的规则的定义 。1 9 9 3 年，g r u b e r 给出的本体定义为“本体是概念化的明确的规范说明”。 本体通过对领域知识的共同理解抽象出相关的领域概念，得到独立于具体的环境状态的概 念模型，对所抽象出的概念以及概念之间的联系都有着明确严格的定义。它体现的是相关 领域中共同认可的、可共享的知识，并以计算机能够理解的形式将概念模型表示出来，实 现知识的共享。 从科技项目申报书中我们获得了大量说明性的知识，基于充分理解与深入分析科技项 目领域知识的基础，可以在这些非形式化的领域知识信息资源中提出构建领域本体的重点 概念和概念间的关系，并且以此形成原型领域本体的主要概念和关系，对原有的知识信息 进行形式化的表示。 通过对科技项目领域知识的分析，我们可以建立了以下几种本体，分别是科技项目基 本信息本体p r o j e c t o n t o l o g y 、项目申请人本体u n d e r t a k e r o n t o l o g y 和项目承担单位本体 6 c o r p o r a t i o n o n t 0 1 0 9 y 、以及学科领域本体s u b j e c t o n t o l o g y 。 通常用类来描述领域中涉及的概念。类由类的名称( 即所代表的概念的名称) 和类的属 性两部分组成，属性用来描述类所具有的特征。类可以具有多个属性，不同的类可以具有 相同的属性，一个属性具有预设的数据类型或用户自定义的数据类型。 2 3 项目本体描述及实现 2 3 1 项目基本信息本体描述及实现 在科技项目基本信息本体p r o j e c t o n t o l o g y 中，确定的类包括项目类、申请人类、研 究内容类、技术来源类等等。项目类的属性有项目编号、项目名称、项目承担人、承担单 位等；项目承担人类的属性包括项目承担人的姓名、年龄、学历、职称等；项目承担单位 的属性包括项目承担单位的名称、性质、所属系统等；技术内容类的属性包括学科领域关 键词向量等等。它的本体结构如图2 1 所示。 图2 1 科技项目基本信息本体结构图 资料来源：华斌，何丽科技项目验收评估管理与决策模型研究 j 科学学与科学技术管理，2 0 0 7 年 第2 期：3 3 - 3 5 从图2 1 中可以看出，p r o j e c t o n t o l o g y 本体中包含的研究内容类、技术来源类等等 主要使用了关键词的特征向量来表示，使用r d f 容器中的r d f ：b a g 对其进行描述。 o w l 是w 3 c 推荐的一种标准w e b 本体描述语言，可被用于明确表示词汇体系中的概念 及概念问的关系，它遵循x m l 语法，语法较容易理解，简单易用，在编码完成之后可以对 7 语言的一致性、可扩展性等方面进行检查。下面是采用o w l 语言对科技项目信息本体进行 描述的部分代码。 l 1 1 2 3 2 项目承担人本体描述 项目承担人本体用u n d e r t a k e r o n t o lo g y 表示，是对所有的项目申请人信息进行共享和 管理的基础。u n d e r t a k e r o n t o l o g y 描述的基本信息主要包括：姓名、年龄、性别、技术职 称、工作单位、最高学历、研究领域、以往项目概况( 包括：以往项目名称、项目类别、 项目应用领域、项目完成状况、在项目中所处的角色) 等。其中，将项目申请人的以往项 r 目概况用类s t a t u s o f p r o j e c t 来描述，用r d f 容器中的r d f ：b a g 来描述近期完成的项目的 集合。u n d e r t a k e r o n t o l o g y 的本体结构如图2 2 所示：。 图2 2 项目承担人本体结构图 资料来源：华斌，何丽科技项目验收评估管理与决策模型研究 j 科学学与科学技术管理，2 0 0 7 年 第2 期：3 3 3 5 2 3 3 项目承担单位本体描述 项目承担人本体用c o r p o r a t i o n o n t o l o g y 表示，描述的基本信息主要包括项目承担单 位的单位名称、单位性质、所属系统、以往项目概况( 包括：以往项目名称、项目类别、 项目应用领域、项目完成状况、在项目中所处的角色) 等。其中，以往项目概况用类 s t a t u s o f p r o j e c t 来描述，用r d f 容器中的r d f ：b a g 来描述近期完成的项目的集合。 图2 2 项目承担单位本体结构图 9 资料来源：华斌，何丽科技项目验收评估管理与决策模型研究 j 科学学与科学技术管理，2 0 0 7 年 第2 期：3 3 3 5 2 3 4 学科领域本体描述 由于不同学科领域方向的项目在研究方式、研究过程、研究成果等方面都存在着较大 的差异性，因此，项目的应用学科知识结构成为了判定项目类别的重要依据。为了确定某 个项目的应用学科知识结构，必须先对学科领域知识进行划分。 中华人民共和国国家标准g b t 1 3 7 4 5 - 9 2 将学科分类为三级，其中一级学科分成数学、 信息科学与系统科学、力学、物理学、化学、医学等5 8 个，每个一级学科又划分成若干 个二级学科，每个二级学科可以分成若干个三级学科。以一级学科材料科学为例，它被划 分成材料科学基础学科、材料表面与界面( 包括表面优化技术) 、材料失效与保护( 包括材 料腐蚀、磨损、老化、断裂及其控制等) 、材料检测与分析技术、材料实验、材料合成与 加工工艺、金属材料、无机非金属材料、有机高分子材料、复合材料、材料科学其它学科， 共1 1 个二级学科，再以其中的材料表面与界面为例，它又被分为材料失效与保护( 包括材 料腐蚀、磨损、老化、断裂及其控制等) 、材料检测与分析技术、材料实验和材料合成与 加工工艺4 个三级学科。 g b t 1 3 7 4 5 9 2 标准中的每个学科可以用一个学科领域本体s u b j e c t o n t o l o g y 来描述。 学科领域本体描述的信息主要包括学科编号、学科名称、学科级别、学科关键词特征向量、 下级学科等等。 图2 3 学科领域本体结构图 资料来源：华斌，何丽科技项目验收评估管理与决策模型研究 j 科学学与科学技术管理，2 0 0 7 年 第2 期：3 3 - 3 5 1 0 2 4 本章小结 这一章主要以科技项目申报书为主要信息知识来源，对科技项目的领域信息进行了分 析与研究，描述并实现了科技项目基本信息本体p r o j e c t o n t o l o g y 、项目申请人本体 u n d e r t a k e r o n t o l o g y 和项目承担单位本体c o r p o r a t i o n o n t o l o g y 、以及学科领域本体 s u b j e c t o n t o l o g y ，将待分类的文本信息( 科技项目申报书) 以计算机可以理解并进行处理 的方式进行了形式化表示，特别是关于项目研究内容类、技术来源类中特征词向量的描述， 为基于关键词词频统计的项目相似度的计算以及项目的聚类提供了依据。 第3 章聚类算法研究 3 。1 聚类分析 聚类( c l u s t e r i n g ) 是对物理的或抽象的对象集合分组的过程。它采用数学方法对数 据对象属性间的相似度进行定量分析，从而以此为据将一个数据集合理地划分为若干簇， 使得同簇内部的任意两个对象之间尽可能地相似，而不同簇中的两个对象之间则尽可能地 相异。相异度可以根据描述对象的属性值计算，在很多方法中都选择以对象间的距离作为 距离指标。使用聚类生成的簇来对原数据集合进行描述，可以有效地使问题简化。聚类的 形式化描述如下： 假定待分类的数据集合x = x ，ii = l ，2 ，n ，其中，x ，是数据对象，根据数据 对象属性之间的相似度将数据集合划分为k 簇，使其满足下列条件： c ( i ) fi = l ，2 ，k ) ，其中，c ( i ) 为生成的簇； c ( i ) x ； c ( i ) nc ( j ) = a ； k uc ( i ) = x 。 i = l 聚类分析是数据分析中的一种重要技术，它的主要研究内容就是从给定的数据集合中 研究数据对象之间的内在联系。 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。作为多元统计分 析的主要分支之一，聚类分析已经被研究了很多年，主要集中在基于距离和基于相似度的 聚类方法。传统的统计局类分析方法主要包括系统聚类法、分解法、加入法、动态聚类法、 有序样本聚类法、有重叠聚类法以及模糊聚类法等等。采用k 一均值、k 一中心点等算法的聚 类分析工具已经被加入到了许多著名的统计分析软件包当中，比如说s p s s 、s a s 等等。 从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督的学习过程。与分 类不同，无监督学习不依赖预先定义的类或者带有类标记的训练实例，必需要由聚类学习 算法自动确定标记，而分类学习的实例或数据对象都有类别标记。聚类是观察式的学习， 而不是示例式的学习。也有人将聚类成为概念聚类。在概念聚类中，只有当一组对象可以 被某个概念描述时，才会形成一个与之相对应的簇。当聚类对象可以动态地进行增加时， 这类概念聚类就是概念形成。不同于统计学中的基于距离的方法，概念聚类首先要发现合 1 2 适的簇，然后才可以形成对簇的描述。 作为数据挖掘的重要手段之一，聚类分析目前已经被广泛地应用在许多的领域当中， 主要包括模式识别、数据分析、信息检索、文本挖掘、医学诊断、客户关系管理( c r m ) 、 图像处理、市场分析、入侵检测、文档分类等等。通过聚类分析，可以发现整个数据集合 的分布状态，观察得出每一簇数据的特征，找出数据对象属性间内在的有价值的联系，为 进一步的数据挖掘工作( 例如关联规则) 提供依据。举例来说，在客户关系管理( c r m ) 系统中，通过对客户关系数据库进行聚类分析，将客户按照不同的消费习惯、消费水平等 等分成不同的客户群体，并且对这些群体的特征进行描述，为使市场分析人员提供信息支 持。在地理学中，通过对数据库中各地域的地表、湿度、环境等等一系列地域特征数据进 行聚类分析，可以用来将各个地域按不同地域类型进行分类，还可以分析出具有相似地域 特征和使用途径的区域，在进行某种土地应用规划时为决策者提供多种备选方案。在文本 分类中，通过聚类分析，可以在海量的数据中，找出描述同类信息的文本，并且对它们所 描述的信息特征进行描述，为下一步的深层数据挖掘提供依据。 3 2 主要聚类算法分析 数据挖掘中的聚类算法主要面对的是大型数据仓库，这就要求其具有良好的可扩展 性。良好的聚类算法应该具有能够发现任意形状簇的能力，尽量减少来自孤立点以及“噪 声”的干扰，消除对数据顺序的敏感性。 目前常用的聚类方法主要包括以下几种：划分法、层次法、基于密度的方法、基于网 格的方法、基于模型的方法等等。 3 2 1 划分方法( p a r t i t i o n i n gm e t h o d ) 划分方法的主要思想是将一个具有n 个数据对象的数据集，按照对象之间的相似度通 过迭代将数据分成k 个划分块，每个划分块作为一个簇，使得目标函数最小化。这种聚类 方法要求经过划分得到的簇要满足以下两个条件： ( 1 ) 每个簇至少包含一个数据对象； ( 2 ) 每个数据对象必须属于且仅属于一个簇。 但是模糊聚类中对于条件( 2 ) 要求并不是那么的严格。划分方法首先需要给定要划 分的簇的数目k ，并且创建出一个初始的划分。然后再使用一种迭代的重定位技术，尝试 。李雄飞，李军擞据挖掘与知识发现【m 】北京：高等教育出版社，2 0 0 3 年：9 3 通过对象在划分间的移动来改进划分，使得在簇内的对象之间尽可能地相似，而不同簇的 对象之间尽可能地相异。 为了能够得到全局最优的结果，基于划分的聚类会要求穷举所有可能的划分。常见的 划分方法主要有k 一平均算法和k 一中心点算法，其它的划分方主要都是受到这两种方法的 启发： ( 1 ) k 一均值算法( k - m e a n s ) 。 在该算法中，每个簇用该簇中对象的平均值或者加权平均值c ；( 质心) 作为簇c ；的代表 点。k 一均值算法不适合用于处理分类属性数据，但是对数值属性数据却有较好的几何和统 计意义。 k 一均值算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小 化，从而使生成的簇尽可能地紧凑和独立。首先，随机选取k 个对象作为初始的k 个簇的 质心；然后，将其余对象根据其与各个簇的质心的距离分配到最近的簇；再求新形成的簇 的质心。这个迭代过程不断重复，直到下列目标函数最小化： 丘 且= 0p c ；1 1 2 3 1 i - 1 ，e f 其中，e 是数据集中所有对象的平方误差的总和；k 为目标簇的个数；p 为数据集合中 的数据对象( 可以是多维的) ，c ；为簇q 的平均值。 卜均值算法尝试找出使平方误差总和函数值最小的k 个划分。在结果簇密集，簇与簇 之间具有较明显的差别时，能够得到较好的聚类效果。面对大规模数据集，该算法是相对 可扩展的，并且具有较高的效率。算法的复杂度为o ( n k t ) ，其中，m 为数据集中对象的数 目，k 为期望得到的簇的数目，t 为迭代的次数。通常情况下，该算法会终止于局部最优 解。 k 一均值算法存在着一定的制约条件，它不适用于处理分类属性数据，且在聚类前必需 先给出期望生成的簇的数目k ，但是在很多实际应用中，并不能事先确定期望生成的簇的 数目。由于k 一均值算法是基于簇的质心的方法，因此，它对于球形分布的数据样本具有较 好的聚类效果，而对于那些非球形的数据样本的聚类效果则较差。此外，它对孤立点和“噪 声 也较为敏感，当数据对象中存在极大值时，将对质心的计算产生很大的影响，很可能 极大地扭曲数据的分布。 ( 2 ) k 一中心点算法( k - m e d o i d s ) 1 4 与k 一均值算法选用簇的质心作为簇中其它对象的参照点不同，k 一中心点算法使用位置 最接近簇中心的一个对象( 中心点) 作为簇的代表点。 k 一中心点算法的核心思想是先随机选取k 个对象作为初始的k 个簇的代表点，将其余 对象根据其与代表点对象的距离分配到最近的簇，然后，反复用非代表点来代替代表点， 以改进聚类质量。k 一中心点算法的目标函数仍然可以采用公式3 1 中的平方误差准则。 常见的k 一中心点算法有p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 算法、c l a r a ( c l u s t e r i n g l a r g e a p p li c a t i o n ) 算法、c l a r a n s ( c l u s t e r i n gl a r g ea p p li c a t i o nb a s e du p o n r a n d o m i z e ds e a r c h ) 算法。由于采用簇的中心点取代质心来代表一个簇，所以它可以用来 处理分类属性数据，且簇的形成不再容易被极端数据所影响，因此它对于孤立点和“噪 声 的敏感度也相对降低，使得k 一中心点算法比k 一均值算法更为健壮。但是，由于k 一中 心点算法需要不断迭代寻找更好的中心点，因此它的执行代价也比较高。 3 2 2 层次的方法( h i e r a r c h i c a lm e t h o d ) 层次聚类算法是一种常用的聚类算法。它将数据分层建立簇，最终形成一棵层次树。 凝聚法 分裂法 图3 1 层次方法聚类图 资料来源：作者编制 如图3 1 所示，将按自底向上进行层次分解的聚类方法，称为凝聚( a g g l o m e r a t i v e ) 层次聚类；而按自项向下进行层次分解的聚类方法，称为分裂( d i v i s i v e ) 层次聚类。 凝聚的层次聚类采用自底向上的分层策略，首先将每个对象作为个单独的簇，然后 逐次适当进行簇的合并形成较大的簇，直到所有的对象合并成同一个簇，或者是满足了某 个终止条件。 分裂的层次聚类与之相反，采用的是自顶向下的分层策略，它首先将所有的对象放在 一个簇中，然后逐层分解成较小的簇，直到每个对象自成一簇，或者达到了某个终止条件， 例如达到了某个希望的簇数目，或两个最近的簇之间的距离超过了某个阈值。 由图3 1 可以看出，层次聚类实际上将产生一棵层次树。层次方法的优点在于可以在 不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。但是，单纯的层次 聚类算法的终止条件含糊，而且执行合并或分裂簇的操作不可修正，这很可能导致聚类结 果质量很低。另外，由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以 这种方法的可扩展性较差。因此，通常在解决实际聚类问题时要把层次方法与其它方法结 合起来。层次方法和其它聚类方法的有效结合可以形成多阶段聚类，能够改善聚类质量。 这类方法包括b i r c h 算法，c u r e 算法和r o c k 算法，以及c h a m e l e o n 算法。 b i r c h 算法( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n g ) 是较为常用的层次聚 类。算法的主要思想是：通过逐个读入对象c f 构造c f 特征树，然后采用其它聚类算法对 聚类结果求精。b i r c h 算法的两个核心概念是聚类特征c f ( c l u s t e r i n gf e a t u r e ) 和聚类 特征树c f - 树( c l u s t e r i n gf e a t u r et r e e ) ，c f 一树是存储了层次聚类过程中的聚类特征信 息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量c f ，用 于概括聚类描述。 一个聚类特征向量是一个三元组，用于给出一个簇的信息概述。假设某子簇中含有n 个d 维数据对象 x ；) ( z = 1 ，2 ，n ) ，该子簇的聚类特征向量定义为一个三元组，存储 了该簇的相关统计信息：c f = ( n ，l s ，s s ) 。其中，n 代表簇中对象的个数；l s 代表这 nn n 个对象的线性和，即x ，l s 反映簇的质心位置；s s 代表n 个对象的平方和，即x r 2 ， s s 反映簇的大小( 凝聚程度) 。 b i r c h 算法只存储聚类的聚类特征统计汇总，这些特征提供了了计算聚类和有效利用 存储的所有关键度量，因此可以保证算法的准确度。同存储簇内所有数据对象的信息相比， 这样做大大提高了算法的效率。 聚类特征被存储在c f - 树中，它是一棵高度平衡树，包含两个参数：分支因子b 、l 以及阂值t 。其中，每个非叶子节点最多包含b 个项目，项目的形式如下： c f ，c h i l d ； ( f = 1 ，2 ，b ) ，c h i l d ，是指向第f 个子节点的指针，c f i 是第f 个子节点所代表的子 李雄飞，李军数据挖掘与知识发现【m 】北京：高等教育出版社，2 0 0 3 年：1 0 3 1 6 簇的聚类特征；每个叶子节点最多包含l 个项目，项目的形式如下： c f ： ( f = 1 ，2 ， l ) 。这些叶子节点表示由相应项描述的子簇组合形成的簇。每个叶子节点都有两个指针分 别指向在它左右两边的叶子节点，这些指针将c f 一树中所有的叶子节点连成链，达到高效 扫描的目的。所有叶子节点所表示的簇的半径都必须小于阈值t 的条件，t 表示叶子节点 中子聚类的最大直径或是半径。因为叶子节点中的项是子簇而不是单个数据对象，因此， c f 一树是对聚类数据的简洁表示。c f - 树的规模可以通过调整参数b 和t 来控制，显然，t 值越大c f - 树的规模越小。 b i r c h 算法采用的是多阶段聚类的技术。在对数据集合进行单遍扫描后生成初步