当前位置：首页 > news >正文

K-means算法

news 来源：原创 2024/5/8 20:02:10

一、K-means算法

K-means(K 均值)算法是机器学习中常用的一种简单的聚类算法，该算法属于划分式聚类算法。其中，K 表示需要将数据集划分成的簇的个数。在运用Kmeans算法时，由于我们一般不知道数据的分布情况，也就无从得知数据的分簇的数目，所以一般通过枚举来确定 k 的值。另外，在实际应用中，由于K-means一般作为数据预处理，或者用于辅助分类贴标签，所以 k 值一般不会设置很大。

K-means 算法的思想：首先，确定 k 个初始点作为分簇的中心；接着，将数据集中的每个点分配到一个簇中，即为每个点找到距离其最近的质心，并将其分配给该质心所对应的簇；然后，每个簇的中心更新为该簇所有点的平均值。再次重新分配数据集中所有的点，如果所有的点被分配的簇和之前一样，即簇的中心不会再改变，则此时的 k 个簇就是我们所需要的；如果某个点被分配的簇改变了，则分配完所有的点之后重新更新每个簇的质心，重复分配、更新操作直到所有簇的中心不再改变。

二、实现K-means算法

K-means 算法的 python 实现
本算法所用的数据集为 uci 上的聚类算法数据集 3D Road Network 。文件中的数据格式为如下（部分数据，用于示例）：

144552912,9.3498486,56.7408757,17.0527715677876

144552912,9.3501884,56.7406785,17.614840244389

#！/usr/bin/env python
# -*- coding: utf-8 -*-

 
from numpy import *
import matplotlib.pyplot as plt
 
def loadDataSet(fileName):
    dataSet = []
    f = open(fileName)
    for line in f.readlines():
        curLine = line.strip().split(',')   # 这里","表示以文件中数据之间的分隔符","分割字符串
        row = []
        for item in curLine:
            row.append(float(item))
        dataSet.append(row)
 
    return mat(dataSet)
 
# 求向量距离
def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2)))
 
 
# 随机生成k个点作为初始质心
# 若选择随机生成的点作为初始质心，则有可能导致后面更新质心时出现有的质心为 NaN(非数) 的情况
# def initCent(dataSet, k):
#     n = shape(dataSet)[1]  # n是列数
#     centroids = mat(zeros((k, n)))
#     for j in range(n):
#         minJ = min(dataSet[:, j])  # 找到第j列最小值
#         rangeJ = max(dataSet[:, j]) - minJ  # 求第j列最大值与最小值的差
#         centroids[:, j] = minJ + random.rand(k, 1) * rangeJ  # 生成k行1列的在(0, 1)之间的随机数矩阵
#     return centroids
 
# 选前k个点作为初始质心
def initCent(dataSet, k):
    data = []
    for i in range(k):
        data.append(dataSet[i].tolist())
    a = array(data)
    centroids = mat(a)
    return centroids
 
# K均值聚类算法实现
def KMeans(dataSet, k, distMeas=distEclud):
    m = shape(dataSet)[0] #数据集的行
    clusterAssment = mat(zeros((m, 2)))
    centroids = initCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m): #遍历数据集中的每一行数据
            minDist = inf
            minIndex = -1
            for j in range(k): #寻找最近质心
                distJI = distMeas(centroids[j, :], dataSet[i, :])
                if distJI < minDist: #更新最小距离和质心下标
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
            clusterAssment[i, :] = minIndex, minDist**2 #记录最小距离质心下标，最小距离的平方
        for cent in range(k): #更新质心位置
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] #获得距离同一个质心最近的所有点的下标，即同一簇的坐标
            centroids[cent,:] = mean(ptsInClust, axis=0) #求同一簇的坐标平均值，axis=0表示按列求均值
 
    return centroids, clusterAssment
 
# 取数据的前两维特征作为该条数据的x , y 坐标，
def getXY(dataSet):
    import numpy as np
    m = shape(dataSet)[0]  # 数据集的行
    X = []
    Y = []
    for i in range(m):
        X.append(dataSet[i,0])
        Y.append(dataSet[i,1])
    return np.array(X), np.array(Y)
 
# 数据可视化
def showCluster(dataSet, k, clusterAssment, centroids):
    fig = plt.figure()
    plt.title("K-means")
    ax = fig.add_subplot(111)
    data = []
 
    for cent in range(k): #提取出每个簇的数据
        ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] #获得属于cent簇的数据
        data.append(ptsInClust)
 
    for cent, c, marker in zip( range(k), ['r', 'g', 'b', 'y'], ['^', 'o', '*', 's'] ): #画出数据点散点图
        X, Y = getXY(data[cent])
        ax.scatter(X, Y, s=80, c=c, marker=marker)
 
    centroidsX, centroidsY = getXY(centroids)
    ax.scatter(centroidsX, centroidsY, s=1000, c='black', marker='+', alpha=1)  # 画出质心点
    ax.set_xlabel('X Label')
    ax.set_ylabel('Y Label')
    plt.show()
 
if __name__ == "__main__":
    cluster_Num = 3
    data = loadDataSet("network.txt")
    centroids, clusterAssment = KMeans(data, cluster_Num)
    showCluster(data, cluster_Num, clusterAssment, centroids)