K-均值算法（一）

用户6021899

发布于 2019-08-14 17:16:11

1.1K0

发布于 2019-08-14 17:16:11

聚类（Cluster) 是一种无监督学习，它将相似度的对象归到同一个簇中。聚类方法几乎可以应用于所有对象，簇内的对象越相似，说明聚类的效果越好。本篇介绍一种最常用的聚类算法，即K-均值（K-means）聚类算法。

K-means 算法的伪代码表示如下：

创建K个点作为起始质心（经常是随机选择）
对数据集中的每个数据点
        对每个质心
                计算数据点到质心的距离
        将数据点重新分配到距其最近的簇
对每个簇，计算所有点的均值，并作为新的质心

上面提到的“最近”的说法，意味着要进行某种距离计算。如果是标称型特征，就必须先转化为数值型数据。我们可以按需选择任意的距离度量方法。最后我们可以用所有簇的全部点到各自簇质心的距离之和的变化趋势来判断是否收敛。

代码如下：

import numpy as np
import matplotlib.pyplot as plt
#from numpy.random import ranf

# Fixing random state for reproducibility
np.random.seed(2019071)
def centerPoint(group):
    n = group.shape[0]
    if n!= 0:
        sum_ = np.sum(group,axis=0)
        return sum_/n
    else:
        return None
def generateData(N=5000):
   
    N1=int(np.random.randint(N,size=1,))
    mu, sigma = 1.5, 0.2
    x1 = mu + sigma * np.random.randn(N1)
    mu, sigma = 1.6, 0.08
    y1 = mu + sigma * np.random.randn(N1)
    N2 = N-N1
    mu, sigma = 1.3, 0.15
    x2 = mu + sigma * np.random.randn(N2)
    mu, sigma = 2.3, 0.14
    y2 = mu + sigma * np.random.randn(N2)
    data=np.concatenate((list(zip(x1,y1)),list(zip(x2,y2))),axis= 0)
    return data

def classfy(data, seeds):
    K = len(seeds)
    groups = [[] for i in range(K)]
    N = len(data)
    for i in range(N):
        point = data[i]
       
        distance_min = np.linalg.norm(point-seeds[0])
        index_min = 0
        for j in range(1,K):
            distance = np.linalg.norm(point-seeds[j])
            if distance <  distance_min:
                distance_min = distance
                index_min = j
               
        groups[index_min].append(point)
    for j in range(0,K):
        groups[j] = np.array(groups[j])
    return groups
    
def distanceSum(groups, seeds):
    s= 0
    for i in range(len(groups)):
        if groups[i].shape[0] ==0 or seeds[i] is None:
            continue
        s += np.sum(np.linalg.norm(groups[i] -seeds[i]))
    return s
    
    
data = generateData(N=5000)
print( "data.shape: ", data.shape)
print(data)
seed0 = [1.8,2.8]#
seed1 = [1.5,1.5]
seed2 = [1.2, 2.0]
seeds = [seed0,seed1,seed2]
#seeds = [seed0,seed1]
distanceSum_log =[] #用于查看收敛与否
colors = ['g', 'b', 'orange', 'cyan','yellow','magenta']
#n 次迭代
n=5
for i  in range(n):
    # center point
    for j in range( len(seeds)):
        if seeds[j] is not None:
            plt.scatter(seeds[j][0], seeds[j][1], s=35,c="red",alpha=1, zorder =2)
   
    groups =classfy(data,seeds)#分类
   
    distanceSum_log.append(distanceSum(groups, seeds))
    for j in range( len(seeds)):                 
        seeds[j] =  centerPoint(groups[j])
        if groups[j].shape[0] ==0 :
            continue
        #plt.scatter(groups[j][:,0],groups[j][:,1],s=5,c=(ranf(),ranf(),ranf()),alpha=1)
        plt.scatter(groups[j][:,0],groups[j][:,1],s=5,c=colors[j],alpha=1)
       
    plt.title("K 均值算法  第 %d 次迭代" % i)
    plt.xlabel("X1")
    plt.ylabel("X2")
    plt.show()
plt.plot(range(1,n+1),distanceSum_log)
plt.scatter(range(1,n+1),distanceSum_log)
plt.title("到各中心点距离之和")
plt.xlabel("迭代次数")
plt.show()