基于标记样本和相似度调整的k均值算法在文本聚类中的应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于标记样本和相似度调整的k均值算法在文本聚类中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
[摘 要]在机器学习领域的众多实际应用中，获得标记样本通常需要付出较大的代价。在一些情况下，获得所有的类标记是非常困难的。近年来，半监督学习已经成为机器学习领域的一个研究热点。本文对聚类的相关技术和半监督学习进行了研究，介绍了文本数据的预处理、距离公式、聚类算法评估准则以及几种k-means算法的扩展算法。
中图分类号：TP31 文献标识码：A 文章编号：1009-914X（2016）29-0361-01
0 研究背景
数据库技术为存储海量数据信息提供了可能，但随着通信网、互联网的迅速发展和日益普及，信息量呈指数级别增长，由于信息产生的速度远远超过人们对信息的利用能力，使得人们在海量的信息面前无所适从，给使用者带来巨大的时间、资金和精力的浪费。因此，通过建立合适的学习系统，将信息分门别类才便于挖掘信息的内部规律，这些信息才可能为人类所利用。
在现实问题中通常存在大量无标记样本，但有标记样本则比较少，无标记样本的获也取相对容易，而获取有标记的样本则要困难得多。尤其是在一些在线应用中这一问题更加明显，从大量的在线文档中获取无类标记的新文章十分简单，如果建立一个分类器来把这些新文档分类到各个类中去，或者想要获得这些文档的类标记可能需要耗费大量的人力、物力和财力。显然，如果只使用少量的有标记样本，那么利用它们所训练出来的学习系统往往很难具有泛化能力，在某些特定的条件下同时使用标记样本和无标记样本的学习结果要优于仅仅使用少量已标记样本的学习结果。
1 研究现状
聚类技术已经在模式识别、图像处理、信息检索、商业数据分析等许多领域的应用中取得长足进展。在模式识别中，聚类分析被应用于语音识别、计算机视觉、字符识别、雷达信号识别、文本识别、气象数据分了、食品检验、水质分析、自动化过程控制和工具状态监测等方面。在图像处理中，聚类分析方法被应用于灰度图像的分割、彩色图像的分割、纹理图像的分割、图像边缘的检测、图像增强、恢复与压缩等方法；在商业领域，聚类分析常被应用用于客户群体分类、预测客户的消费模式和习惯等；文本聚类在信息检索领域有着广泛的应用，通过聚类发现数据空间分布特征，从而建立主题索引，帮助用户快速的找到所需信息。同时，聚类分析也用于个性化信息推荐系统。
基于标记样本和相似度调整的k-means算法（LSKM）是根据半监督学习的聚类假设条件，结合了基于约束和距离测度两种思想的半监督聚类算法。为了读者更好地理解这个算法，本章首先阐述了文本处理技术、无监督学习的的理论基础半监督聚类算法和半监督聚类算法研究的一些相关问题，包括：样本间的距离学习、聚类算法的评价准则、k-means聚类的扩展算法等。
2.1 文本处理
文本是非结构化的数据，无法用数据挖掘的方法对文本直接进行处理，需要先对文本进行预处理，使文本最终表示成为一种结构化的计算机能够处理的形式。文本预处理是聚类分析中一个非常重要的环节，预处理的质量直接影响着聚类分析的性能。预处理包括：正文提取、去除停用词（stopwordremoval），提出词干（stemming），处理数字、连接词、标点以及字母大小写等预处理工作。如果处理中文还需要对文本分词。对于网页，还需要移除HTML标签和鉴定网页主要内容等。虽然经过预处理后的本文长度会有所降低，但此时的文本仍然是非结构化的数据。为了方便计算机处理，需要将这些文本转化成某种结构化的模式，这个转化的过程就是文本的表示和特征选择。这一节将对这两种技术进行简要的阐述。
2.2 聚类
将物理或抽象对象的集合分成相似的对象簇的过程称为聚类（Clustering），簇（cluster）是样本对象的集合，这些对象与同一个簇中的对象彼此相似，而与其它簇中的对象相异。一个样本对象簇可以整体看作一个组，因此可以看作一种数据压缩形式。尽管分类是一种识别对象组或类的有效手段，但是它常常需要高昂的代价收集和标记大量训练元组集或模式，以便分类算法使用它们对每个组建模。通常，人们更希望反方向处理：首先，基于样本的相似性把样本划分成组，然后给这些数量相对较少的组指定标记。这种基于聚类的过程的另一个优点是可以适应变化，并且能够挑选出区分不同组的有用特征。
2.3 聚类算法评估
聚类结果体现了数据的分布特征，从未知数据中发现有意义的模式。评估过程是对所发现的的模式的有效性的验证，用来指导用户调整模型和参数值。从直观上看，就是把相似数据划分到同一个簇中，而不相似的数据尽可能划分到不同簇中。
（1）纯度度
纯度（purity）可以理解为被正确聚类的对象的比例。该值越大，说明聚类的结果与被数据的实际分布情况越符合。对于输出结果的每个簇，统计其每个样本类标签，用出现次数最多的类别作为该簇的类标签，纯度值即为类别与所在簇类标签相同的样本所占的比例。
（2）信息增益
信息增益（InformationGain）也是一种评价聚类结果与实际数据的匹配程度的一种方法。其匹配度为每个簇的信息增益的加权求和，其权值为簇中样本占全部样本的比例。这个值越小，表示聚类结果与实际数据的匹配程度越高。如果结果中簇的样本的类标签相同，信息增益为0，反之，如果簇中样本含有多个类标签，则信息增益就比较高。
（3）紧密度和分离度
紧密度（compactness）和分离度（separation）用来反映聚类的质量。紧密度反映属于同一类的成员之间相似的程度，紧密度越大，类内相似性越大；分离度反映类间成员之间的相似性，分离度越大类间相似性越高。
2.4 半监督学习的两个假设
半监督学习之所以能够发挥作用要归功于两个常用的基本假设，即聚类假设（ClusterAssumption）和流形假设（ManifoldAssumption）。聚类假设是指在相同簇（cluster）中的样本有较大的可能拥有相同的标记。该假设等价于低密度分隔（LowDensitySeparation），即决策边界应尽可能通过数据较为稀疏的地方，从而避免把稠密的簇中的数据点分到决策边界两侧。在这一假设下，大量无标记样本的作用就是帮助探明样本空间中数据分布的稠密和稀疏区域，从而指导学习算法对利用有标记样本学习到的Q策边界进行调整。聚类假设简单、直观，经常以不同的方式直接应用于各种半监督学习算法的设计当中。
3 总结
半监督学习已经成为机器学习领域的一个研究热点，它必将得到更加广泛的应用。本文提出的基于正例和相似度矩阵调整k-means算法，还有可以改进之处。近年来，语义网技术得到了快速的发展，成为未来的重要研究方向之一。语义网技术使文本的特征提取和文本距离公式都发生了改变，从语义层次进行文本理解和分类是作者今后研究工作的重点。对半监督学习领域进行的初步探索，虽然取得了一些成果，但是许多问题有待于进一步深入研究和发现。
参考文献
[1] BingLiu，Web数据挖掘[M].俞勇，薛贵荣，韩定一译.北京：清华大学出版社，2009.111-140.
[2] 周志华，王珏.机器学习及其应用2007[M].北京：清华大学出版社，2007.45-132.
[3] 张邦佐.基于正例和无标记样例学习研究[D]：博士学位论文，长春：吉林大学计算机科学与技术学院，2009.