基于weka的数据库挖掘➖聚类方法K-Means算法
目标
1.掌握k-Means算法的原理和聚类过程
2.可以使用k-Means算法实现对给定样本集的聚类。
内容
1.采用k-Means算法,对给出的15个样本数据进行聚类，聚类簇数可自由调整，最后输出簇数为2、3、5的聚类结果。
k-Means初识
k-Means算法是一种常用的聚类算法，用于将一组数据点划分为k个不同的簇（clusters）。每个簇都由其内部的数据点相似性特征而定义，而不同簇之间的数据点则具有较大的差异性。
k-Means步骤
- 初始化：在开始时，我们需要选择聚类的数量k，并且随机选择k个数据点作为初始聚类中心。
- 数据点分配：对于数据集中的每一个数据点，我们会计算它与每个聚类中心的距离。然后，根据距离最近的聚类中心，将这些数据点分配到相应的簇中。
- 聚类中心更新：在每一次迭代中，我们会重新计算每个簇的聚类中心。这个新的聚类中心是该簇所有数据点的均值。
这个过程会反复进行，直到聚类中心不再发生变化，或者达到了预设的迭代次数。K-Means算法的目标是最小化每个数据点到其所属簇中心的距离之和，从而优化聚类的结果。
聚类的结果是一组簇，每个簇由其内部数据点的相似性特征定义，而不同簇之间的数据点则具有较大的差异性。
这个过程通过不断迭代来优化聚类结果，直到收敛到一个局部最优解。最终的结果是一组簇，每个簇表示一个聚类，数据点在不同的簇中根据相似性进行分组。
具体实现
代码如下：
import java.util.*;
public class Km {
private ArrayList<double[]> dataSet; // 数据集链表
private ArrayList<double[]> center; // 中心点链表
private ArrayList<ArrayList<double[]>> cluster; // 聚类链表
private int k; // 类数
private int m; // 迭代次数
private int dataSetLength; // 数据集长度
private ArrayList<Double> wc; // 每次迭代的误差链表
public Km(int k) { // 构造函数
if (k < 1)
k = 1;
this.k = k;
dataSet = new ArrayList<double[]>();
center = new ArrayList<double[]>();
cluster = new ArrayList<ArrayList<double[]>>();
m = 0;
dataSetLength = 0;
wc = new ArrayList<Double>();
}
private ArrayList<ArrayList<double[]>> getCluster() { // 获取聚类链表
return cluster;
}
private void init() { // 初始化，样本数据集
if (dataSet == null || dataSet.size() == 0) {
double[][] dataSetArray = new double[][] { { 8, 2 }, { 3, 4 },
{ 2, 5 }, { 4, 2 }, { 7, 3 }, { 6, 2 }, { 4, 7 }, { 6, 3 },
{ 5, 3 }, { 6, 3 }, { 6, 9 }, { 1, 6 }, { 3, 9 }, { 4, 1 },
{ 8, 6 } };
for (int i = 0; i < dataSetArray.length; i++) {
dataSet.add(dataSetArray[i]);
}
}
dataSetLength = dataSet.size();
if (k > dataSetLength) {
k = dataSetLength;
}
center = initCenter();//初始化中心点
cluster = initCluster();//初始化空的聚类链表
}
private ArrayList<double[]> initCenter() {//初始化中心点，防止找到数据集中的同一个点，但是有一个问题是也不保证数据集中存在相同的点
ArrayList<double[]> center = new ArrayList<double[]>();
int[] randoms = new int[k];
boolean flag;
Random random = new Random();
int temp = random.nextInt(dataSetLength);
randoms[0] = temp;
for (int i = 1; i < k; i++) {
flag = true;
while (flag) {
temp = random.nextInt(dataSetLength);
int j = 0;
while (j < i) {
if (temp == randoms[j]) {
break;
}
j++;
}
if (j == i) {
flag = false;
}
}
randoms[i] = temp;
}
for (int i = 0; i < k; i++) {
center.add(dataSet.get(randoms[i]));// 生成初始化中心链表
// System.out.println(center.get(i)[0]+" "+center.get(i)[1]);
}
return center;
}
private ArrayList<ArrayList<double[]>> initCluster() {
//初始化空的聚类链表
for (int i = 0; i < k; i++) {
ArrayList<double[]> clusters = new ArrayList<double[]>();
cluster.add(clusters);
}
return cluster;
}
private double distance(double[] point, double[] center) {
double x = point[0] - center[0];
double y = point[1] - center[1];
double distance = x * x + y * y;
return distance;
}
//求出离样本点最近的中心点
private int minDistance(double[] distance) {
double minDistance = distance[0];
int minLocation = 0;
for (int i = 1; i < k; i++) {
if (minDistance > distance[i]) {
minDistance = distance[i];
minLocation = i;
} else if (distance[i] == minDistance) // 如果相等，随机返回一个位置
{
Random random = new Random();
if (random.nextInt(10) < 5) {
minLocation = i;
}
}
}
return minLocation;
}
private void setCluster() { //重新设置
double[] dist = new double[k];
//通过两个for循环求dataset中点跟初始中心点的距离
for (int i = 0; i < dataSetLength; i++) {
for (int j = 0; j < k; j++) {
dist[j] = distance(dataSet.get(i), center.get(j));
}
//第二个for循环，求出样本中某点和所有中心点的距离后，调用minDistance求出离该点最近的中心点，归为一簇
cluster.get(minDistance(dist)).add(dataSet.get(i));
}
}
private ArrayList<double[]> updateCenter() {//更新中心点
for (int i = 0; i < k; i++) {
double[] newCenter = new double[2];
int n = cluster.get(i).size();
if (n != 0) {
for (int j = 0; j < n; j++) {
newCenter[0] += cluster.get(i).get(j)[0];
newCenter[1] += cluster.get(i).get(j)[1];
}
newCenter[0] = newCenter[0]/n;
newCenter[1] = newCenter[1]/n;
center.set(i, newCenter);
}
}
return center;
}
private void errorSquare() { //计算每次迭代后，所有点与其对应中心点的距离误差值
double errorValue = 0;
for (int i = 0; i < k; i++) {
for (int j = 0; j < cluster.get(i).size(); j++) {
errorValue += distance(cluster.get(i).get(j), center.get(i));
}
}
wc.add(errorValue);
}
private void kmeans() {
init();//初始化样本数据集
while (true) {
// System.out.println(cluster.size());
setCluster();
errorSquare();
if (m != 0) {
if (wc.get(m) - wc.get(m - 1) == 0)
System.out.println(m);
break;
}
center = updateCenter();
m++;
cluster.clear();
cluster = initCluster();
}
}
public void printDataArray(ArrayList<double[]> dataArray,
String dataArrayName) {
for (int i = 0; i < dataArray.size(); i++) {
System.out.println("print:" + dataArrayName + "[" + i + "]={"
+ dataArray.get(i)[0] + "," + dataArray.get(i)[1] + "}");
}
System.out.println("===================================");
}
private void execute() {
long startTime = System.currentTimeMillis();
System.out.println("kmeans begins");
kmeans();
long endTime = System.currentTimeMillis();
System.out.println("kmeans running time=" + (endTime - startTime)
+ "ms");
System.out.println("kmeans ends");
System.out.println();
}
public static void main(String[] args) {
Km kl = new Km(3);//设置聚类的簇数
kl.execute();
// System.out.println(kl.center.get(9)[0]+" "+kl.center.get(9)[1]);
ArrayList<ArrayList<double[]>> cluster = kl.getCluster();
for (int i = 0; i < cluster.size(); i++) {
kl.printDataArray(cluster.get(i), "cluster[" + i + "]");
}
}
}
运行结果：
优缺点
优点
- 简单而高效：k-Means算法是一种简单且易于实现的聚类算法。它的计算效率通常很高，特别是对于大规模数据集。
- 可扩展性：k-Means算法可以处理大规模数据集，并且在处理大量数据时仍能保持较好的性能。
- 可解释性：k-Means算法产生的聚类结果相对直观，每个数据点都被分配到与其最近的聚类中心所对应的簇中。
- 并行化能力：由于独立计算每个簇的聚类中心，k-Means算法在一定程度上可以并行化，从而加速计算过程。
缺点
- 需要预先指定簇的数量：k-Means算法在运行之前需要指定要生成的簇的数量k。选择不合适的k值可能会导致聚类结果不佳。
- 对初始聚类中心敏感：k-Means算法对初始聚类中心的选择非常敏感。不同的初始聚类中心可能会导致不同的聚类结果。
- 对噪声和离群点敏感：k-Means算法对噪声和离群点非常敏感。它可能会将它们错误地分配到某个簇中，从而影响聚类结果的准确性。
- 仅适用于凸形状的簇：k-Means算法假定簇是凸形状的，对于非凸形状的簇划分效果可能不佳。
- 需要提前确定距离度量：k-Means算法需要使用距离度量来衡量数据点之间的相似性，因此需要在运行之前选择适当的距离度量方法。
k-Means算法是一种常用的聚类算法，广泛应用于数据挖掘、模式识别、图像分割等领域，它通过迭代优化来将数据点划分为不同的簇，根据数据点之间的相似性进行聚类。