一种基于模糊数学思想的K均值算法

打开文本图片集

摘要：随着云计算、移动计算等互联网技术的快速发展，海量数据分析已成为企业战略决策、营销推广的基础，海量数据挖掘愈显重要。传统的K均值算法作为一种硬聚类算法存在诸多问题，例如数据划分武断、准确率较低等。引入模糊数学思想，提出了一种模糊K均值算法，基于隶属度关系对数据进行了有效的聚类分析，以提高数据挖掘的准确度。

关键词：模糊数学；K均值；硬聚类；隶属度

DOIDOI：10.11907/rjdk.161041

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）005-0041-03

0 引言

随着互联网技术的快速发展，多媒体图像、Web文档、影像视频等海量数据大量涌现，在丰富人们生活的同时，也给检索带来了巨大的工作量。采用自动化、智能化、模式化的聚类分析方法，已经成为海量数据应用研究的热点。K均值作为一种聚类算法，其思想和应用执行过程较为方便，一直以来受到互联网企业青睐，在入侵检测、图像处理、视频聚类、文本数据挖掘、电子商务推荐、遥感信息识别、软件聚类等领域得到了广泛应用，取得了较好的效果[1-3]。随着对K均值算法研究的深入，算法得到了极大的改进。

王敞等[4]分析了K均值聚类算法存在中心设置容易陷入局部最优化等问题，提出了一种基于遗传算法的K均值聚类算法，能够有效结合遗传算法寻找全局最优。在自适应交叉和变异操作中引入K均值操作，克服了传统K均值算法的局部性和敏感性，能够实现较好的聚类效果。陈宗海等[5]分析了聚类算法强化学习过程中，连续状态空间对自适应划分方法存在的缺点，提出了一种基于节点生长的K均值聚类算法，分别给出了离散动作和连续动作下强化学习方法的执行步骤，实验结果显示，该方法可以自动调整划分的精确度、优化学习最佳策略。高滢等[6]提出了一种半监督K均值多关系数据聚类算法，该算法在K均值算法的基础上，改进了类簇的选择方法和数据对象之间的相似性度量方法，将其应用于多关系的半监督学习过程中，充分利用标记数据、对象属性，提高了K均值算法的准确度。陶新民等[7]详细地分析了K均值算法存在的缺点，提出了一种改进的粒子群优化的K均值混合聚类算法。该算法引入小概率随机变异操作，以便能够增强种群的多样性，提高混合聚类算法的全局搜索能力；根据群体适应度方差确定K均值算法操作的时机，增强局部精确搜索能力，缩短算法的收敛时间。王莉等[8]分析了粗k均值聚类算法易受随机初始聚类中心和离群点的影响，导致出现一致性和无法收敛的问题，提出了一种改进的粗K均值聚类算法。该算法能够选择潜能最大的K个对象作为聚类中心，基于其它数据对象和中心之间的距离判定数据归属类簇，提高了算法准确度，克服了离群点的不利影响。胡伟等[9]分析了K均值算法随机指定不同的聚类个数而导致聚类错误率较高的问题，集合层次划分算法，提出了一种改进的层次K均值聚类算法，能够自底向上聚类分析，形成一棵树型结构，并且在树形结构上自动选择聚类。实验结果表明，该聚类提高了数据分析的准确度。赵冬玲等[10]整合网格聚类和K均值聚类算法优势，提出一种基于网格的K均值聚类算法，改进了算法中计算密度阈值的函数，可以有效降低算法的低凝聚度，提高数据聚类分析效率。

传统聚类算法对初始化的聚类中心比较敏感，并且随着初始化聚类中心的不同，具有不同的聚类结果，因此需要根据经验设置聚类中心，很容易陷入局部最优化。另外，传统的K均值算法属于硬划分，每个对象都归属于一个具体的类簇，降低了算法的准确度。为了解决上述问题，本文引入模糊聚类思想，提出一种模糊K均值聚类算法。实验结果表明，该算法能够有效提高聚类的准确度。

1 背景理论

在聚类算法执行过程中，可以对公式（9）和公式（10）进行迭代执行，得到一个具体的模糊K均值聚类算法，在实际的数据集划分过程中使用。

本文基于模糊思想的K均值聚类算法描述如下：算法输入：簇数目K，参数b，包含N个数据对象的数据集。

算法输出：K个簇。

算法步骤：①采用随机初始法为数据集设定K个簇，并指定每个簇的中心为mi；②计算数据集中每个数据对象的隶属函数，计算方法为公式（10）；③基于步骤②的隶属度函数，计算各个簇的中心值mi，计算簇中心采用公式（9）；④遍历数据集中每个数据对象，当隶属度不再发生变化时，算法终止；否则返回步骤②。

3 实验与结果分析

3.1 实验数据与环境

系统实验工具为Matlab2012程序处理平台，实验环境采用的服务器为一台酷睿双核PC，CPU型号为i3-2310M，其主频为2.10GHz，内存为4G，操作系统为Win7。

算法实验数据采用Lang收集的20-NG数据集，使用BoW工具对数据集进行预处理，从中选择4 500篇文档，将这些文档分成9个子数据集，每个数据集包含的文章数量为500篇，具体如下：数据集Binary_1、Binary_2、Binary_3分别包含2个档类别，分别是talk.politics.mideast和talk.politics.misc，每个类别包含250篇文档；数据集Multi5_1、Multi5_2、Multi5_3分别包含5个文档类别，分别是comp.graphics、rec.motorcycle、rec.sport.baseball、sci.space和talk.politics.mideast，每个类别包含100篇文档；数据集Multi10_1、Multi10_2、Multi10_3分别包含10个文档类别，分别是sci.electronics、comp.sys.mac.hardware、rec.sport.hockey、misc.forsale、alt.atheism、talk.politics.guns、rec.autos、sci.crypt、sci.med和sci.space，每个类别包含50篇文档。

4 结语

传统K均值算法属于硬划分，并且算法的初始中心节点需要人为指定，容易降低算法的执行效率及准确度。本文基于模糊聚类思想提出了一种新的K均值聚类算法，将每个数据对象按照隶属度划分到真实的类别中，提升了算法的准确度。未来工作的方向主要是：①改进模糊聚类隶属度函数，以便能更有效地提高算法准确度；②基于遗传算法、粒子群算法、模拟退火算法等，改进K均值初始中心的设置，提高初始设置的准确度，进一步改进算法划分效果。

参考文献：

[1]胡艳维， 秦拯， 张忠志. 基于模拟退火与K均值聚类的入侵检测算法[J]. 计算机科学， 2010， 37（6）：122-124.

[2]吴永芳， 杨鑫， 徐敏，等. 基于K均值聚类的医学图像分割算法[J]. 计算机工程， 2011， 37（5）：232-234.

[3]杨宏宇， 常媛. 基于K均值多重主成分分析的App-DDoS检测方法[J]. 通信学报， 2014， 35（5）：16-23.

[4]王敞， 陈增强， 袁著祉. 基于遗传算法的K均值聚类分析[J]. 计算机科学， 2003， 30（2）：163-164.

[5]陈宗海， 文锋， 聂建斌，等. 基于节点生长k-均值聚类算法的强化学习方法[J]. 计算机研究与发展， 2006 （4）：661-666.

[6]高滢， 刘大有， 齐红，等. 一种半监督K均值多关系数据聚类算法[J]. 软件学报， 2008，19 （11）：2814-2819.

[7]陶新民， 徐晶， 杨立标，等. 一种改进的粒子群和K均值混合聚类算法[J]. 电子与信息学报， 2010， 32（1）：92-97.

[8]王莉， 周献中， 沈捷. 一种改进的粗K均值聚类算法[J]. 控制与决策， 2012，27 （11）：1711-1714.

[9]胡伟. 改进的层次K均值聚类算法[J]. 计算机工程与应用， 2013，49 （2）：157-159.

[10]赵冬玲， 冯艳若， 潘正运. 基于网格的K-均值聚类分析算法研究[J]. 科技通报， 2014， 30（7）：175-179.

（责任编辑：杜能钢）