一种改进的K—medoids知识聚类算法研究

谭黔林+覃运初+卢艳兰

摘 要：根据文本信息在聚类过程中的特点构建了一种基于K-medoids的文档聚类方法，并结合文本特征提取KNN算法对训练文本进行测试，该方法首先利用K-medoids在聚类过程中实现简单、收敛速度快的特性，再利用KNN算法在文档特征提取过程中简单、高效的特点，对训练进行聚类划分。实验结果表明，利用该方法在对文档进行聚类时，F1值、耗时及分割数等方面与KNN及CLKNN算法相比都有较大提高。

关键词关键词：K-medoids；知识聚类；聚类分析技术

DOIDOI：10.11907/rjdk.161475

中图分类号：TP312

文献标识码：A ：1672-7800（2016）008-0013-03

0 引言

聚类分析技术已广泛应用于各大领域，并已在原有基础上针对不同的应用领域进行了改进，提出了相应的算法及模型，大体上可分为网格、层次、密度、层次及划分方法。大数据时代，各类结构化、半结构化的数据资源在快速增长，用户在检索信息过程中的搜索范围也越来越广，聚类分析技术的引入可以有效提高相似信息的分类，使同一类的信息个体具有高度的同质性，使不同类之间的个体具有高度的异质性[1]，从而有效提高了用户信息获准率。

知识搜索，实际上是将信息按照学科性质、从属关系及层次关系进行组织，根据关键词、关键字及其属性进行分类汇总的过程，通过聚类规则将同属性、高相似度的信息进行分类，有效解决当前大数据集下信息的获准率问题，从而提高知识获取的速度与准确度。K-means聚类方法由于实现简单、收敛速度快而被广泛应用，但由于K值难以估算从而给具体分类带来了困难。大数据集中，为了有效实现数据分类，阮光册在文献[2]中将集对分析同异反系统和文本向量空间模式相结合，提出了一种基于流形结构的聚类分析算法；杨欣欣、黄少滨在文献[3]中通过相关性度量指标Goodman-kruskalτ对特征变量和对象变量的相关性进行衡量，提出了一种高阶层次联合聚类算法；文献[4]中利用二分图聚类算法构造了基于Web数据挖掘的搜索引擎。因此，通过聚类方法将同质性的信息进行聚合，解决知识搜索中的泛在性，对大数据集下的知识搜索相关研究具有重要意义。

1 K-medoids聚类算法

聚类是数据挖掘中的一种常用方法，通过聚类将相同特质和具有共同属性的个体归为一簇，在不同的簇中，同质性的个体具有较高的相似度，表现为个体之间的距离较短，异质类个体之间的距离则表现为距离越大，相似度越低。K-medoids聚类算法是一种基于划分的聚类方法[5]，相比K-means算法而言，K-medoids算法更容易实现，具有较好的收敛性和时间复杂度，在全局搜索时所得到的效果更好。

1.1 算法描述

K-medoids算法广泛应用于大数据集下的文本分类，算法过程是将N个数据对象划分为K个类作为聚类参照中心，对未划分到类中的数据对象按照距离优先原则划分到邻近的簇中，得到初始聚类后，将剩余的对象按距离长短进行重新划分，反复执行这一过程，直到簇收敛。K-medoids聚类算法是基于聚类准则函数的最优原则，使用最接近聚类中心的对象作为类中心，增强了算法的鲁棒性，对小的数据集非常有效[6]。

1.2 K-medoids算法过程

输入：K个簇，包含n个数据集。

输出：符合条件的K个聚类。

在输出的符合条件的K个聚类中，聚类效果通常使用绝对误差标准函数来进行衡量，定义为：

式（1）中，x为簇si中的一个对象，si是聚类中心的第i个簇，k表示簇的数量，C值的大小取决于簇内各对象与中心点的距离，C值越大说明簇內各对象的相似类越低，反之亦然。

①从n个数据集中，选k个对象作为聚类的初始中心点；②对离中心点距离较远的对象进行划分，将其分配到附近的簇中；③对每个簇的均值进行重新计算，为每一簇赋予新的值给；④重复②、③步骤，直到类收敛。

1.3 K-medoids算法扩展

K-medoids聚类算法在聚类过程中，通过对簇中心点周围的对象进行反复均值计算更新，能够得到较为理想的分类结果。在知识搜索过程中，利用这一思想，通过类别、关键词、关键字、同一性等方式对不同信息资源进行分类汇总，产生初始的类，再利用K-medoids聚类算法对知识的特征码进行聚类分析，直到类收敛，可以有效提高信息知识的分类效果。

2 基于K-medoids的聚类构建

2.1 特征提取

在进行聚类前，所有知识信息都是相对独立的，利用KNN算法进行特征提取时根据这一特点进行假设判定：①假设所有的知识信息都是相对独立的，知识信息内容出现的频率和位置无关；②将收集到的知识信息进行抽取映射分组，分成U1，T1；U2，T2；…；UN，TN个组别；③假设信息知识分组的训练集有C，C中有N个不同的类别V1，V2，V3，…，VN，其总数有M；④最后将特征对数进行降维处理，表示为Wi={a1，a2，a3，…，an}T，其中i的取值范围为0～M（含M）。

在特征提取阶段，按照知识信息的特征向量，将训练过程中分类尚未确定的知识信息W表示为：W={a1，a2，a3，…，an}T；再次从C训练集中提取出W中相似度较高的训练集知识信息Wi={a1，a2，a3，…，an}T，得到知识信息的高相似性分类，最后W归属分类知识信息。待分类知识信息和训练集的分类根据向量夹角余弦公式计算，如下：

根据K邻近值，对分类信息W在各分类中的所属关系进行计算，如下：

最后得到Vm，其中包含了等分类的信息文本W。

在分类算法中，KNN算法具有简单、高效的特点，在文本信息分类过程中经常用到此方法。

2.2 聚类构建

在大数据集中，对一些复杂的信息进行分类，单独采用K-medoids或KNN算法都具有一定的局限性或不足，K-medoids在大数据集聚类过程中存在收敛度低、产生的类目较多等缺点，而KNN在聚类过程中也存在耗时大、误差也较大等不足，基于以上考虑，在聚类过程中同时采用K-medoids和KNN算法对大数据集下的信息知识进行二次聚类处理，以解决在大数据集下对信息知识聚类过程中存在的中足，提高聚类的效果和效率，聚类过程如下：输入：训练集W，包含n个数据集。输出：m个聚类。①从数据集中随机对数据进行抽取，找到若干个样本集W1，W2，W3，…，Wm作为原始的聚类中心点；②通过K-medoids算法，用公式（1）对样本集进行聚类处理，并将每个聚类标记为C1，C2，C3，…，Cm；③反复从训练集W中对样本的相似类进行计算，得出最大相似度的文本；④在计算出初始聚类后，利用KNN算法对类进行收缩计算，去除因增长较慢而未形成的类，调整聚类中心；⑤重复步骤①-④，直到所有数据被划分出m个类，且无独立的文本数据。

3 实验分析

实验之前，考虑到计算过程中文本相似度较大，所产生的维度也较高，为确保计算效果，在进行聚类时，对文本类别、标题、关键字、关键词进行分析，以降低计算时文本产生的维度。同时利用本文所提出的方法进行了实验，实验环境如下：实验时所采用的系统环境为Windows 8 64位，处理器为Inter i5 5200 2.2G，内存为6G，实验工具为Eclipse和Matlab。数据集源自复旦大学计算机信息与技术系国际数据库中心自然语言处理小组提供的文本分类语类库，文档总量为19 637篇，共20个类别，选取其中农业、艺术、军事、计算机、经济、教育、环境、医学8个类别，共2 627个文本，其中用于训练的文本总量为1 839个，余下788个文档用于测试，实验数据如表1所示。

对文档聚类效果进行评价，常用的指标参数为文档的查准率P（precision）、查全率R（recall）及F1值（与准确率、查全率有相关性）[7]。查准率由文档正确分类数T1和用于测试的总文档数T2之间的比值构成，计算公式如下：

查全率是衡量检索性能的一项重要评价指标，是计算结果中所得到的正确的分类文档数T1与实际应得到的文档数T0之间的比值，计算公式如下：

F1值是为了平衡查准率和查全率之间的关系而提出，当查准过高时，查全率相应就会降低，反之亦然，F1值的计算公式如下：F1=P×RP+R×2×100%（6）

实验过程主要分为两个阶段，实验中将文本提出的方法与传统的KNN算法和文献[8]中所提出的CLKNN算法进行对比实验，第一阶段主要确定3种不同算法的最佳分类点，在初始分类值的基础上依次递增，根据P、R及F1值确定最佳分类值。3种不同算法最佳分类的比对情况如表2所示。

从表2中的实验数据可得出，KNN算法在进行聚类划分过程中，当取值为19时，P、R及F1值达到最大值，此时聚类效果最佳；CLKNN算法在取值为14时，各项指标达到最大值；本文中的算法取值为17时P、R及F1值为最大，聚类效果达到最优。在得到最优取值的前提下，进行第二阶段的实验，对比3种不同算法在实验过程中的优越性，实验数据如图1和表3所示。

考虑到文本聚类的综合评价指标不由查准率和查全率单独确定，因而省略了P、R值的对比。从图1和表3两组数据中可看出KNN算法和改进的CLKNN算法与本文提出的方法在对数据集进行聚类后的F1值、耗时及分割个数的对比情况，图1中，CLKNN算法相对于KNN所得到的F1值有了明显提高，平均提高了3.8%，而本文中的算法在前两种算法基础之上有了进一步提升，比CLKNN算法平均提高了1.2%。表3中，KNN算法在聚类时耗时最长，由于CLKNN算法在对训练集进行聚类时分割的文数较多，所花费的时间相对于本文提出的算法多了18s，而本文算法在分割上较CLKNN少，因而在训练过程中所耗费的时间也较CLKNN少，通过两组数据的分析证明，本文所提出的方法在对文本的分类性能上较前两种算法均有所提高。

4 结语

本文利用K-medoids聚类方法并结合KNN算法在文本聚类中的优势，提出了一种基于K-medoids的改进的知识聚类算法，在实验过程中经过大量的训练及测试，并与原有KNN算法及经过改进后的CLKNN进行了性能测试、比较，结果表明，本文所提出的方法不管是在聚类效果还是在测试耗时及分割方面都有明显提高，进一步解决了KNN算法在聚类过程中耗时长、文本丢失较大的缺点。本文算法在性能方面较KNN和CLKNN算法有明显提高，但本方法是在对测试集进行降维处理前提下所进行的实验，在测试过程中减少了对本文算法的部分开销，此外大数据集下本算法的峰值及性能评测、维度处理也需重点研究。

参考文献：

[1] 唐然，龙腾锐，龙向宇.基于模糊聚类的改进遗传算法[J].重庆大学学报，2008（2）：165-169.

[2] 阮光冊.基于知识关联的检索结果聚类分析研究[J].情报科学，2015（2）：63-66.

[3] 杨欣欣，黄少滨.高阶异构数据层次联合聚类算法[J].计算机研究与发展，2015，521（1）：200-210.

[4] SHARIFI，ABOOSALEH M，AMIRGHOLIPOUR.Intrusion detection based on joint of k-means and knn[J].Journal of Convergence Information Technology，2014（5）：45-52.

[5] SHASHIDHAR HV，SUBRAMANIAN VARADARAJAN.Customer segmentation of bank based on data mining security value based heuristic approach as a replacement to kmeans segmentation[J].International Journal of Computer Applications，2011（5）：66-72.

[6] S VIMALA.Convergence analysis of codebook generation techniques for vector quantization using K-Means clustering technique[J].International Journal of Computer Applications，2011（3）：85-92.

[7] NALINI SINGH，AMBARISH G MOHAPATRA.Breast cancer mass detection in mammograms using kmeans and fuzzy cmeans clustering[J].International Journal of Computer Applications，2014（3）：34-40.

[8] 路永和，何新宇.文档相似矩阵在提高KNN分类效率中的应用[J].情报理论与实践，2014（1）：141-144.

[9] HEJIN YUAN，CUIRU WANG.A human action recognition algorithm based on semi-supervised kmeans clustering[J].Transactions on Edutainment，2014（6）：47-52.

（责任编辑：孙 娟）