K-means算法研究

2014-03-26胡朝清

长春工业大学学报 2014年2期

胡朝清

（德宏师范高等专科学校，云南德宏 678400）

1 应用程序设计

K-means算法首先接受输入量k；然后将n个数据对象划分为k个聚类，以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的［1］。依据K-means聚类的原理，在做应用程序设计时，一般将程序分为主程序、命令行解析模块、数据文件读取模块和聚类分析模块4大部分，各部分关系如图1所示。

图1 程序构件图

主程序通过命令行解析模块获取用户输入参数，创建聚类分析模块和数据读取模块，通过数据读取模块将输入文件读取到聚类分析模块中，然后调用聚类分析模块将数据进行分类并直接输出。

1.1 命令行解析模块（cmd＿parser）

命令行解析模块为程序实现一个简单易用且功能强大的用户交互界面，通过命令行的方式获取用户需要的参数，包括数据文件路径、数据集名称所在列、将数据集分割成为聚类的个数、判断浮点数是互相等的阈值等［2］。使用命令行作为交互界面不仅使用方便，而且便于通过脚本实现自动货批量处理，为该程序与其它程序整合和集成提供了方便。该模块通过调用GNU getopt模块实现命令行的解析，接受以下参数：

1.2 数据文件读取模块（data＿reader）

由于在数据挖掘和数据分析中，经常需要进行数据读取操作，因此为了让程序能够尽量通用，方便以后的扩展，组织文件读取模块和数据分析模块，其使用方式如图2所示。

图2 通用的数据读取框架

在此，将数据分析模块定义为一个抽象类solver，提供add＿data和solve两个抽象方法。当数据读取模块成功地从输入流中获取一行数据时，调用solver的add＿data方法，将数据添加到solver的sovle方法对数据进行处理。当使用不同的算法分析数据时，只需要继承solver类，在子类中实现自己的solve方法即可，无须再考虑数据读取和文件格式解析的问题。

1.3 聚类分析模块（k＿means）［3－4］

数据读取完毕后，程序通过k＿means类对数据进行处理。k＿means类继承自solver类，将解题过程分为“初始化”、“迭代计算”和“输出结果”3个步骤进行，如图3所示。

图3 K-means算法实现类图

2 算法实现［5－6］

程序主要基于STL来实现，下面分别从数据结构和算法实现两方面进行分析。

2.1 数据结构

在输入数据上使用一个vector保存，每个元素为一个结构体，包括元组名称和数据两部分，如图4所示。

图4 输入数据存储

虽然在迭代过程中只对数据集进行顺序操作，不进行随机访问，但使用list会造成读取效率降低。虽然vector在初始化数据集的时候空间增长时有一些额外开销，但读取完毕之后就不再存在这样的内存占用，因此是比较值得的。而读取完毕后就不再对该数据进行任何写操作，因此，也不必考虑vector的内存失效问题。

由于聚类中心数据量不大，在聚类过程中又需要频繁读写，因此使用vector保存数据。聚类中心结构保存如图5所示。

图5 聚类中心位置

聚类结果仅进行“尾部添加”操作，无须随机访问，似乎比较适合使用list。但是由于每次迭代完毕后，都需要将结果集清空重新进行下一轮迭代，而list的销毁需要消耗线性时间复杂度，因此，仍然使用vector保存聚类结果，如图6所示。

图6 聚类结果

虽然vector在增长过程中可能会消耗一些额外时间，但由于每轮迭代后并不释放vector占用的空间，这类额外开锁会非常小，可以忽略不计。

2.2 算法实现

程序初始化时，在聚类中心数组中填充数据集中的前n组数据，然后开始迭代：将数据集中的每个数据与聚类中心点的距离进行比较，将数据焦距的数据添加到与之最近的中心点所对应的结果集里，在添加过程中直接累加各结果集的向量和，为一次迭代完成后重新计算聚类中心提供方便，提高程序运行的效率。当一次迭代和前一次迭代之间聚类中心没有再移动时，认为迭代已经完成，进入输入聚类结果阶段［7－8］。