基于用户特征的K-means聚类算法应用与改进研究

王辉 赵玮 祁 薇

摘要：随着电子商务的快速发展，用户数量与日俱增，商品数量庞大。在海量商品中，如何快速地得到自己想要的商品。基于这个问题，该文利用了用户的个人信息，将用户的个人性格特征、所属职业，以层次树的方式进行量化表示，并采用K-means算法将用户进行聚类，具有相似特征的用户在同一个类别中，将查询最近邻时间降低。最后针对K-means聚类算法初始中心的选择问题，采用kruskal算法构造最小生成树的思想进行改进，解决了k中心点的选择问题。

关键词：个人特征;次树;k-means算法;Kruskal最小生成树

中图分类号：TP391    文献标识码：A        文章编号：1009-3044（2018）35-0017-03

1  背景

中国电子商务研究中心2018年统计数据表明[1]，我国电子商务全局保持了快速发展的势头，成为我国经济发展的主力军。个性化推荐技术是电子商务领域核心技术，它能根据不同的用户推荐符合个人需求的商品。个性化推荐系统的可以划分为三个模块：第一个模块用来提取用户特征，第二个模块进行相关物品检索，最后一个模块用于推荐结果。聚类是用户特征提取模块的重要算法，属于数据挖掘技术之一，能够帮助市场分析人员区分出不同的消费群体来。聚类分析算法有很多，有基于密度的聚类、基于模型的聚类、基于层次的聚类、基于划分的聚类，我们通常使用基于划分中的k-means聚类算法[2]。

该文利用了用户的个人信息，将不同用户的性格特征、从事的行业，通过层次树的方法进行量化表示，之后，利用K-means算法将用户进行聚类，使具有相似个人特征的用户在同一个簇中，降低了搜索最近邻的时间。

2 K-means聚类算法

K-means是一种常见的数据聚类算法，基本思想是：算法接收参数k，然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高，不同聚类中的对象相似度较小。通过不断的迭代，逐次更新各聚类中心的值，直至得到最好的聚类结果。

K-means聚类算法步骤：

1） 先从没有标签的元素集合A中随机抽取k个元素，作为k个子集各自的重心;

2） 分别计算剩下的元素到k个子集重心的距离，根据距离将这些元素分别划归到最近的子集;

3） 根据聚类结果，重新计算重心：

4） 判断聚类函数是否收敛，收敛则结束，不收敛转向2）进一步迭代：[E=i=1kx∈cix-xi2] （2）

K-means聚类算法简单高效，适用于海量数据的处理的特性，但是k值的选择是随机的，对于初始质心点的选取的好坏容易影响最终聚类结果，容易陷入局部最优解。

针对k-means聚类算法的缺陷，该文采用kruskal算法构造最小生成树的思想优化初始聚类质心数目k的选择，避免局部最优解的产生。

3 k-means聚类算法的改进

该文借鉴了最小生成树的原来，提出了一种改进的k-means聚类算法。将系统中的用户作为数据空间的顶点，用户之间的距离，看作是一条边，根据kruskal[4]算法来用点和边构造最小生成树。

改进的k-means聚类算法步骤：

1） 所有用户表示成连通网N=（V，{E}），其中V是顶点的集合，每一个顶点代表一个用户，E是全部边的集合，每一条边代表用户之间的距离。

2） 使用具有n个顶点且无边的非连通图T=（V，{ }）表示初始状态，把每个顶点看成一个连通分量。

3） 在E中选择边长最小的边，如果该边对应的顶点处于T中不同的连通分量上，则将此边加入T中，否则，去掉该边，重新选择一条边长最小的边。重复以上步骤，直到某些顶点的连线构成了环，则将这些顶点加入同一个集合k中，然后把这些顶点在T中删除。

4） 重复第3）步，直到所有的顶点都分配到k个集合中。

5） 计算每个集合的中心，以此作为k个初始的聚类中心。

6） 应用传统的k-means聚类算法完成聚类。

求解过程演示如图1。

4 基于用户个人特征的聚类算法实现

该文将用户的个人特征分为六个属性：年龄，性别，学历，职业，性格特点，个人偏好，按照用户个人特征的不同对其进行聚类。

首先将用户的个人信息进行量化表示。年龄是一个数值属性，使用用户注册信息时填写的年龄值，性别是个二元属性，男性用0表示，女性用1表示，学历划分为小学，中学，大学，硕士，博士五种类型，分别用数字1到5来表示，职业和性格特征将其以层次树的形式进行表示。

美国霍普金斯大学心理学教授、著名的职业指导专家约翰.L.霍兰德（John L.Holland）[3]将职业划分为实际型、研究型、艺术型、社会型、企业型、传统型六大基本类型。参照约翰.L.霍兰德的分类方法，该文将用户职业以层次树的形式进行表示。如图2所示：

六个基本类型内部还有具体的职业划分，例如歌唱舞蹈分为：歌唱家，舞蹈家，歌唱家还分为民族，通俗，美声等等。自然科学分为天文学工作者，物理学工作者，化学工作者等等。自顶向下，从左到右，将每一层进行编号从0开始标号，0为职业，1为实际型，2为研究型，3为艺术型…011为手工操作，012为技术操作，0111为木匠，0112为锁匠…以此类推。

用戶的性格特征也可以分为以下几类：严肃型，严谨型，幽默型（冷幽默，搞笑型），热情型，内向型，外向型，综合型…那么将用户性格特征表示成性格层次树，如图3所示。

通过性格层次树，用户性格特征可以进行量化，例如，某一用户的性格特征是木讷型，可以量化为022，严谨型则量化为0211，以此类推，全部用户特征都可以量化表示。

通过上面两个操作，用户信息全部进行了量化，例如用户甲：性别：男;年龄31，学历：硕士，职业：物理学工作者，性格：严谨型，那么用户甲个人信息量化的结果为{0，31，4，0212，0211}。

之后，采用改进的k-means算法对用户量化向量实行聚类操作，使具有相似个人信息的用户能够聚为一类，从而得到k个用户簇，最近邻的查找在同一个簇中进行，节省了查找时间，提升了推荐精度。

5 试验结果及其分析

该文采用的实验数据来自movielens的数据集，分别利用传统的k-means聚类算法以及改进的基于用户个人特征的聚类算法仿真实验，比较两种算法的性能，以最小空间内搜索到最近邻的数目作为衡量标准。

随机选取ID为16，121，317，608，912五位用户，最近邻阈值选取14，聚类数目分别选取2，3，4，5，（其中4为通过kruskal找到的最佳k值）对每一个活动用户只在其所在的簇中查找最近邻居，查到的最近邻居如表1、2所示：

传统的聚类算法：

通过计算得出，聚类数目2，传统的聚类算法搜索率为1.497，聚类数目3，搜索率为2.366，聚类数目4，搜索率为2.34…，平均搜索率为2.16。

改进的聚类算法如表2所示。

通过计算得出，聚类数目2，改进聚类算法搜索率为1.63，聚类数目3，搜索率为2.69，聚类数目是4（4是通过kruskal找到的最佳k值），搜索率为2.99…平均搜索率为2.37。

通过改进的聚类算法和传统聚类算法的对比，证明了该文改进的聚类算法能够合理地选择k值，在比较小的用户空间内搜索到更多的邻居，这种改进方法提高了查找用户最近邻的效率和精度，能够满足推荐系统对实时性的要求。

6 总结

该文针对传统的k-means聚类算法k值不确定问题，采用了kruskal算法构造最小生成树的思想对其进行改进，解决了由于k的隨机性带来的局部最优解的问题，并且按照用户个人特征，采用职业层次树和性格层次树方式，对用户个人特征进行量化表示，节省了最近邻的搜索时间，提高了推荐精度。

参考文献：

[1] 朱明.数据挖掘[M].合肥：中国科学技术大学出版社，2008：37-38.

[2] Han J W， Kamber M. 数据挖掘：概念与技术[M].北京： 机械工业出版社，2001： 232-235.

[3] Nada Dabbagh， Brenda Bannan-Ritland. Online learning： concepts， strategies， and application[M]. New Jersey： Prentice Hall， 2004.

[4] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社， 2003：175-176.

[5] Sarwar B M.， KaryPis G， Konstan J A， et al. Item-based Collaborative filtering recommendationaglgorithm[C]. Proceedings of the Tenth International World Wide Web Conference， ACM Press， 2001：285-295.

[通联编辑：谢媛媛]