K-means聚类(一）

聚类：

聚类（clustering）是一种无监督学习（也就是说没有label,因为我们的目标就是为了生成label.）,它将相似的样本归类成同一簇,而将不相似的样本归类到其它簇中。 簇识别（cluster indentify）是为了发现有那些簇，同时各种簇里面到底有什么。

K-means是一种聚类方法，K的含义是可以生成K个簇（K个类别），而每个类别会有一个中心（centro）,这个簇中心是根据簇内元素的均值（mean）定义的。K-means是基于簇中心的聚类方法.

---

使用K-means

需要确定：
1. 确定相似度算法
2. 确定收敛条件
3. 确定簇中心更新方法

生成实验数据

我们先随机生成3组数据，这三组数据分别是以(0,0) (4,4) (8,8)为均值，1为方差的的二维正态分布点。每组20个点。
效果如图：

生成代码：

def genData():
    center=[[0,0],[4,4],[8,8]]
    data=list()
    for i in range(len(center)):
        n=20
        da=list()
        print(i)
        while len(da)<n:
            x,y=np.random.normal(center[i],1)
            if(((x-center[i][0])**2+(y-center[i][1])**2)<2):
                da.append([x,y])
                data.append([x,y])
    return  data

K-means基础版本

1. 相似度算法：欧几里德距离
   
   其中X,Y都是行向量
   Dist越大 越不相似
2. 收敛条件：所有样本都归类到里自己最近的族中心所在的簇中
3. 簇中心更新方法：簇内所有样本各个维度的均值

算法：
    基本流程：
    创建初始的随机k个簇中心（注意这k个中心必须不同）
    当仍然有样本更改自己所属的簇时：
        对于每个样本
            寻找该样本最近的簇中心，并把这个样本归类到这个簇
        更新各个簇中心
    输出簇中心，各样本所属的簇id及相似度.

代码：

class simplekmean:
    '''
    dataset: each row vector is an example.
    '''
    def randc(dataset,k):
        n=np.shape(dataset)[1]
        centro=np.zeros(shape=[k,n],dtype=np.float32)
        for i in range(n):
            _min=np.min(dataset[:,i])
            _max=np.max(dataset[:,i])
            alpha=np.random.rand(k,1)
            new=alpha*_min+(1-alpha)*_max
            centro[:,i]=np.reshape(new,newshape=[k,])
        return centro
    def Eudict(x,y):
        diff= x-y

        rst=diff*np.transpose(diff)
        #print("#"*5+"Eudict")
        #print({'x':x,'y':y,'diff':diff,"rst":rst})
        #print("#"*10+"Eudict")
        if(rst[0][0]==np.nan):
            print(rst)
        return  rst
    def simpleKmeans(dataset,k,randcentor=None,dist=None):
        if(randcentor==None):
            randcentor=simplekmean.randc
        if(dist==None):
            dist=simplekmean.Eudict
        centers=randcentor(dataset,k)
        sample_changed=True
        n =np.shape(dataset)[0]
        clusterReg=np.random.rand(n,2)
        while sample_changed:
            sample_changed =False
            for i in range(n):
                lowestdist=np.inf
                minID=-1
                for j in range(k):
                    #print(j)
                    #print(centers[j])
                    #print(dataset[i])
                    curdist=dist(dataset[i],centers[j])
                    #print(curdist,lowestdist)
                    if(curdist<lowestdist):
                        lowestdist=curdist
                        minID=j
                if(minID!=clusterReg[i][0]):
                    sample_changed=True
                    clusterReg[i][0]=minID
                    clusterReg[i][1]=lowestdist
            nonosampleID=-1
            if(sample_changed):
                for i in range(k):
                    index=np.nonzero(clusterReg[:,0]==i)
                    #print(index)
                    if(np.shape(index)[1]==0):
                        nonosampleID=i
                        continue
#注意这段判断index是否为空很重要，如果index是空的那么接下来center[i]的计算就会出错。

                    subset=dataset[index]
                    centers[i]=np.mean(subset,0)
        return centers,clusterReg

simpleKmeans(dataset,k,randcenter,dist)是基础版本
randcenter 参数用于指定随机中心的生成方法

dist用于指定两个向量之间的距离或相似度

默认randcenter指向randc,dist指向Ecudict.

函数返回k个中心，以及各个样本所属的簇ID和距离簇中心的距离

clusterReg是一个nx2的矩阵.clusterReg[i][0]表示第i个所属的簇ID,clusterReg[i][1]表示第i个样本距离其簇中心的距离。

保存成Kmean.py，我们看看效果：
测试脚本：

from Kmean import  *
import  random
import  numpy as np
import pylab as pl
def genData():
    center=[[0,0],[4,4],[8,8]]
    data=list()
    for i in range(len(center)):
        n=20
        da=list()
        print(i)
        while len(da)<n:
            x,y=np.random.normal(center[i],1)
            if(((x-center[i][0])**2+(y-center[i][1])**2)<2):
                da.append([x,y])
                data.append([x,y])
    return  data
oridata=genData()
data=np.mat(oridata)
pl.plot(data[:,0],data[:,1],'o')
pl.show()
print("*"*10)
center,cluster=simplekmean.simpleKmeans(data,3)
print(center)
print("#"*30)
for i in range(len(cluster)):
    x=oridata[i][0]
    y=oridata[i][1]
    if(cluster[i][0]==0):
        pl.plot(x,y,'+b')
    if(cluster[i][0]==1):
        pl.plot(x,y,'*b')
    if(cluster[i][0]==2):
        pl.plot(x,y,'sb')
pl.plot(center[0,0],center[0,1],'r+')
pl.plot(center[1,0],center[1,1],'r*')
pl.plot(center[2,0],center[2,1],'rs')
pl.show()

聚类的中心为：

[[ 8.08795738  7.93696928]
 [ 0.09250244 -0.01405806]
 [ 3.84930944  4.08832884]]

约为[8,8],[0,0],[4,4]效果还是不错的。
图表显示：
第一类样本显示为”+”
第二类样本显示为‘*’
第三类样本显示为方块
所有样本显示为蓝色，而簇中心显示为红色。
结果：

还是不错的哈。
但是如果我们多运行几次 会发现偶尔会有这样的结果：

会发现 很明显有一个中心给异常了。这是为什么呢？

我们看我们的randc的逻辑：

def randc(dataset,k):
        n=np.shape(dataset)[1]
        centro=np.zeros(shape=[k,n],dtype=np.float32)
        for i in range(n):
            _min=np.min(dataset[:,i])
            _max=np.max(dataset[:,i])
            alpha=np.random.rand(k,1)
            new=alpha*_min+(1-alpha)*_max
            centro[:,i]=np.reshape(new,newshape=[k,])
        return centro

生成的中心的各个维度是各个维度的[min,max]区间内的一个随机数。

3个中心是随机化的。有可能在第一次迭代的时候，所有的点全部分配到其中的一个中心或两个中心，这样，剩下的那些中心都不再有机会参与修正了。

例如上图的结果，一种可能的过程就是：生成中心的时候就簇0的中心靠近【0,0】，【4,4】周围的点，而簇2中心靠近【8,8】。

簇1特别悲催 分配到了边边角角上。于是：第一次迭代的时候，[0,0],[4,4]就分配给簇0，而[8,8]又分配给了2，所以直接导致簇1根本就没有参与到修正中来。

解决方法：

判断有没有那个簇一个样本都没有包含的，如果有的话，把这个簇给撤销掉。然后找到其它簇中簇内样本距离之和最大的那个簇，对这个簇的所有样本所组成一个子集Subset 进行k=2的聚类。把Subset集合上的k=2聚类结果合并到原来的聚类结果中。

代码：

def simpleKmeans(dataset,k,randcentor=None,dist=None):
    if(randcentor==None):
        randcentor=simplekmean.randc
    if(dist==None):
        dist=simplekmean.Eudict
    centers=randcentor(dataset,k)
    sample_changed=True
    n =np.shape(dataset)[0]
    clusterReg=np.random.rand(n,2)
    while sample_changed:
        sample_changed =False
        for i in range(n):
            lowestdist=np.inf
            minID=-1
            for j in range(k):
                #print(j)
                #print(centers[j])
                #print(dataset[i])
                curdist=dist(dataset[i],centers[j])
                #print(curdist,lowestdist)
                if(curdist<lowestdist):
                    lowestdist=curdist
                    minID=j
            if(minID!=clusterReg[i][0]):
                sample_changed=True
                clusterReg[i][0]=minID
                clusterReg[i][1]=lowestdist
        nonosampleID=-1
        if(sample_changed):
            for i in range(k):
                index=np.nonzero(clusterReg[:,0]==i)
                #print(index)
                if(np.shape(index)[1]==0):
                    nonosampleID=i
                    continue
                subset=dataset[index]
                centers[i]=np.mean(subset,0)
        if(nonosampleID!=-1):
            print("internal cluster")
            maxDist=-np.inf
            id=-1
            for i in range(k):
                if i==nonosampleID:
                    continue
                dis=np.sum(clusterReg[np.nonzero(i==clusterReg[:,0]),1])
                if (dis>maxDist) :
                    maxDist=dis
                    id=i
            bicenter,bicluster=simplekmean.simpleKmeans(dataset[np.nonzero(id==clusterReg[:,0])],2)
            centers[nonosampleID]=bicenter[0]
            centers[id]=bicenter[1]
            clusterReg[np.nonzero(0==bicluster[:,0]),0]=nonosampleID
            clusterReg[np.nonzero(0==bicluster[:,0]),1]=bicluster[np.nonzero(0==bicluster[:,0]),1]
            clusterReg[np.nonzero(1==bicluster[:,0]),0]=id
           #以上在合并聚类结果 clusterReg[np.nonzero(1==bicluster[:,0]),1]=bicluster[np.nonzero(1==bicluster[:,0]),1]
    return centers,clusterReg

我们使用nonosampleID来记录那个簇没有任何样本的，任何进行相应的操作。注意，我们在处理这个情况的使用会打印：internal cluster来表示进行簇间修正。
我们看看效果：

输出：

internal cluster
internal cluster
[[ 7.98872566  7.97427654]
 [ 3.87677813  4.08358049]
 [-0.01632341 -0.05349483]]

进行了两次internal cluster的修正,效果不错的。

我们增加到5类点即增加[10,10],[4,7]周围的点各20个。

原样本分布图：

聚类结果：

但是多跑几组数据 发现有异常的情况：

聚类结果：

可以发现 这还是很有问题的，因为右上角那一坨居然被聚成了一类。这个就是其基础版本的局限性 会收敛于局部极小而不是全局最小。 这需要再进行修正和完善。

biKmeans 未完待续（(๑′ᴗ‵๑)）