基于聚类的内容分类方法

《电脑与信息技术杂志》2014年第三期

1基于改进的K-Means聚类算法的内容分类方法

1.1K-Means聚类算法K-Means算法首先选取初始聚类中心，然后对所有数据点进行分类，最后计算每个聚类的平均值，在每次循环中不断的调整聚类中心，最终使类内对象相似性最大，类间对象相似性最小[7]。其具体的算法步骤有如下五步:（1）从数据样本中随机选取K个对象，作为初始聚类中心；（2）计算其他数据到初始聚类中心的距离，将其与距其最近的聚类中心划为一类；（3）对于每一类，计算所有对象的均值，选取最接近均值的点为新的聚类中心；（4）重新对数据进行聚类；（5）若聚类中心及对象不再变化时，即达到最终聚类状态时，结束。否则转至第3步。传统的K-Means算法对密集海量数据可以达到较好的效果[8]，但仍然具有以下三个问题：（1）算法中的K值为根据经验值设定，忽略了实际数据本身的分部特点和聚类数目，有可能会导致最终聚类结果不准确；（2）传统的K-Means算法中初始聚类中心为随机选取，有可能会与实际聚类中心又较大偏差，最终导致聚类结果的随机性和不稳定性；（3）由于采用迭代更新的方法，当初始聚类中心落在局部最小值附近时容易产生局部最优解。

1.2改进的K-Means算法针对传统的K-Means算法的不足，本文针对K值以及初始聚类中心的选取作出改进，提出了一种改进的K-Means算法。本算法的主要思想是在选取K值时，首先对待聚类的样本进行初步划分，将其划分的类数作为K，并在选取的类中以基于密度的方法选取密度最大的对象作为初始聚类中心，然后结合标准的K-Means算法，完成对聚类样本的分类。具体来讲，本算法主要分为两个阶段：第一阶段为初始化阶段，在此阶段，通过计算类间平均距离的方法对样本进行简单划分，将其初始化为K个初始类，并计算各类中每个对象的密度，选取密度最大的对象作为初始聚类中心；第二阶段为标准的K-Means算法阶段，在此阶段采用标准的K-Means算法，使用第一阶段产生的K值和初始聚类中心进行聚类划分，最终得到完整的分类。为便于描述，本文采用二维空间模型对本文算法进行描述，其理论推演至多维模型与其类似。下面以二维空间的样本分布模型为例阐述如何通过类间平均距离对样本进行简单划分。在二维样本空间X={x1，x2，x3…xn}中，记样本xn的坐标为（xnx，xny），每一个样本对象距离与其他对象的距离可以通过它们在X轴和Y轴的映射坐标来表示，如样本x1与x2的横向距离为|x1x-x2x|，纵向距离为|x1y-x2y|。因此，对于样本空间X，其平均横向类间样本距离dx与平均纵向类间样本距离dy分别为|xnx-x1x|（/p－1）与|yny-y1y|（/q－1），其中p为横坐标不重复的样本个数，q为纵坐标不重复的样本个数，xnx、x1x为x轴方向距离最远的两个点的横坐标，yny、y1y为y轴方向距离最远的两个点的纵坐标。具体的样本划分方法主要有以下几步：（1）首先计算出样本对象的平均横向和纵向样本距离dx、dy；（2）分别从横向与纵向依次求出每两个对象之间的样本距离，若其样本距离小于d<￡dx，则该对象应位于同一类别，其中￡为阈值，可用于调整样本分类精度，￡应取1-2之间的任意值，￡值越小，分类精度越大；朱青等：基于聚类的内容分类方法的研究与应用分析•5•（3）对于横向与纵向同时在二维空间中作出划分之后，属于同一划分区域的类别即为初始化之后的类别。如图1、图2所示，其中图1为初始样本空间，图2为划分之后的样本空间。如图2所示，初始的9个样本空间被初步划分为3个区域，即3个类别。在对样本进行划分之后，K值已经确定，接下来在各个划分区域通过计算每个样本的密度来确定初始聚类中心。本文中通过如下方法计算样本Xn的密度ρXn：（1）计算各类别中样本的平均距离，即平均欧几里得几何距离，如计算样本x1的平均欧几里得几何距离，其计算公式为d＝(d2+…+dt)（/t-1），其中t为该区域中样本的个数，di为该样本x1与所在区域中点xi的距离。2）以样本的平均欧几里得几何距离为半径，对于类中的每一个样本画圆，计算该圆中包括的样本个数M；3）样本Xn的密度ρXn即为以Xn为圆心，以d为半径的圆中的样本个数与圆的面积之比，即：ρXn=M/πd2。各类别种的样本密度计算完毕之后，选取密度最大的样本为各类别的初始聚类中心，之后利用标准K-Means算法进行聚类划分，即可得到最终分类结果。

1.3基于改进K-Means算法的内容分类方法基于改进的K-Means算法，本文所提出的内容分类的方法的具体步骤有如下4步：（1）提取内容特征，采取向量空间模型来表示所要分类的内容，采用向量集合X表示所有内容；（2）对于内容集合X中的任一内容，采用如3.2节所描述的方法计算其样本间距离，并进行初始划分；（3）计算各个样本类之中的样本密度，使样本密度最大的样本为初始聚类中心；（4）以第2步和第3步计算出来的K值和初始聚类中心为参数，运行标准K-Means算法，对所有样本进行分类。通过上述4个步骤，可以实现对内容的有效分类。

2内容分类方法的应用研究

内容分类作为内容管理的重要手段，可以应用在各个方面。本文针对内容管理的特点，结合聚类分析分类类别的无目标性，能够有效组织内容管理系统中的数据，实现对数据处理的高效性，成为一种高效的内容管理和分类方法，可应用于多种场景。（1）在内容的展示方面，为了方便用户对搜索结果的浏览，采用聚类算法对搜索结果文档进行聚类，根据分组情况，输出每个分组的描述信息，分类呈现给客户[9]，使客户缩小检索范围，快速定位到所感兴趣的主题，同时为用户的二次搜索提供信息。（2）在内容[10]方面，内容管理系统中的个性化设计[11]是其突出的特点，此内容管理方法在个性化方面不仅表现为可以使用户自行定义操作界面，而且可以对不同用户提供感兴趣的内容推荐，提高用户体验。通过用户提交兴趣方向或者根据用户的历史访问挖掘用户的兴趣。通过对用户感兴趣的文档进行聚类分析，发现用户的兴趣，把用户分为不同的兴趣小组，根据用户的兴趣，把聚类后的文档快速给相应兴趣小组的用户。（3）在新闻的方面，自动根据不同主题，通过聚类提供最近相关信息的自动汇编。便于用户对同一主题信息的浏览，实现对新闻信息的归类呈现和管理。（4）在对海量数据进行有效的管理方面，采用聚类分析算法，改善文档分类结果，便于对文档的归类组织、管理、存储。

3结论

本文针对传统的K-Means算法的不足进行了相应的改进，提高了K值和初始聚类中心选择的准确性，并在此基础上提出了基于改进的K-Means聚类算法的内容分类方法。这种基于聚类算法的内容分类方法比传统的基于固定分类的内容分类方法更能刻画内容的具体特征，能够实现对内容的有效分类组织，可以灵活的应用在包括内容、内容搜索和内容展示等各个方面，具有十分重要的研究意义。

作者：朱青牛志慧张晓凌单位：北京工业大学软件学院