基于概念语义分析的文本聚类研究

《基于概念语义分析的文本聚类研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

东北师范大学硕士学位论文不同类别间的事物相似度尽量小哺。聚类作为一种非监督型的知识发现方法，不需要任何事先的训练数据，而仅仅按照相似度原则，将一组数据划分为事先未知的分类状态，因而是一种有效的，得到广泛应用的模式识别与知识发现的方法。在文本聚类中，短文档聚类存在高维稀疏性问题，导致了文档的查全率低下，本文基于这一问题在知网结构下进行概念语义分析，提出节点关键词映射知网关键词的匹配法，来解决高维稀疏性问题。文本聚类的方法大致可分为层次凝聚法和平面划分法两种类型盯’83传统的基于文本关键字的向量空间模型(VSM)，用m个关键字构成的文档向量Dj={dli，d2j，⋯，“i)表示文档集中的一个文档，这种方法存在一定的问题。表现在向量空间应用矢量内积计算文本向量空间的相似度，把词语看成了独立的元素，词语之间没有联系，不能明确表达文本语义内容。其次，语义的向量空间模型只是对文本中存在的词语进行匹配，忽略词语中的一词多义以及一个文本语义的多种表示方法。知网(HowNet)是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库，知网是面向计算机的双语常识知识库。目前，词条集合并不能完全准确地反映文本的语义，可以通过改变文本聚类的途径来对文本的语义进行聚类。文本通过知网的内容来构建概念语义树，消除一词多义和一义多词及一个文本语义的内容可以有多种表达方式等问题的歧义性，将语义相近的文档实现基于内容的聚集。文本通过知网的内容来构建概念语义树，进行概念语义分析，消除一词多义、一义多词及一个文本语义内容可以有多种表达方式等问题的歧义性，并通过细粒度计算来解决稀疏性问题，提高查全率，从而将语义相近的文档实现基于内容的聚类本文。本文的结构如下：第一章，绪论主要介绍了研究背景及意义、文本聚类概念及本文的研究目标及主要工作；第二介绍了文本聚类的主要因素；第三章：语义树及语义的相关度问题；第四章：介绍概念离线语义树和动态语义树的构建、查询及公式；第五章：实验部分，给出了实验结果以及实验分析，并对该工作进行总结，并提出了进一步研究设想，从而为后续研究提供了基本思路。2 东北师范大学硕士学位论文1．1研究背景及意义第一章绪论21世纪，计算机技术和网络通信技术正在推动人类各方面的进步，互联网已经成为人们不可缺少的信息来源。目前，网络资源数据增长速度飞快，人们要获取所需的信息要花费很多时间，所以，如何快速准确获取信息成为焦点。传统的信息搜索技术存在着这局限性，已经不能适应目前增加的大量文本数据处理，文本挖掘(TextMining)成了数据挖掘的一个很有前途的研究方向。文本处理的特殊性，不能像数据库中的数据，文本处理需要有自然语言理解的支持，目前机器对自然语言理解还存在很多歧义问题，因此文本挖掘还不能很好的表达理解的层次。文本数据挖掘中的概念与方法有很多是直接来源于传统的数据挖掘技术。数据挖掘技术是一种从大量数据中提取其潜在信息的方法论。聚类分析是文本挖掘的主要手段之一，他的主要作用是：1)通过对检索结果的聚类，将检索到的大量网页以一定的类别提供给用户，使用户能快速定位查找的目标；2)自动生成分类目录；3)通过相似网页的归并便于分析网页的共性。其中的一个重要的应用方面就是聚类。对于文本数据来说，聚类就是尝试将不同的文档按照其内在的信息进行归类，使得聚类之后的各类文档，在同一个类中文档具有最大的相似性，而处于不同的类中的文档具有最大的差异性n川。从数学角度来看，文本聚类是一个映射的过程，它将未标明类别的文本映射到根据文本内容自发形成的类别当中，该映射可以是一对一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。用数学公式(卜1)表示如下：厂：彳一B；(卜1)其中，么为等待聚类的文本集合，B为聚类系统中的类别集合；文本聚类作为基础研究，对已有网络信息资源的组织和检索起到很大作用。过去都是通过人工完成文档分类，费时费力。利用计算机进行文本分类是一种有效的方法。综上所述，文本聚类随着网络快速发展而得到重视和发展，文本聚类技术将成为人工智能领域一个重要的研究课题。目前，国内很多学者对中文文本分类进行了深入研究，如黄萱箐H5。等提出一种基于机器学习的、独立于语种的文本分类模型。周水庚H明等在论述隐含语义索引的理论基础，研究了隐含语义索引在中文文本处理中的应用。李荣陆H铂等使用最大熵模型对中文文本分类进行研究。张剑H副等提出一种以wbrdNet语言本体库为基础，建立文本的概念向量空间模型作为文本特征向量的特征提取方法。对于中文文本分类的研究已经做了很多工作，中文与英文存在本质上的不同，中文存在多义词、同义词等等复杂情况，但是对 东北师范大学硕士学位论文于多义词、同义词等问题也是可以解决的，本文提出了一种方法来解决了这个难题。1．2聚类分析1．2．1聚类的概念聚类(Clustering)就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类或簇(Cluster)的过程。聚类所生成的类是对象的集合，这些对象与同一个类中的对象彼此相似，与其它类中的对象相异。聚类的严格数学描述如下旧3被研究的样本集为E，类C定义为E的一个非空子集，即CcE且C≠西聚类就是满足下列两个条件的类c1，C：，⋯，Cr的集合1．C1uC：u⋯uG=E2．C，r、C，=咖(对任意f≠．，)由第一个条件可知，样本集E中的每个样本必定属于某个类；第二个条件可知，样本集E中的每个样本最多只属于一个类。定义1阳∞给定由一些元组组成的数据库D=“，f：，⋯乙)和整数值尼，则聚类问题就是定义一个映射厂：D一{1，⋯，七)，其中第i个元组I被映射到第j个簇K，中去。第j个簇K，由所有被映射到该簇中的元组组成，即K，={‘l厂(I)=K，，1≤，≤七，f，∈D)。定义2哺01给定由一些元组组成的数据库D=％乞，⋯，。)以及两个元组f，，t∈D之间的相似性度量s砌(r，，f，)和整数值K，则聚类问题就是定义一个映射厂：Dj{1，⋯，Jj})，其中第，个元组，，被映射到第j个簇K，中去，1≤，≤忌。给定簇K，对于V7，1，f，，∈后，和t仨七，。有sf聊(‘，1，f，。)>sf所(‘『1，I)。聚类分析也称群分析、点群分析，它是研究分类问题的一种多元统计方法H9。j引。它和判别分析都属于分类方法，判别分析属于“训练学习”分类，而聚类分析属于“自我学习’’的分类。聚类分析根据分类对象不同分为Q型聚类和R型聚类’4旷533：Q型聚类是指对样本进行聚类，可以用来预测，样本分布划分等；R型聚类是指对变量进行聚类(分类处理)，用于变量的选择。1．2．2聚类的应用领域如上所述，聚类分析是数理统计中研究“物以类聚”的一种方法，它是多元分析的一个分支，目前已被用于信息检索∞1’62|、模式识别哺3’64|、机器学习阳5’蚓、图像处理¨铂等研究领域。在各种领域，可以从时间上聚类，也可以从地域上聚类，还可以从其他因素上进行聚类。聚类分析根据样本的属性和特征等方法来定样本间的关系，按自然程度，客观程度进行聚类，从而得到合理结果。4 东北师范大学硕士学位论文1．3文本聚类1．3．1文本聚类研究背景文本聚类的映射规则是系统根据已经掌握的每个文本若干数据信息，计算出文本之间的近似程度，再根据文本与各个自动聚集形成的类别之间的相似程度，逐渐将每个文本和各个类别联系起来。具体而言，通常的认识是将不同的文档按照各自的主题进行聚类，聚类之后的文档在同一个类中具有相同或近似的主题，不同的类则代表不同的主题。文本聚类技术在对大规模文本集的组织、浏览、文本集的层次归类的自动生成等方面有非常重要的应用，诸如通过对检索文档聚类，为用户呈现有组织的和可理解的结果；在文档集中聚类文档(电子图书馆)；自动的(或半自动的)创建文档类别目录(yahoo)；以及通过在相关的子集(聚类)而不是在整个文档集中检索文档，以获得高效的信息检索。文本聚类的方法包括了决策树n2—3|、统计方法n4’1引、神经网络n61、启发式逻辑n71以及基于规则的系统¨鲫等其他方法。这些方法分别来自不同的研究领域，包括数据库(DB)、信息检索(IR)、人工智能(AI)中的机器学习(ML)与自然语言处理州LP)n引。对于任意一种聚类技术来说，都包含了以下四个方面的概念：·一种数据的表示模型●一种相似度测量方法●一种聚类模型·一种采用上述数据模型以及相似度测量方法建立聚类的聚类算法目前，文本聚类领域的研究主要集中在以下几个方面：(1)对大规模文本集进行有效数学模型化的问题，主要与语言文字的特性相关；(2)在无指导的情况下确定文本集中文本主题数目的问题，也就是说如何确定聚类之后所形成的累的数目；(3)在算法的时间复杂度和准确度上做平衡的问题。根据对文本数据建立表示模型方式以及相似度测量方式的不同，可以将现有的文本聚类方法分成两类：不考虑文本语序(基于单词)进行建模和计算相似度的聚类方法和考虑文本语序(基于短语)进行建模和计算相似度的聚类方法。1．3．2概述及分类将文本进行归类的方法有两种：文本聚类和文本分类。文本分类是一个有指导的学习过程。一个已经被人工标注的训练文本集合，寻找文本属性和文本类别之间的关系关系模型(称为分类规则)，然后用学习得到的关系模型对新文本进行自动的类别判断。所以说文本分类一般分为训练和分类两个阶段。 东北师范大学硕士学位论文图1．1文本分类——学习阶段图1．2文本分类——分类阶段文本聚类与分类的不同之处在于，文本聚类是一个无人指导的学习过程，没有预先定义好的主题类别，在每一个类中，文本间具有尽可能大的相似性，而不同类之间，具有最大的非相似性。也就是说，文本分类需要人工给予计算机一段时间，等其掌握了学习规则后在自学；而文本聚类不需要人工给时间，计算机能通过观察来学习。文本聚类的步骤：图1．3文本聚类步骤1．3．3文本聚类的定义定义1．1：文本聚类(TextcluStering)是对一个给定的文本集合D={吐，吃，⋯，吨)进行划分，从而得到一个类的集合C={cl，c2，⋯吒)，其中c，cD(／=1，2，⋯尼)，使得对V谚(谚∈D)，j巳(巳∈C)且巧∈c，，同时使得代价函数厂(c)达到最小。文本聚类的一般过程可以用图1．1表示：文档图1．4文本聚类的流程1．3．4文本聚类的算法分类通过定义1．1，对一个文本对象矿，并没有规定其归属的类的数目，一个文本对象可以仅仅属于一个类，也可以属于多个类。这样就可以把聚类算法划分为两类“1l：分别为硬聚类和软聚类。6 东北师范大学硕士学位论文目前聚类算法可以分为以下几类：1．划分法划分算法H2：给定一个有N个元组或者记录的数据集，构造K个分组，每一个分组代表一个聚类(KD，则取d(B，p，)=D。注：d(p，，p，)=maxld(p1，p2)，d(p2，p1)】(3—5)概念是根据多个义原组成的义原项来解释，每个概念主要分为4部分义原，它们按从主到次的顺序对概念进行描述。在义原的体系结构中，每个义原与其它树中的义原也会存在一定关系，因此义原体系结构增加了横向联系，这样就存在义原的横向关联扩展。综上所述分析，对各项因素加权平均即可得出词相关度，记为R，公式b43为：R(w】，w2)=maxl叩。窆卢，lnq(s，是)+叩：I1一坐妥型l+r7，E(s，曼)(3删Li：lJj=lL“J式中771+叩2+，73=1；女口773为O时，77】+叼2=l。3．4本章小结本章介绍了语义树及语义相关度，语义树为二叉树，在本章开始对二叉树进行了简单的介绍，语义树的主要特点是“即用即造”可以离线构建也可以在动态构建。语义相关度是一个模糊的概念，没有明确的客观标准可以衡量。语义相关度与语义相似度是两个不同的概念，但两者之间有着密切的联系，语义相关度是由义原的相似度与关联度所决定。通过“知网”了解了概念，概念由多个义原所组成的义原项来加以解释，每个概念主要分为4部分义原，在对概念与词进行比较的时候主要就是对这4部分义原进行比较，来实现文档的比对。 东北师范大学硕士学位论文第四章概念语义树及公式本文提出了概念语义树的构建及相似度公式(4—1)，在词的向量空间模型里存在“关键词障碍”的问题，在自然语言文本中广泛存在一词多义，一义多词以及一个文本语义的内容可以有多种表达方式等问题。这样使得基于词语向量空间模型的查询和文本的语义匹配性不能达到最佳。本文应用了语义树，在文中将构建一个概念语义树来解决语义匹配的问题，实现基于语义的查询。语义树口。是按照某种规则在有向二叉树的每个结点上都标记有一个合式公式而构成。4．1构造概念语义树语义树模型的构造有离线构造语义树Hj和动态构造语义树。4．1．1离线构造语义树设RSim(p，q)为概念p与词q之间的相似度值，对任意给定的概念p，采用树状的模型来表达概念p与所有其它概念的关系，如图1所示。Pq1qmqAqlqmqlqiqmBC图4．1离线语义树在图4．1中，以概念p为根结点，词q为叶结点，两者之间的路径权值是概念与词的相似度。从q，到q，的所有词都是按照词与概念p之间的相似度来排序的，与p相似度越高的词在最左边，以满足下式：R&m(p，91)≥R所聊(p，92)≥⋯⋯≥R·研聊(p，g，)≥⋯⋯≥R·辩聊(p，g。)在图4．1三棵树中，确定相似度的方法。首先，保留了从左起到m个词，其余的词丢弃；其次从级到g。的相似度区间为(1～O．4)，对保留的m个词进行在次划分，具体分为g。到gf，研到％，定义91到g，的相似度区间为(1～O．6)，g，到吼的相似度区间为(0．6～O．4)。本文是将B树进行在次划分，这样可以更进一步的对语义度进行比较， 东北师范大学硕士学位论文提高文本与文本集的聚类效果。构造离线语义树的算法如下。在文档集D中，P为概念向量空间{p1，p2，．．．，pn)buildPST(T)输入：查询文档q，q为词向量空间{ql，q2，．．．q。)输出：buildPST(T7)if1≤sim(p，qm)≤0．4then；retumqm；elseremoVe(T，qm)；ifsim(p，qi)≥sn(p，qm)≥0．4；0．4≤sim0，qi)usim0，qm)≤1；if0．6一一学校一大学二师范大学一计算机学院网络<／curriculum><／coIIege><／name><／node><／rOOt>24 东北师范大学硕士学位论文[高校，大学，政府，银行，公司⋯⋯】【大专，高职，高校，中专，大学⋯⋯】【东北师范大学，北京师范大学，华东师范大学，长春师范学院，师范学校⋯⋯】【计算机系，计算机，计算机科学，计算机公司，历史学院⋯⋯】<二!至薹茎三二卜r网络理论，网络技术，通信技术，网络安全，网络通信⋯⋯，图5．1输入xml文档5．3实验结果本文应用相关度与相似度相结合的方法从横向与纵向两个方面进行比较求得概念相似度。图5．1中给出xml文档树的相对应的概念语义向量，并以college一计算机学院为例进行比较。college一计算机学院：匹配度公式计算机学院—j：L一计算机系，所得的相似度为0．72匹配度公式计算机学院——上一计算机，相似度为O．392在构建语义树时，本文对相似度进行了进一步的划分，当相似度<0．3时将删除，相似度≥0．3时再次求其相似度，相似度≥0．6时直接进行下一级的比较。通过上面例子看出，在比较时计算机系会直接返回。给定实验参数B，a求得相似度的值如表一。本文算法是基于概念的相似度进行比对，图5．3可以看出本文的算法可以比较准确给出概念与词之间关系，通过上图可以看出第一义原的大小觉得这词之间相似度的关系。当卢120．48卢720．25卢320．2卢4。o．07d=1．6时实验结果如下：25 东北师范大学硕士学位论文表一：R(p，g)20．4时实验结果比对图节点关键词知网匹配关键词匹配度(O．4)撒～二高中O．43136大学0．648768大学。学校0．6968．”3蕊≤大专0．152＼高校0．688、职业学校0．2184东北师范大学O．66912北京师范大学0．71504华东师范大学0．6688师范学院0．83776白城师范学院O．45296吉林师范大学O．67936长春师范学院O．4164计算机系0．72计算机0．392计算机科学O．60416计算机学报O．332网络技术0．828网络理论0．8624网络教程O．8664通信技术0．408＼网络安全0．7976一网络通信0．797626 东北师范大学硕士学位论文表二：R(p，g)20．55时实验结果比对图节点关键词知网匹配关键词匹配度(O．55)计算机学院-计算机系0．57师范大学-师范学院0．65992陷＼≤网络技术0．651网络理论0．6758网络教程O．6813图5．2MM=O．55时的结果图27 东北师范大学硕士学位论文图5．3MM=0．4时的结果图图5．2的实验数据对比，说明本文的方法取得了较好的效果，当第一义原越大相似度也就越大，本文的方法所得出来的比较数值比较平缓，本实验中所得各个概念之间的相似度为得到的结果为上图。还是以该文档为例，在实验中个概念之间当相似度为0．4时，所得的文档相似度为0．7，表三给出了相对应的参数值。实验二：输入文档一一削一苹果一面包一巧克力28 东北师范大学硕士学位论文吃<／eat><／f00d><／bread><／fruit><／fUnCtiOn>切，砍，苹果，刀，皮⋯⋯】【刀，皮，橘子，苹果，牛奶⋯⋯]蛋糕，苹果，巧克力，报纸，饼干⋯⋯][糖，饮料，水果糖，白糖⋯⋯]面包，报纸，蛋糕，饮料，刀⋯⋯]图5．4输入姗l文档当卢1=o．32卢2=o．3卢3=o．25卢420．17a=1．6时实验结果如下：表三．实验结果比对29 东北师范大学硕士学位论文图5．5MM=0．4时的结果图由表中数据可以看出，文献6相似度算法得出的相似度的粒度大相似度较低，如“面包”和“报纸”的相似度比“面包”和“苹果”的要高；在相关度算法得出的相关度比相似度有改善，但“面包”和“巧克力”的相关度完全一样。在本文提出算法中得出的结果粒度小相似度高。实验三：输入文档-一宾馆一吉林省宾馆一人民大街<／street><／nOde><／head>30 东北师范大学硕士学位论文饭店，宾馆，大酒店⋯⋯]山宾馆，时尚宾馆，吉林省宾馆，⋯⋯】咱由大路，人民大街，新民大街，南湖大路⋯⋯】图5．6输入xml文档当p1=o．4卢2=o．25卢3=o．2卢420．15a=1．6时实验结果如下：图5．7删_0．4时的结果图 东北师范大学硕士学位论文图5．8MM=0．6时的结果图实验三构建了简单的xml文档，在进行比较时，概念间的相似度的取值仍然是0．4和0．6两个值，当相似度取值为0．4时，所得的相似度为O．8；当取值为0．6是，所得的结果为0．7。实验二说明了，当相似度取值小是，所得的文档相似度会大，但是检索到的内容可能不会很理想，当相似度取值比较大，所得的结果反而比较好。实验四：不相似文档本实验还做了不相似文本的比较，还是以上个xml文档为例子，但是数据库中的文档有所改变，但是数据集中还是包括Xml文档中的概念词，在实验中，xml文档中的各个概念跟数据库中的概念进行比较，每个单独的概念都找到了相似的数据，但是整个档比较时就没有发现相似文档。32 东北师范大学硕士学位论文5．4实验分析图5．9不相似文档实验结果本文通过对两个相似文档和一个不相似文档进行了实验并加以分析，实验中分别对两个相似文档在相似度为0．4和O．6两种情况下得到的数据进行如下分析。1．当相似度为0．4是，概念向量与每个词向量间的相似度很大，而且很接近，所得的整体文档的相似度也相对比较大，这样对文本聚类的效果不是很明显。2．当相似度为O．6时，概念向量与每个词向量间的相似度会相应减小，所得的文档相似度也会相应减小，这样对文档聚类会相对好一些。3．当对不相似文档进行比较是，概念向量与每个词向量之间还是存在一定的相似度，但是当对整体进行比较时，所得的结果为NOSIMVALUE(如图5．11) 东北师范大学硕士学位论文总结与发展随着Internet的快速发展，信息处理已成为人们获取信息不可缺的工具，从而，文本聚类成为信息处理的热门，文本聚类是一种无人指导的学习过程，没有预设主题类，通过“自我观察”进行学习。文本以xml文档为对象，研究如何将文本聚类应用于文档分类当中，包括以下几个方面：1．给出了本文的研究背景及意思；聚类分析及文本聚类概述及方法，主要介绍了文本聚类的发展，定义及其算法；说明了本文的研究目地及主要的研究内容，并对整体文章的结构加以概述。2．介绍目前常用的几种文本模型及语义网络的概述；主要以传统的vsm模型为例，这种方法把词语看成独立的元素，词语间没有联系，不能明确表达文本语义；语义网络：它作为一种知识表示方法，本文介绍了知网，Wordnet，HDC。3．语义树：语义树本身是“即用即造”可以动态灵活的构造，本文将语义树与知网相结合从而构造概念语义树来对文本进行聚类。语义相关度：相关度与相似度为两个概念，但是两者之间关系密切，当词语的相似度高，相关度也高；但是相关度高，相似度不一定高。4．本文通过语义树自身特点与知网中的概念相结合构建了概念语义树，本文还根据语义相关度和相似度的公式给出了自己的公式(4—1)，并加以证明，给出了匹配度公式(4—2)。5．实验：通过实验证明了本文给出的公式及其想法的有效性；在实验中分别对相似文档和不相似文档分别做了实验，在相似文档中当概念间相似度值有改变时文档间的概念相似度及整体文档的相似度都有相应的变化。本章还给出了目前实验完成的情况，而且还存在很多不足的地方，在日后的工作中要进行下一步的完善。本文通过CSTM(概念语义树)来进行节点关键词与知网匹配关键词进行比较，其思想是通过知网中义原的特点来更好的得到词向量与概念向量的相似度，进行文本与文本集间的聚类。与传统的聚类比较这种方法可以很好的对词进行解释，解决同义词和多义词问题。并通过语义相关度的方法从纵向关系和横向关系解决结构性歧义问题，提高聚类的效果。以前文本聚类很多只考虑了语义的相似度从而忽略了相关度重要性，本文将语义相关度与相似度相结合算出语义匹配度(MatchingMeasurement)，通过细粒度计算来解决文档中存在的稀疏性问题，从而提高文档的查全率，得到更好的聚类的效果。下一步工作是进一步完善本文参数的自适应配置，以实现文档的语义聚类。34