维吾尔文网页聚类算法的设计与实现

《维吾尔文网页聚类算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维吾尔文网页聚类算法的设计与实现★买买提依明·哈斯木．维尼拉·木沙江(新疆大学信息科学与工程学院，乌鲁木齐830046)摘要：将传统的数据挖掘领域中的聚类技术引入网络信息搜索中(Web聚类技术)，以解决搜索引擎结果集不便于用户浏览问题为目的。分析维吾尔语的词法特点，选择适合维吾尔文文本聚类的特征，构造可扩展后缀树，选择基类，合并基类，把维吾尔文网页按相似度分成不同的类并形成类标签。关键词：聚类；后缀树；STC；STCI0引言一篇介绍关于部队生活的电视剧文章．就既可以属于娱乐类文章。也可以属于军事类文

2、章。这在实际的使用当用户从搜索引擎获得所需要的网页后．面对海中是会经常遇到的情况。鉴于此．由OrenZamir和量的网页．往往不能很快地获取所需的信息．所以如何OrenEtzioni提出的后缀树聚类(SumXTreeClustering)使用户从搜索结果中快速准确地找到自己所需的信息就成为非常符合实际需要的自动聚类方法。该方法的就是需要解决的问题。从实际使用中可以发现，如果对优点在于不需要事先指定分类的数目．并且能够利用网页进行聚类．就可以将大量的网页缩短为一个类别每个类中各个文本所含有的共同短语来

3、描述这些类目录．这样用户能够根据自身需要．将寻找范围缩小到此外．还允许一个文本出现在多个类别中。以上优点使相应的类别中．这样就可以提高效率．同时也能使得搜该方法成为比较符合实际需要的聚类方法。与此同时．索网页的覆盖率得到提升。后缀树聚类算法在时间复杂性上格外突出．它是一种鉴于此．引入聚类的思想。聚类．就是将物理或抽线性算法．可以在搜索引擎返回第一条结果的同时就象对象的集合分子分成为由类似的对象组成的多个类开始工作．在接收到最后一条结果时显示结果．用户几的过程被称为聚类由聚类所生成的簇是一组数据对乎感

4、觉不到明显的迟滞现象．并且其聚类准确率比经象的集合．这些对象与同一个簇中的对象彼此相似．与典的聚类算法高。所以．将其作为维吾尔文文本聚类的其他簇中的对象相异。文本聚类．主要是依据著名的聚实现方法类假设：同类的文档相似度较大，而不同类的文档相似度较小作为一种无监督的机器学习方法，聚类由于不1相关工作需要训练过程．以及不需要预先对文档手_丁标注类别，1．1后缀树聚类算法(STC)具有一定的灵活性和较高的自动化处理能力后缀树是一种字符串匹配和查询的数据结构．被聚类的方法有很多lll。大致可分为两种：层次聚

5、类广泛应用于基本的字符串处理问题广义后缀树是对(HierarchicalClustering)和非层次聚类(PartitionalClus—后缀树的一种扩展。在文本聚类中．广义后缀树的基本tering)。虽然它们的应用很广泛，可是也有一些缺点，处理单位是词而不是字符。对应的字符串为此序列．或例如需要事先确定好条件，K均值聚类(K—MeansClu—称为短语。下面给出两个定义121。stering：KMC)需要事先确定好K值。在实际的实用中，后缀树：一个具有m个词的字符串S的后缀树T，有可能出现一篇文

6、章属于几个不同类别的情况．例如★基金项目：国家自然科学基金项目(No．61063026)收稿日期：2010—07—29修稿日期：2010—08—29作者简介：买买提依明·哈斯木(1980一)，男，新疆和田人，助教研究生，研究方向为搜索引擎现代计算机2010。09百’＼，三．就是一个包含一个根节点的有向树．该树恰好带有m(2)确定基类，利用后缀树找出所有最大短语束，个叶子．这些叶子被赋予从l到in的标号。每一个内部并对其打分：节点，除了根节点以外，都至少有两个子节点，而且每(3)合并基类．根据规则选择

7、最有代表性的短语束条边都用S的一个非空子串来标识出自同一节点的显示。任意两条边的标识不会以相同的词开始。1．2STC算法的缺点扩展后缀树：若干字符串组成的后缀树，称为一个f1)需要降维扩展的后缀树：m个字符串Sn，其中字符串的长度为虽然在准确率方面STC要优于k一平均算法。但是mn．由这些字符串组成一个扩展的后缀树T．它是一个在空间复杂度方面。它要比k一平均算法需要更多的存包含一个根节点的有向树。该树有mR个叶子，每个叶储空间翻因为在树的生成过程中，需要较大的存储空子都用一个两数字的坐标(k，1)来

8、标识，其中k的范围间来存放树中每个节点所属的文本等大量的信息。以便是从1到n．而l的范围是从l到m，每一个内部节点，在后面的处理过程中，能快速的定位。设文档集：D{1，2，除了根节点外．都有两个子节点并且每条边都用一个非空的S中若干单词构成的一个子串来标识。并且出⋯}、词语集：{1，2，⋯}，STC时间复杂度为O(nm)。随着自同一节点的任意两条边的标识的第一个单词不能相召回文档不断增加。n值直线上升。通常一篇新闻文档同。对于任意的叶子(，从根节点到该叶子所经历的有2