（计算机软件与理论专业论文）基于移动技术的答疑系统研究.pdf

，r |11 l 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究 工作所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人 承担。 学位论文作者签名： 醴刍 日期学位论文作者签名：历7 全汇绉日期： 汐 口弓 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：茏茎鏊刍 日 期：卫丝! ：弓 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名：艺宰堡丕 日 期：丝! ! ! ! 刍 电话： 邮编： 1 j 摘要 随着信息科技在教学过程中的广泛应用，一种基于移动技术的答疑学习系统改变了 传统的学习方式和教育方法。这种采用自主的、探究式的、灵活多样的移动答疑学习方 式让学习者从自己的实际情况出发，自己决定要学习的内容和需要浏览的相关资源，它 突破了以往学校统一化的教学模式，带来的是一种“新鲜的、个性的 学习新主张。但 是要指出的是，在利用智能移动设备进行远程教学时，由于学习者和教育者多数情况下 是不能进行面对面的直接交流的，这样教与学、问与答的学习过程要通过一个桥梁来实 现，这就是移动答疑系统，用这种简单、快速的方式浏览以及问与答的过程，提高学习 的效率。不过像这样的学习系统还尚处于研究和测试的阶段，很多的功能并不完善。设 计上的主要问题集中在忽略了提出问题者提问的语义分析和反馈答案时其有效性较差 的弊端。为了解决答疑系统在答疑过程中遇到的这些问题，本文设计了一个依托初中历 史学科的基于移动技术的答疑系统。该系统根据学习者自身的学习特点和学习过程中产 生的难点以及知识点对可能出现的问题进行了有效的聚类分类，为系统在进行答案抽取 时提供了便利。同时改进了中文语句相似度的匹配算法，对问题采用模式化匹配和无模 式匹配的两种相似度算法来提高问题成功匹配的效率。通过这些方法的改进提升了答案 的查准率和查全率。在文章的最后探讨了移动答疑系统的结构设计，为日后的研究者抛 砖引玉。 关键词：移动学习；智能答疑；文本聚类；语句相似度 a b s t r a c t w i t ht h ee x t e n s i v ea p p l i c a t i o no fi n f o r m a t i o nt e c h n o l o g yi nt e a c h i n gp r o c e s s ，ak i n do f q u e s t i o na n da n s w e rs y s t e mw h i c hi so nt h eb a s i so fm o b i l et e c h n o l o g yc h a n g e sm e t h o d so f t r a d i t i o n a ll e a r n i n ga n dt e a c h i n g t h i si st op r o c e e df r o mr e a l i t yo fl e a r n st h r o u g hu s i n go f m o b i l eq u e s t i o na n da n s w e rm e t h o dw h i c hi si n d e p e n d e n t 、e x p l o r i n gv e r s a t i l ea n df l e x i b l e l e a r n sc a l lm a k ed e c i s i o n sa b o u tl e a r n i n gc o n t e n ta n dr e s o u r c e sb yt h e i ro w n ，w h i c hi sa b r e a k t h r o u g ho fu n i f o r mt e a c h i n gm o d ei n s c h 0 0 1 i ti saf r e s hl e a r n i n gp r o p o s i t i o no f i n d i v i d u a l i t y b u ti tm u s tb ep o i n t e do u tt h a t ，ab r i d g ei sn e e di nt h el e a r n i n gp r o c e s sb e t w e e n t e a c h i n g a n dl e a r n i n g 、a s k i n ga n da n s w e r i n g ，b e c a u s el e a r n sa n dt e a c h e r sc a l ln o t c o m m u n i c a t ef a c et of a c ei nd i s t a n c et e a c h i n gw i t hi n t e l l i g e n tm o b i l ee q u i p m e n t t h eb r i d g e i sam o b i l eq u e s t i o na n da n s w e rs y s t e m ，t h r o u g ht h es i m p l ea n dr a p i dm e t h o d ，t h ep r o c e s so f a s k i n ga n da n s w e r i n gc a nb ea c c o m p l i s h e dw h i c hw i l li m p r o v et h ee f f i c i e n c yo fs t u d y i n g b u t s u c hl e a r n i n gs y s t e mi ss t i l li nt h es t a g eo fr e s e a r c h i n ga n dt e s t i n g , m a n yf u n c t i o n sa g en o t w e l l t h em a i np r o b l e mo fd e s i g ni si g n o r i n gq u e r ys e m a n t i ca n dt h ea n s w e rt ot h ev a l i d i t y w i t hl e s se f f e c t i v e t oa d d r e s st h e s ep r o b l e m sw i t hq u e s t i o na n da n s w e rs y s t e m ，t h ea u t h o r d e s i g n saq u e s t i o na n da n s w e rs y s t e mr e l i e so nj u n i o rh i g hs c h o o lh i s t o r y , w h i c hi sb a s e do n t h em o b i l el e a r n i n gp l a t f o r m t h es y s t e mm a k e sc l u s t e r i n gc l a s s i f i c a t i o ne f f e c t i v e l ya c c o r d i n g t oc h a r a c t e r i s t i c so fl e a r n e r so w nl e a r n i n gp r o c e s s 、d i f f i c u l t i e st h a ta r i s ed u r i n gl e a r n i n ga n d t h ep o t e n t i a lp r o b l e m sw i t hk n o w l e d g ep o i n t s i tp r o v i d e sac o n v e n i e n c ed u r i n ge x t r a c t i o no f a n s w e rw i t ht h es y s t e m ，a n da l s oi m p r o v e st h em a t c h i n ga l g o r i t h mo fc h i n e s es e n t e n c e s i m i l a r i t y w i t ht h eq u e s t i o n s ，a l g o r i t h m so fp a t t e r nm a t c h i n ga n dm o d e l e s sm a t c h i n ga g eb o l h u s e dt oi m p r o v et h ea c c u r a c yo fq u e s t i o nm a t c h i n g t h e r ei sag r e a tp r o m o t i o no fb o t h p r e c i s i o na n dr e c a l lo fa n s w e r sw i t h i nt h e s ei m p r o v e m e n t s a tt h ee n d o ft h ep a p e r , t h e r ei sa p r o b eo ft h es t r u c t u r ed e s i g n e do fm o b i l eq u e s t i o na n da n s w e rs y s t e m ，w h i c hi ss t a r t e da d i s c u s s i o nf o rf u t u r er e s e a r c h e r s k e yw o r d s ：m o b i l el e a r n i n g ；i n t e l l i g e n tq u e s t i o na n da n s w e rs y s t e m ；t e x tc l u s t e r i n g ； s e n t e n c e s i m i l a r i t y ； i i 目录 摘要“一”“”一“” a b s t r a c t 目录一”“一 l 绪论一 1 1 研究背景与现状 1 1 1 答疑系统研究现状 1 1 2 移动学习系统研究现状 1 2 本文主要研究内容 1 3 研究意义 2 理论基础 2 1 文本聚类 2 1 1 文本相似性度量 2 1 2 主要算法 2 2 中文语句相似度算法t o o t t o 9 2 2 1 基于向量空间模型的t f - i d f 方法9 2 2 2 基于语义距离的文本相似度计算方法1 0 3 基于聚类的问题分类研究1 2 3 1 句子聚类方法存在的问题及改进研究1 2 3 2 关键词聚类的问题分类方法1 2 3 2 1 问题聚类步骤1 3 3 2 2 关系型模糊c - m e a n s 聚类算法1 3 3 2 3 聚类算法实际效果分析1 4 3 3 关键词聚类实例分析1 5 4 基于关联词词组的语句相似度算法研究1 7 4 1 设计思想1 7 4 2 基予一定模式的关联词组匹配算法1 7 4 2 1 关键词选取及词组匹配算法的设计1 7 4 2 2 关键词组的形式化化描述1 8 4 2 3 关键词组相似度匹配计算方法1 8 4 3 基于词形的语句相似度算法1 9 5 移动学习答疑系统的总体架构研究与系统实现2 1 5 1 系统总体分析与设计2 1 i l l 5 2 软件开发环境介绍2 2 5 3 移动终端答疑系统的实现2 3 5 3 1 客户端的实现2 3 5 3 2 数据的交互2 4 5 4 结果分析2 5 6 结论”2 6 6 1 全文总结2 6 6 2 今后工作展望2 6 参考文献2 8 致谢”3 0 在学期间公开发表论文及著作情况3 1 东北师范大学硕士学位论文 1 绪论 1 1 研究背景与现状 近年来，无线网络技术的迅猛发展，特别是智能移动终端设备各项功能的日趋完善 和性能的大幅提升为教学者开展全天候的教育与学习提供了可能。因此，依托无限网络 技术和智能移动终端设备作为辅助教学的一种手段已经成为国内外教育界新的研究热 点【。这一热点研究也就催生出了一种新的学习方式就是移动学习。 移动学习技术的出现更加催动了无线网技术和数字学习的相互融合。这种方式可以 使学习者随时随地，就能共享教学资源进行学习活动；同时，教育者和学习者之间也通 过移动学习的这种方法增加了沟通和联系。移动学习的随时性和随地性的优点明显优于 其它的教学手段。经过综合专家的意见，移动学习被定义为：一种全新的可对教与学双 方互交流的数字化学习的学习方式；主要用到的技术手段包括移动计算技术、通讯技术 和嵌入式软件开发等相关技术；实现设备主要有智能手机和具有无线通信模块的p d a ， 主要是考虑是否可以在该设备上安装学习平台；为使用移动学习的用户提供完整的学习 资源和科学的学习方法，强大的搜索能力和方便的互动交流以及绩效评价准确等要求i z j 。 1 1 1 答疑系统研究现状 在一个学习者整个的教学过程中，学习者自主学习的时间占了相当大的比例。为了 很好的完成自主学习的这一过程，建立一个相应的学习系统来完善网络教学的各个环节 就显得急切和必要了【3 l 。而答疑系统之所以成为国内外研究者研究的热点和难点正是因 为它是构建远程教学中的重要环节和最需要智能处理、灵活应对的部分。 其中较为成功的智能答疑系统有美国普林斯顿大学设计的一套用来研究语言学的 词汇参考系统w o r d n e t ，该系统是由心理学专家和语言学专家共同参与研发的，因此系 统在智能化方面有出色的变现、另外还有a s kj e e v e s 公司的a s kj e e v e sf o rk i d s 网上答疑 系统、m l t 人工智能实验室开发的s t a r t 系统1 4 j 等。这些国外设计比较优秀的智能答疑 系统出色的智能性主要体现为： 1 人机理解的自然语言接口和相应的问题查询反馈上【5 1 。例如在w o r d n e t 的设计 中对词语之间的编排是有包含一定语义关系体现。其有别于以往英文字典的设计是，在 w o r d n e t 中的名词，动词，以及形容词和副词在设计上都遵循一个语义概念为其编制了 各自的同义词集合，这些集合酷似神经网络一般由语义链接组成了覆盖词典的语义网。 例如：对水果( f r u i t ) 搜多，输入苹果( a p p l e ) 、香蕉( b a n a n a ) 或者西瓜( w a t e r m e l o n ) 等均可查 到，利用语义的关联查询可以提高查询效率也扩大了查询结果的覆盖面积，还为词与词 之间的语义关系的训练提供了方便。 东北币范大学硕士学位论文 2 系统内容采用了专业领域方式的资源库设计并且对外开放，这样资源得到合理的 编排还扩大了资源搜集的范围，也容纳了更多问题的回答提高了问题的召回率；而且系 统也通过训练的方式不断更新和修改自身的资源库，能在一定程度上把没有收录到资源 库中的问题和答案纳入库中1 6 j 。 国内对答疑的研究这两年也非常的热，主要的突破方向是在专业领域答疑这部分， 但受限于技术和一些硬件方面上的限制，目前多数还采用信息交流的方式进行答疑，但 随着国内答疑技术这个市场需求的提升和答疑技术的快速进步，国内的答疑软件也将步 入一个新的水平。较有代表性的有上海交大研制的a n s w e r w c b s 和校际通网络教学平台 等，不过在答案召回的准确率和对使用者的针对性设计上还是不能完全让人满意的。造 成这些问题的原因川总结起来有以下几方面： 1 智能答疑是通过对问题分析匹配从资料库中自动搜索答案实现的，用户的提问 往往是通过一段文字或者几个关键词进行查询，答疑系统对用户的提问进行全文匹配然 后根据结果把相关性较强的答案抽取出来并按照相似度大小排列后返回给用户。然而基 于中文的自然语言理解是一个难点所以导致答疑系统召回的答案准确率较低，在大量的 召回答案中往往需要用户再次进行判断来选取自己需要的答案，这也就造成答案针对性 较低，不能令人满意的原因。 2 答疑系统在远程教育领域还处于试探性阶段，因此其资源库内容需要一定时间 积累才能丰富起来，组织结构也不那么科学，况且研发机构它们的学习资源库和目前教 学机构多年积攒总结下来的这部分资源是分割开的。 3 制约中文答疑系统智能化的关键问题是中文的信息处理，主要是中文在意思理 解上容易产生歧义和区别于英文的语句相似度匹配还没有很好的解决。 4 目前还没有权威和完整的中文语料库。 5 受限于人工智能和专家系统等现有技术水平的影响也拖累了答疑系统的智能性。 1 1 2 移动学习系统研究现状 移动学习兴起于本世纪初，它作为研究的热点带动了一条新的产业链蓬勃发展起 来，围绕着移动学习这一情景光明的行业各项研究都取得了突破性的进展，并且都得到 了市场很好的认可。那么在深入的研究了移动学习的相关知识后，可以按照研究的目的 作如下分类【8 j ：第一类是移动学习方式的可行性研究，主要研究移动学习技术在学习过 程中所能起到的优势和推动作用以及需要完善的部分；第二类是移动学习这种方式它对 于教育技术这门学的研究是一种推动，这一部分主要由各高等院校以及教育部门在研 究，重点主要集中在运用这项新技术改变以往的教学手段和管理方式；第三类是移动学 习在企业培训和产品开发方面的研究，前身多是对数字化学习进行商业化开发的企业， 他们希望把数字化学习和移动学习相结合，使产品更具综合性，更能迎合市场的需求。 这里列举了是几个有代表性的研究项目。 一、移动学习的可行性研究 2 东北师范大学硕士学位论文 表卜1 - f r o me - l e a r n i n gt om l e a r n i n g 承担者爱立信教育、挪威n k i 远程教育、德国开放大学、 爱尔兰远程教育机构 该项目是利奥纳多达芬奇研究计划的子项目，研究注重选择基于w a p 研究内容技术开发移动学习内容，重点研究移动学习技术的可行性、移动学习 的优势及移动学习课程的设计与开发 研究成果通过研究不同移动终端在移动学习中的应用，初步得出一些结论。 二、移动学习对于教育的推动性研究 表卜2 - “m - l e a r n i n g 承担者英国学习与技能发展处、意大利理论与应用数学研究中心、剑桥培训 与发展部、英国u l t r al a b 及瑞典的l e c a n d oa b 两家数字化学习公司 此项目始于2 0 0 1 年1 0 月，历时三年。该项目提出三个与欧共体各国 的许多年轻成年人有关的社会与教育问题： 读写与计算能力较差 不能接受传统校园的教育与培训 研究内容 因没有掌握一定的信息通信技术所导致知识与信息获取机会的不 平等 研究内容包括： 移动电话技术的应用研究，包括成年用户的需求，态度和使用习 惯的研究等 计算机游戏设计及其特征研究 关于适当的知识呈现方式、学习者模型及标准的研究与开发 研究成果作为研究的阶段性成果，提出了一个系统的系统学习体系框架( 见图 卜1 ) ，这对于我们理解移动学习的多样性，设备的多样性与技术的多 样性提供了一个宽广角度的视野 3 东北师范大学硕士学位论文 图1 - 1 移动学习系统体系架构 三、移动学习在企业培训和产品开发方面的研究 表1 - 3 ：移动教育研究项目 承担者诺基亚、i n s e a d 和i c u s 等 他们选择“移动中的电子商务”这门课程作为教学内容，同时开发基于 研究内容w e b 和w a p 的可能内容，学生可以通过既有w a p 功能的诺基亚和 接入i n t e m e t 的计算机获取课程内容与教学服务。i n s e a d 主要提供 教学内容，i c u s 负责网络课程资源的教学设计及教学组织与实施。 研究成果根据学生学习过程的评价结果揭示：在教学支持方面，两者教过没有 明显差异，而在技术支持方面，w a p 技术比w e b 技术做的更好。 1 2 本文主要研究内容 本文基于移动技术的答疑系统，是依托于理想信息技术研究院的实验室项目。是自 适应学习系统项目的重要组成部分。主要研究的是通过移动通讯技术和手机嵌入式的学 习平台来打造针对初中历史课程的移动答疑系统。这套系统的特点在于可以让使用者随 时随地的进行答疑的全过程。本文计划的答疑过程分为如下步骤：用户登录答疑系统， 在界面以自然语言方式输入问题并提交，再由系统进行内部计算，这是对用户使用的自 然语言理解和消化的过程，其中要用到语句相似度匹配和信息检索等相关技术。常见的 关键词检索如今已经不能很好的满足用户的需求了，为了能更好的符合检索的需要，本 文设计了模式匹配和无模式匹配两种检索机制来满足需要。在移动嵌入式这部分，仿效 网络答疑系统的模式，充分利用智能终端设备的高性能来提高系统的智能性。因此系统 的研究目标定位如下： 1 问题模糊分类方法 4 f 乞 东北师范大学硕士学位论文 智能答疑系统中问题分类的基本思想是：如果给定一个问题，系统能够根据其语义 将其定位在某个范围内，然后在此范围内进行答案的查找，这样可以缩小查找的范围，提 高查找速度。经典的分类算法很多，如简单向量距离分类法、贝叶斯算法以及k n n 算法 等。考虑到它们计算的复杂性及答疑系统自身的特性，系统采用了一种基于聚类的问题 分类方法，该方法通过关键词语义的聚类而达到问题的模糊分类。 2 语句相似性的计算方法 语句相似度计算在文本信息处理领域有着非常重要的地位，也是整个答疑系统的核 心部分。本文提出了一种基于关键词词组的语句相似度计算方法，并对有模式匹配情况 下的语句相似度计算和无模式语句相似度计算进行研究。 1 3 研究意义 我国著名的唐代大文学家韩愈在师说一文中这样说道，“师者，所以传道授业 解惑也”。意思是说“所谓老师，就是传授道理、授与专业知识、解答疑难问题的人。 可见，学生在学习的过程中老师需要起到的作用和职责。而在整个学习的过程中最为重 要的环节是在学生遇到问题时给予及时的解答和帮助，使学生能对问题有正确的理解和 认识，从教育学的角度看这一点也非常重要。答疑系统正是延续和发扬了老师在千百年 来教学过程中解惑的重要作用。而且在答疑系统与移动技术相结合后，更是可以消除传 统答疑系统在使用时间和地域上的局限性。更加方便使用者进行有效学习。移动答疑系 统为学习者全时学习提供了便利。 5 东北师范大学硕士学位论文 2 理论基础 2 1 文本聚类 2 1 1 文本相似性度量 文本挖掘是对海量文本信息处理的一种有效的方法。其中一种重要的方法就用到了 文本聚类的技术。通过文本聚类来对文档进行无指导和快速的分类是它的优势所在。文 本聚类的过程就是对一个文本集进行分化，使其按照内容形成若干个子集也就是通常所 说的簇( c l u s t e r ) 。每个簇的文本之间具有较大的相似性，而簇间的文本具有较小的相似 性【9 l 【姗。通过聚类的方法在检索过程中提高了系统对临近文档检索的查全率。通过近年 来的不断研究发现，文本聚类技术还可以在文本查看、文本归类等方面起到巨大作用。 特别是在问答系统这类用作响应使用者查询和搜索的用到文本分类功能的项目。可以迅 速高效的让文本信息自动分类，并利用这些分类结果方便文本查询。文本聚类的过程主 要有3 个步骤： ( 1 ) 模式描述，主要是对文本信息的特征进行选取； ( 2 ) 设置对要进行聚类数据相适应的领域模型相似程度比较的定义方法； ( 3 ) 进行这种模式的文本聚类。 典型的聚类流程如图2 - 1 ： 图2 - 1 文本聚类过程 通过文本聚类的流程可以看出文本聚类主要牵扯两方面：初始值的选取以及相似性 的定义和聚类算法。当前主流的技术是向量空间模型的文本相似度匹配。而日趋成熟的 方法是基于概念的和语义的聚类算法，以及多种算法相融合的理念。未来的文本聚类可 能会在聚类前先对文本进行分层处理，以达到在不同层使用对其分类最优的聚类算法来 提高和加快文本间相似性度量结果。 2 1 2 主要算法 目前主要的聚类算法有平面划分法、层次聚类法以及时卜研究比较热门的基于概念 的、基于遗传算法的和基于蚁群算法的聚类方法【1 1 1 4 1 。本文主要介绍划分法和层次聚类 6 、 擎j 东北师范大学硕士学位论文 法这两个在各方面技术都比较成熟的聚类算法。并在下文提出了针对问题分类的改进的 聚类算法。 1 平面划分法 平面划分法是在聚类开始前就先确定聚类数k ( k 垒) 然后再对要聚类的数据n 进行 聚类，最终将数据库中需要聚类的数据划分为k 个类，这样划分得到的聚类遵循着事先 设置的划分标准( t t 如两个要聚类文本之间的距离等) 使其最优，这样每个类中含有元素 都是“相似度高的”，而各个聚类间元素是这个“相似度最低”。平面划分法区别于层次聚 类法在于划分法是将数据对象集合水平的分割成设定好的类数，而层次聚类是要先生成 有层次的嵌套类之后再进行划分。划分法中通常使用的是k - m e a n s 和k - m e d o i d s 这两种经 典的聚类算法。 k - m e a n s 算法【1 5 】是：在聚类开始时从参与聚类的数据n 中随机选取k 个数据作为初始 聚类的中心，接下类对剩余的数据对象按定义的规则计算与k 个类中心的相似度，根据 就近原则把数据划分到相似度高的聚类中去；然后再次计算k 个聚类的新平均值。反复 上述过程到标准测度函数收敛结束。标准测度函数一般采用平均误差e ： e ；善k 劲卅 浯t ) n 表示所有数据，m i 是聚类c i 的平均值ic 。i 是聚类c i 中数据元素的数目。即： ”荟毒 ，“f f ( 2 - 2 ) k - m e a n s 聚类算法的处理流程如下： ( 1 ) 从带聚类的数据集d 中任意选取k 个数据作为这k 个类的原始中心； ( 2 ) 循环执行( 3 ) 一( 4 ) 直到每个聚类不再发生变化为止； ( 3 ) 根据数据集中每个数据的d i 值，分别计算剩余数据与各类中心s i 的均值s i m ( d i ，) ； 并根据最小距离重新对相应对象d i 进行划分为s i 为聚类中心的簇c i 中； ( 4 ) 重新确定每个有变化的簇的中心点； k - m e a n s 聚类算法在处理文本聚类时表现的优点为响应时间短、效率高并且弹性较 好。但它也是有明显缺点的：k - m e a n s 算法对于干扰和孤立点数据特别敏感，直接影响中 ，t l , 值的结果；这也是因为这种算法生成的簇的数量k 是事先确定好的，不能在聚类过程中 根据情况自动判别增加或减少簇的个数导致的。 k - m e d o i d s 算法【1 6 j 是针对k - m e a n s 算法的不足之处的改进算法，不同点在于聚类中心 的计算和表示。k - m e d o i d s 算法是规定了聚类中最中心的数据为聚类中心代表这个簇而 区别于k - m e a n s 算法选择靠近中心的数据项代表聚类的中心。这样基本消除了脏数据对 各个类平均值计算的干扰。k - m e d o i d s 处理流程如下： 7 东北师范大学硕士学位论文 ( 1 ) 随机选取k 个对象作为m e d o i d s ( 0 1 ，0 2 ，q 。q ) ； ( 2 ) 循环执行( 3 ) 一( 4 ) 直至u k + m e d o i d s 固定下来； ( 3 ) 剩下对数据对象根据与m e d o i d 最相近的原则分到各个类中去； ( 4 ) 对于每个类( 0 i ) 中，顺序选取一个o f ，计算用o r 代替o i 后的消耗e ( o ，) 。选择 e 最小的那个o ，来代替o i 。这样阶m e d o i d s 就改变了； k - m e d o i d s 算法优点在于对干扰数据不敏感，但是缺点也很明显就是计算量较大， 不合适大量数据。 总体来看用划分法进行文本聚类有聚类效率高和线性复杂度低的一些优点。但是因 为划分法要求在聚类开始前就确定分类的个数( k 个簇) ，这使得该方法对非凸面形状的 簇和差异很大的簇探测不明显，因此这种聚类方法不适用于大量数据信息的聚类。 2 层次聚类法 层次聚类方法是不可逆的聚类，当凝聚式把两组合并后不能通过分裂式再将其分离 到之前的状态。而且层次聚类是需要使用者给出聚类停止的条件和时间的，以求得到最 佳分类的效果。这种层次聚类多用于含有潜在层次结构的数据集。 层次凝聚法在层次聚类中用到最多的方法，其原理是将数据对象按照使用者定义的 距离逐步进行文本聚类到分类数和数据深度满足使用者的需求终止聚类。其过程可以归 纳为：最初的是n 个单成员的类，最后的划分是一个包含全部个体的单个类。凝聚式聚 类有很多方法如b i r c h 算法、c u r e 算法等等，但基本的原理是相似的，整个聚类过 程的每一步骤，是将距离最近的簇或者数据元素融合成一个新的簇。方法间的差异只是 距离计算方法的不同。 凝聚式层次聚类的过程1 1 7 1 如下： ( 1 ) 将数据集d = 仁。，d ：，d 。 中的每个文档d t 作为单个簇q 一仁- ，这些类构成了 d 的一个聚类c = c 。，c ：， ； ( 2 ) 循环执行( 3 ) 一( 4 ) ，直到数据集中只有c 簇或达到终止条件； ( 3 ) 计算c 中每对簇( c i ，c ! i ) 之间的距离s 拥( q ，c ，) ； ( 4 ) 选取具有最小距离的簇m a x s i m ( c ；，c ，) ，把q 和q 重新聚合为一个新的簇c k = qu q ，并形成t o 的一个新的聚类c 一 c 1 ，c ：，q 一。 ； 层次聚类法的优点很多：首先适用性广泛可以用于任意形状的簇并且任意数据间的 相似度是自行定义的；其次是对数据聚类过程中簇的粒度是可控制的。然而层次聚类法 也存在着聚类构建的结果不可逆；聚类终止条件不智能，需要人为设置；计算量巨大， 运行速度慢等不完美之处。 8 秘， p 、 一 东北师范大学硕士学位论文 2 2 中文语句t i t 0 , 度算法 本节主要介绍中文文本相似度计算方法，分析了现行的相似度算法的优缺点。 2 2 1 基于向量空间模型的t f i d f 方法 向量空间模型旧( v e c t o rs p a c em o d e l ，v s m ) 是一个使用较多且效果较好的应用于信 息过滤，信息撷取以及评估相关性的代数模型。s m a r t 是首个使用这个模型的信息检 索系统。在v s m 中，文档被看作是由相互独立的词条组仍，t 29 t o t 9 ) 构成，对于每一词 条t i ，根据其在文档中的重要程度赋以一定的权值w i ，并将互，t 2 ，l 看成一个n 维坐 标系中的坐标轴，w 1 ，w 2 ，w a 为对应的坐标值。这样由佤，乏，瓦) 分解而得的正交词 条矢量组就构成了一个文档向量空间，文档则映射成为空间中的一个点。对于所有文档 和用户查询都可映射到此文本向量空间，用词条矢量瓴，疋，l ，睨) 来表示，从 而将文档信息的匹配问题转化为向量空间中的矢量匹配问题。假设用户查询为q ，被检 索文档为d ，两者的相似程度可用向量之间的夹角来度量，夹角越小，说明相似度越高。 t f - i d f 1 8 1 是一种广泛用于资讯探勘和资讯检索的加权技术。多是基于向量空间模型 的常用于检测文本相似度的一种算法。t f - i d f 采用统计的知识来评估字词对于一个文 本集中一份文本的重要程度，字词的重要性随著它在文件中出现的次数成正比增加。因 此每个字词在文本集中的出现的频率为( t f ) 和单字词对文本集中每个文本的分辨力为 ( i d f ) 。这里设数据集中所有出现的词为w 1 ，w 2 ，w n ，那么每个文本都可以用一个n 维 向量t 一佤，t 2 ，瓦) 表示。其中，t i ( 峰匀) 的表达式为：l n l o g ( m m ) 。设n 为w i 在 这个数据中出现的数量，m 是在数据集中含有w i 的数据数量，m 表示文本集还有的文 本数目。分析表达式可知，t 值并不单纯由变量n 的值所决定，也就是说一个t f 值很 高的词还要看它的i d f 值( 1 0 9 ( m m ) ) 的表现。例如：中文里“是”这个字，它的出现频率 很高，也就是说“是”字的t f 值很大。可是在文本集中“是”这个字仍然是个高频词语， 这就影响了它对于帮助辨别文本的能力，这样i d f 值受此影响也会很小。所以t f i d f 是一种综合考虑词频和字词判别力的优秀算法。同理可得文本a t 的1 1 维向量 t = 仃，t ，t 。) 。文本a 和文本a t 的文本相似度就用t 和t - 这两个向量之间夹角的 余弦值来表示。文本相似度的成用算法还有内积法、d i c e 系数法、j a c c a r d 系数法和余 弦系数法等。 设文本a 和文本a 的n 维向量是t 和t 。上述方法计算相似度的公式： 内积法 9 东北师范大学硕士学位论文 d i c e 系数法 j a c c a r d 系数法 余弦系数法 s i m ( t , t 1 ) 一耋醐1 跏；筌婴 善互2 + 善1 1 2 眦n 。：娶三 善互2 + 善互1 一善l 1 1 s i m ( t ，t 1 ) 一 ( 2 - 3 ) ( 2 - 4 ) ( 2 - 5 ) ( 2 - 6 ) 基于向量空间的t f i d f 算法其不足之处表现为：该算法是基于统计的方法，适用于 包含词条数目较多的大粒度文本。算法需要被测文本中包含大量词语，只有当数据中所 包含的词语数量足够多时相关词才会多次出现，才能发挥正常的效果。 2 2 2 基于语义距离的文本相似度计算方法 计算中文语句相似度是答疑系统关键的问题【1 9 1 2 0 1 ，为了解决这个问题研究者们提 出了基于字面数据的和以词素处理的相似度测定1 2 1 】基于语义分类体系的相似度计算等 1 2 2 其中文献主要采用董振东和董强先生创建的知网 2 3 1 为基础的词汇相似度计算是一 个较有前景的发展方向【驯。计算句子语义的相似度主要通过对句子中词语相似度计算， 通过句中的这些词之间相似度的比较来判定语句之间相似的程度。词语之间的相似度需 要计算他们之间的语义距离来确定。有学者把语义距离定义为两个词对应的义原在义原 树中的最短距离。知网中存在e n t i t y 、e v e n t 等1 0 棵义原树，哈工大的研究者们通过 对知网义原树的改进使义原存在了父子关系的表示，并且把词与词之间的这种上下 位的关系特征表示了出来。 可以通过对词语计算它们之间的语义距离来计算两个句间相似程度。设待测语句a 句中有m 个词，b 句中有n 个词。两个语句间的相似度用s ( a ，b i ) 表示a ( 1 i 三m ) 和b j ( 1 j 9 ) 。 这样就得到一个m * n 的矩阵，公式2 7 ： 1 0 妒 i r j 东北师范大学硕士学位论文 m 似，曰) = s ，b )s ，b 2 ) 。s 似，色) s ，b 1 )s ，b 2 ) 一j ，反) 通过矩阵可由公式2 8 得到语句ab 之间的语义相似度s i m ( a ，b ) ： s i m ( a ，曰) =善m a x g b ) ，s ，易) ，e ) ) ( 2 - 7 ) ( 2 - 8 ) 基于语义距离的这种语句相似度计算方法在智能化方面有所提高，不过它忽略了词 语在语句中是有权重的这一特征，也就是在计算语句相似时可能因为忽略了某个词在语 句中的权重造成理解上的偏差，另外因为中文语法的复杂性对提取文本特征信息增加了 难度，所以对于语义的这种语句相似度的计算还需要不断的研究和完善。 东北师范大学硕士学位论文 3 基于聚类的问题分类研究 3 1 句子聚类方法存在的问题及改进研究 把问题作为聚类的对象是采用聚类算法对问题分类的通常方法。本文设想了一种通 过对语句提炼代表关键词来代替原语句进行文本聚类的问题解决方法。 1 问题可能由一个或者几个语句组成，而对问题的理解往往需要先从对语句提取特 征项开始。我们知道一个句子的特征项是由它的关键词的意思组合表示出来的。也就是 说如果直接对一个语句进行聚类的话是要考虑在一个句子中出现多个关键词的情况的， 这样就增加了聚类过程的难度甚至会涉及多维聚类甚至高维聚类【2 5 1 。为了避免这种情况 本文选择了直接对关键词进行聚类的方法，这样只需考虑对关键词之间的语义联系用它 们之间的关系矩阵便可完成文本的聚类过程。 2 用户使用答疑系统提问的内容多为自然语言的中文文本信息，这在以结构复杂 著称的中文语句的理解上是一个难题。经过作者对国内外文献的研究发现，关键词在语 句结构中是稳定的，这种以关键词作为聚类目标的方法可以很好的降低聚类频率。同时， 对初中历史课程的研究也表明，历史这门课程的结构可以按照时间主线来进行划分；对 其考试大纲和问题库的分析可得到这样的结论就是大多数的考试内容都包含代表关键 词或可以通过关键词组进行表示。 在实际的设计中一个类和它的相近类不能界定的那么清晰，模糊概念与文本分类算 法相结合的方法在实际的使用中有着非常良好的效果，不但提高了算法的准确度，还可 以把知识间的这种联系清晰的表示出来。 3 2 关键词聚类的问题分类方法 一个高效的答疑系统通常会对问题库分类来提高系统的工作效率。作者深入研究了 问题库分类技术，本文运用模糊分类的概念与文本聚类相结合的方法。方法的关键是对 中文语句中关键词的利用，关键词在语句中是相对稳定的，又可以避免频繁分类，从而 避免了对问题直接聚类可能引起的复杂的高维聚类。在以关键词作为对象的文本聚类方 法中本文选择了f c m 算法予以实现。f c m 算法的主旨思想是在文本划分时将数据元素间 相似度最大的划为一个簇，而不同簇间的相似度最小。f m c 算法是对c 均值算法的改进， 它完善了c 均值算法对数据的划分过于硬性使分类标准过于苛刻，影响了分类成功的机 率的弊端。f m c 算法则很好的利用了模糊概念的优势将分类过程改成了一种柔性的模糊 划分。不过这种算法直接受到关键词之间的语义关系质量的影响。因此不断地完善关键 词的语义关系也是十分必要的工作。 1 2 东北师范大学硕士学位论文 3 2 1 问题聚类步骤 首先，关键词聚类方法是要找出这一类别中所有关键词和关键词之间矩阵r 1 2 6 1 的关 系。设有刀个关键词用慨，疋 表示，这样便形成了一个万万的矩阵凡那么在这个集合 中两个关键词x 和y 的相似度表示为尺。 设聚类个数为c ，主要分为3 步聚类： ( 1 ) 由关系矩阵尺，通过模糊聚类算法得到结果是cx n 的矩阵u ： u 尺 ( 2 ) 设问题a 中有m 个关键词( k ，k 。) ，其权重分别为( q 级) 。 对问题a 进行模糊分类：k 对于c 个类的隶属度向量为妙m u 。：，【厂k ，用u 。表示。 同理，如对于c 个类的隶属度向量用u 。表示。则