浙江大学算法研究实验报告
数据挖掘
题目：K-means
1
目录
一、实验内容………………………………………………………5 二、实验目的………………………………………………………7 三、实验方法………………………………………………………7 3.1软、硬件环境说明……………………………………………7 3.2实验数据说明…………………………………………………7 图3-1 ……………………………………………………………7 3.3实验参数说明/软件正确性测试……………………………7 四、算法描述………………………………………………………9 图4-1 ……………………………………………………………10 五、算法实现………………………………………………………11 5.1主要数据结构描述……………………………………………11 图5-1 ……………………………………………………………11 5.2核心代码与关键技术说明……………………………………11 5.3算法流程图……………………………………………………14 六、实验结果………………………………………………………15 6.1实验结果说明…………………………………………………15 6.2实验结果比较…………………………………………………21 七、总结……………………………………………………………23
2
3
一、 实验内容
实现K-means算法，其中该算法介绍如下：
k-means算法是根据聚类中的均值进行聚类划分的聚类算法。 输入：聚类个数k，以及包含n个数据对象的数据。 输出：满足方差最小标准的k个聚类。 处理流程：
Step 1. 从n个数据对象任意选择k个对象作为初始聚类中心； Step 2. 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分； Step 3. 重新计算每个（有变化）聚类的均值（中心对象） Step 4. 循环Step 2到Step 3直到每个聚类不再发生变化为止；
k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：
E??i?1?p?Cp?miik2 (1)
其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。
4
5
数据挖掘关于Kmeans算法的研究（含数据集）
