基于K—means与FCA的网页文本聚类算法的研究

2013-04-29朱正国

计算机时代 2013年9期

朱正国

摘要：搜索引擎针对某个查询条件返回给用户的查询结果可能数量非常巨大，要从这么多的返回信息中找到所需要的信息是很困难的。研究聚类算法是为了帮助用户更好地查询到自己所需要的和感兴趣的信息。提出采用基于K-means与FCA的网页文本聚类算法，并分析了两种算法各自的优势与缺点，为研究更优的网页文本聚类算法提供依据。

关键词：聚类算法；搜索引擎； K-means； FCA

中图分类号：TP312 文献标志码：A 文章编号：1006-8228（2013）09-43-02

0 引言

随着互联网的普及，人们对互联网的依赖程度提高，网络成为人们获取信息的一个重要的途径。当我们想查阅资料的时候就可以打开搜索引擎输入所要搜索的关键字。但是目前很多信息是保存在文本文件中的，这就降低了搜索查询的速度。由此，人们开始对文本聚类、信息过滤和信息检索等算法进行大量的研究。文本聚类技术可以将大量文本信息组成少数有意义的簇，能够提供导航/浏览机制，进而来改善检索性能，因此，聚类技术已成为搜索引擎中信息检索过程中对文本信息检索的核心技术。本文针对当前两种重要聚类算法K-means和FCA的进行研究，并将其用于网页的聚类中。

1 网页文本聚类系统的研究现状

文本聚类（Text clustering）文档聚类主要是依据著名的聚类假设：同类的文档相似度较大，而不同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段，为越来越多的研究人员所关注。

目前，应用较多的聚类算法主要有划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法。

2 基于K-means网页文本聚类算法研究

K-means算法是比较典型的聚类算法[4-5]，它的主要特点就是基于距离聚类，它是基于划分的思想。

K-means算法的思想如下：

给定一个有N个元组或者记录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K

3 K-means算法实现

实现聚类的详细步骤如下：

⑴ 处理文本集，随机得到K值，从n个数据对象任意选择k个对象作为初始聚类中心；

⑵ 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；

⑶ 对于每一个文本对象向量，重新计算该文本对象与K个簇中心的相似度，选择相似度最大的簇将该对象文本加入该簇，同时，将该文本对象从其他簇中去除，达到对簇的整体调整；

⑷ 重新计算每个（有变化）聚类的均值（中心对象）；重新计算调整后的K个簇的中心，而不是使用簇内所有文本对象向量的简单算术平均；

⑸ 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤⑵；若文本集合中的文本对象都被聚类完毕，则进入⑹，否则返回到⑵继续执行计算中心；

⑹ 按照预定规则输出聚类结果，算法结束。

根据上述算法进行了程序设计，K-means算法系统数据实现如图1所示。

本系统采用了K=12的聚类，根据K-means算法聚成了12个类，这个聚类是以攀枝花的词频“0.002892637”为中心点分散开的。本程序对72个文本数据进行聚类，当K=12的时候，平均分为12个类，每个类分别由6个文档构成。

4 基于FCA 网页文本聚类算法研究

4.1 FCA算法

形式概念分析（Formal Concept Analysis，FCA）是Wille提出的一种从形式背景进行数据分析和规则提取的强有力工具，形式概念分析建立在数学基础之上，对组成本体的概念、属性以及关系等用形式化的语境表述出来，然后根据语境，构造出概念格（concept lattice），即本体，从而清楚地表达出本体的结构。在形式概念分析中，概念的外延被理解为属于这个概念的对象的集合，而内涵则被认为是所有这些对象所共有的特征或属性集，这实现了对概念的哲学理解的形式化。所有的概念连同它们之间的泛化/例化关系构成一个概念格。

定义1 一个形式背景K=（G，M，I）由两个集合G和M以及G，M之间的关系I?GXM组成，G中的元素被称为形式背景的对象，M中的元素被称为形式背景的属性，若gIm或者（g，m）∈I，则表示“对象g有属性m”。

定义2 假定给定一个形式背景一个形式背景K=（G，M，I），其中G为对象集合，M为属性集合，I为它们之间的一个二元关系，则存在一个偏序集合与之对应，并且这个偏序集合产生一种格结构，这种由形式背景（G，M，I）所诱导的格L就称为一个概念格。格L中的每一个节点是一个序偶（即概念）记为（X，X'），其中X∈G称为概念的外延，X'∈M称为概念的内涵。序偶（X，X'）关于关系R是完备的，即有性质：

X'={x'∈M|?x∈X，xRx'} ⑴

X={x∈G|?x'∈X'，xRx'} ⑵

在概念格节点之间能够建立一种偏序关系，给定C1=（X1，X'1）和C2（X2，X'2），那么C1

4.2 FCA算法实现

本文通过切词分词算法，计算出关键词在文本中的权重，通过关键词在文本中的权重得到了关键词集，我们称作数据集。通过对已经获得的数据集里的词集进行分类，获得新的词集，所得出的聚类结果如图2所示，结果前面的数字代表文本的编号。

5 K-means算法与FCA算法的实验对比

在实验过程中运行的机器是一台PC机，配有CPU Intel Pentium（双核），内存2GB，硬盘160G，所运行的操作系统为Windows XP SP3。

在上述实验中发现，K-means算法程序运行时间明显比FCA算法运行时间短，但是FCA算法准确率高一些；使用概念格提高了准确率，由于FCA算法较复杂，所以运行时间明显比K-means算法程序运行时间长；由于K-means算法较简单，所以节省了运行时间。

6 结束语

目前越来越多的用户喜欢用搜索引擎查询资料，为了帮助用户快速查找所需要的内容，本文通过研究与分析认为，K-means与FCA算法适合作为搜索引擎的算法，而且有各自的优点和缺点，通过利用这两种算法的优点可以方便用户获得自己所需要的信息，为今后提供更优的网页文本聚类算法提供依据。

参考文献：

[1] 韩晓红，胡彧.K-means聚类算法的研究[J].太原理工大学学报，2009.40（3）：236-239