所有提交的EM系统将被重定向到网上投稿系统.作者被要求将文章直接提交给网上投稿系统各自的日志。

一种简单有效的聚类数据库文档的方法

Dikhtiarenko Oleksandr1, Biloshchytskyi Andrii2
  1. 研究生,计算机科学基础,基辅国立建筑大学,基辅,乌克兰
  2. 教授,技术科学博士,乌克兰基辅国立建筑与建筑大学it系主任
有关文章载于Pubmed谷歌学者

更多相关文章请访问国际计算机与通信工程创新研究杂志

摘要

在本文中,我们描述了一种新的文本文档聚类方法。文档中的单词频率表被用作每个文档的特征。这些表是使用词频创建的,这些词频清除了不具有特定文档特征的单词,并且对整个文档集或大部分文档都是通用的。为了识别这些单词,我们计算了该单词出现在文档中的百分比(逆文档频率)。本文的目的是确定使用频率字典文档作为语义特征的可能性,并确定使用频率表的聚类方法。

关键字

文档聚类;频率词表;语义特征;聚类算法

我的介绍。

在研究搜索引擎以查找电子文档中的模糊重复时,有必要加快搜索过程。实现这一点的一种方法是减少要处理的文档总数。如果我们使用文档本身的主题对所有文档进行分组,这是可能的。不幸的是,我们不能将此用于科学的文档分组分支,因为来自一个科学分支的不同方法和模型可以在另一个科学分支中非常成功地使用。例如,医学方面的一些工作可能包含诊断某些疾病的信息模型和治疗方法,但数据处理的途径和方法将更接近信息技术,而不是健康科学。因此,在信息技术领域中使用相似模型和数据处理方法的其他作品之间进行重复搜索更为准确。
然而,这项工作只是在医学领域解决问题的一个例子。因此,要确定科学作品所涵盖的学科范围,不能用作品本身的属性,需要关注它的内容。在没有预先指定类别的情况下将文档分布到组中称为聚类。对于文档聚类,我们需要确定一种从文档中获取定量数据的方法,并确定这些数据之间的距离。下一步是确定文档进入一个集群的距离,如果有的话-在不同的集群中。这个问题的一个特征是填充文档数据库的方法:首先我们有一个文档,然后是两个,依此类推。我们无法预先知道哪些文档可以到达我们的数据库,哪些组可以在这些文档中。

2相关工作

对数据或文本文档进行集群的方法有很多,让我们考虑其中一些。潜在语义分析[1]-一个专利过程(美国专利4,839,853),但该专利已经过期。该方法是在构造文档-术语矩阵的基础上,利用文档-术语矩阵简化奇异值分解。该算法的一个关键特征是在文档中缺少该类的某些属性的情况下识别同一类的元素。
概率潜在语义分析(probistic Latent Semantic Analysis[2])是Hofmann于1999年开发的,它是对之前算法的改进版本,采用文档术语矩阵和需要共享文档的类别数量。
层次聚合聚类[3]-另一种文档聚类方法,它允许您获得比前两种更高的准确性。该算法的本质是将相似的文档合并到作用域中,然后合并作用域。为了确定文档的相似性,可以使用各种技术,但最好使用不考虑文档大小的标量积。图1显示了一个关联的示例。
图像
K-means[4,5]是一种聚类方法,其中所有文档都由空间中的点表示。该算法将聚类中心定义在同一空间内,尽量减小聚类中心到每个聚类成员的距离。这种方法的缺点是需要设置聚类的数量以及聚类中心的定义。这种方法不适用于最初只有一个文档,然后数据库中文档数量不断增加的情况。
朴素贝叶斯[6]是一个非常简单的算法,它利用概率来工作。在本例中,文档-术语矩阵被转换为概率(而不是它使用的单词的出现次数除以该单词在本文档或组中使用的概率)。这种方法的缺点是它需要所有聚类的训练数据,这在我们的例子中是不可能的,因为我们甚至不知道我们会得到多少个聚类。
N-grams[7]不是聚类方法,只影响文档术语矩阵的创建。在使用这种方法的情况下,首先它过滤所有没有脱离上下文含义的停止词,然后它删除分隔字符(以及其他非字母符号),最后它对所有单词使用词干(切断结尾)。从产生的字符字符串中,找出给定长度的所有可能子字符串(例如3个字符),并使用接收到的数据构建文档术语矩阵。生成的矩阵以另一种方式处理,例如使用kmeans。
自组织地图[8]是一种将多维空间投影到具有少量测量值(通常是二维或三维)的空间上的方法。对于多维空间的投影,它使用一个自组织映射,它由两部分组成:一个神经元,其输入的数量等于输入数据的维度,以及空间中的坐标,用于投影数据。这种方法的缺点是结果很大程度上取决于最初指定的数据(映射)。
正交化(极正交化)[9]是在欧几里得或厄米空间中构造给定线性无关向量系统的过程V是一个非零向量的正交系统,它生成与V相同的子空间。在理论上和在某些实际情况下,它比LSA或k-means要好得多,但它需要一个模型来学习。因此,这种方法不适用于本文所考虑的特定情况。
所有这些方法都很好,而且经过了验证,但它们有一个缺点;它们需要用于训练或初始化的初始数据。唯一的例外是层次聚合聚类(HAC)。理论上,可以使用HAC创建初始聚类,然后使用数据初始化k-means或其他方法。然而,在这项工作中,我们将探索一种不同的方法来评估文档的内容,并将使用频率词表代替文档术语矩阵。

3频率词表

本文中的频率词表是由两列组成的表。第一列是预处理后出现在文档中的单词。预处理包括消除各种形式的表达,使所有的单词以一种形式出现(规范化),消除同义词和停止词,还可以使用词干[10]。在这种情况下,停止词不仅仅是一个绑定符和代名词。单词频率表确实考虑了在所有文档中出现频率很高的单词。例如,“工作”或“研究”可能会在科学著作中遇到,但这些词本身(脱离上下文)并不能描述它们所取自的文件的特征。这些词如果我们用一个或两个文件是不能确定的。在这种情况下,我们也不得不采取大量的文件之前,编制一个停止词的列表。
一旦测试文档被处理,我们就创建了这个表。在创建表之后,行按照单词的使用量降序排列。从结果表中选择一定数量的元素(n),我们假设将其作为特定于文档的特征,然后作为特征聚类。表1就是这样一个例子。
图像
除了选择用于描述的第n个元素外,我们还从最后一个元素(n + 1)开始取n个元素,以元素号2n结束。第二组是“阴影”表,它不用于工作(第一次比较),但之后两个表可以交换它们的项目。

一种处理频率词表的方法

在重复匹配的搜索引擎上,我们做了一些实验[11],得出的结论是,在一个区域写的不同内容的作品(不含重复)可以包含高达80%的共享词。因此,我们有一个想法,在一个领域写的科学论文很可能会操纵特定于该领域的对象和术语。此外,这些术语在其他领域可能完全没有必要。因此,通过比较文档中出现的单词集,我们可以确定这些文档的主题是如何彼此接近的。让我们考虑一个例子,我们有一个空的文档数据库,我们一个接一个地获取新文档。对于第一个文档,我们构建了一个表T1,只要它是一个单独的文档,它就会立即进入一个新的集群C1,文档的特征(频率表和阴影表)成为集群本身的特征。对于我们获得的每个额外文档,我们构建它的比较表(T2..Tn),并将这个表与我们拥有的所有集群的所有表进行比较(在这种情况下,只有集群C1的表)。为了比较表,我们使用Jaccard距离[12]:图像
将结果值与允许的最小值Jmin进行比较,如果结果值大于此值,则文档属于集群C1,如果不大于此值,则创建一个新的集群C2,并将文档添加到其中。进入数据库的每个新文档都将与所有现有集群进行比较,如果不匹配,则创建自己的集群。为了使聚类的特征适应其所包含的所有新文档,每当聚类获得一个新文档时,都会重新计算聚类的频率词表。对于重新计算,我们使用新文档的新文档频率词表,以及集群中的文档数量(k)。集群的表T1包含值{w1, w2, w3…wn},其中w - word具有与新文档相似的结构和表。在计算单词的频率时,我们使用了以下公式:图像其中wc是来自聚类表的词频,wnew是来自新文档表的词频,k是聚类中已经包含的文档数量。在这个阶段,我们不仅总结了主表的频率,还有影子表。如果阴影表中某些单词的频率值大于主表中频率的最小值,则主表中的阴影值将主表中的较低值推入阴影表。因此,频率表总是对应于集群中的文档集群集。

五、算法的实验验证

为了检验算法的能力,我们取了一个包含150篇论文的小型科学论文数据库。这一小组数据是因为我们手动验证算法的准确性,这对于大量的文档来说是很难检查的。数据库中的文档有不同的主题(从整个论文数据库中随机选择)。该算法的任务是准确地将该主题的文档分组。在实验中,我们使用了以下变量:N是频率表中的字数(2N是主表和影子表中的字数总和),k是两个表相似的最小容差因子(Jaccard distance)。
首先,将所有文档转换为文本格式,删除标点符号和常见的停止词(没有进行识别特定停止词的工作)。
为了评估质量,我们使用了两个参数:精度(P)和聚类数量(Q)。手动确定每个聚类的精度,并根据聚类中的文档总数估计一个受试者的文档数量,然后取平均值。所得结果如表2所示。
图像

六。结论

在本文中,我们考虑了使用频率词表聚类文档的方法。通常,documentterm矩阵用于文本文档的聚类,但如果我们没有完整的文档数据库,并且任务是分析新传入的文档,则使用documentterm矩阵是不切实际的。在这种方法中,每个文档只构造一次频率词表,只有在集群中输入一个新文档时才转换集群表,其他的保持不变。给出的实验数据说明该方法可以应用于实际,但算法系数的选择需要非常谨慎,这又需要进一步的实验。最后,应该从可能对聚类结果有重大影响的停止词中清除所获得的数据。

参考文献

  1. 兰auer、Thomas K.、Peter W. Foltz、Darrell Laham,â '  -潜在语义导论analysisâ ' ——话语过程,Vol. 25, No.2-3, pp.259-284, 1998。
  2. Heintze, Nevin, â '  -可伸缩文档fingerprintingâ '  -, USENIX电子商务研讨会,Vol. 3, No. 1, 1996。
  3. Willett Peter, â ' Â:层次文档聚类的最新趋势:一个关键的reviewâ ' Â,信息处理与管理,第24卷,第5期,第3页。577 - 597年,1988年。
  4. 施泰因豪斯,â '  - Sur la division des corps materiels en partiesâ '  -,牛。专科学校Polon。科学。,Vol.4, pp.801—804, 1956.
  5. Lloyd S., â '  -最小二乘量化在PCM中的应用'sâ '  -,贝尔电话实验室论文,Vol.28, No.2, pp.129-137, 1982。
  6. 多明戈斯,佩德罗,迈克尔·帕扎尼,Ã①Â′Â 0 -1下简单贝叶斯分类器的最优性lossÃ①Â′Â,机器学习,第29卷,No.2-3, pp.103-130, 1997。
  7. 苗英波,vladokeelj, EvangelosMilios, â '  -基于字符N-grams的文档聚类:基于术语和单词的比较评价clusteringâ '  -,第14届ACM信息与知识管理国际会议论文集,pp.357-358, 2005
  8. Björck, Åke, Clazett Bowie, Ã①Â′Â计算正交的最佳估计的迭代算法matrixÃ①Â′Â′,SIAM期刊上的数值分析,卷。8第二页。358 - 364年,1971年。
  9. Lovins, j . B。一个¢€•发展阻止algorithmA¢€–,麻省理工学院信息处理组,Vol.11 No.1-2 pp.22-31, 1968。
  10. Biloshchytskyi A., Dikhtiarenko O.,â '  (textsâ '  -)中匹配查找方法的有效性,复杂系统管理,Vol.14, No.1, pp. 144 - 147, 2013。
  11. 雅卡尔P.,â '  -分布de la flore高山丹斯盆地和丹斯奎尔克地区voisinesâ '  -,公牛。Soc。Vaudoise科学。自然界,卷。37,页241-272,1901。
全球科技峰会