无监督学习-使用后处理来提高聚类性能

Poblog 07月04日 2017


一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和)

一种方法是将具有最大SSE值的簇划分成两个簇,将最大簇包含的点过滤出来并在这些点上运行K-均值算法,其中的k设为2


为了保持簇总数不变,可以将某两个簇进行合并

有两种可以量化的办法:合并最近的质心,或者合并两个使得SSE增幅最小的质心

二分 K-均值算法(为克服K-均值算法收敛于局部最小值的问题)

首先将所有点作为一个簇,然后将该簇一分为二

之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值上述
基于SSE的划分过程不断重复,直到得到用户指定的簇数目为止


算法执行流程


dat2=loadDataSet('testSet2.txt')
datMat2=np.mat(dat2);

centroids,clusterAssment=biKmeans(datMat2,3);

//
centroids:中心点
[[ 2.93386365  3.12782785]
 [-2.94737575  3.3263781 ]
 [-0.45965615 -2.7782156 ]]
clusterAssment:划分关系
[[0.00000000e+00 1.45461050e-01]
 ...
 [2.00000000e+00 1.61040000e+00]]
//



#二分K-均值聚类
def biKmeans(dataSet,k,distMeas=distEclud):
      
// dataSet:需要聚类的点
[[ 3.275154  2.957587]
 [-3.344465  2.603513]
 ...
 [ 0.639276 -3.41284 ]]

 k:需要聚类的个数
 3
 //

    m=np.shape(dataSet)[0]
    
//m:需要聚类的数据点个数
      60//

    clusterAssment=np.mat(np.zeros((m,2)))
   
 //clusterAssment:存放聚点和误差距离的矩阵
         [[0. 0.]
 ...
 [0. 0.]
 [0. 0.]]//

    centroid0 = np.mean(dataSet, axis=0).tolist()[0]
    
//centroid0:中心点
     [-0.15772275000000002, 1.2253301166666664]
    //

    centList = [centroid0]  # create a list with one centroid
    
//centList:中心点的list集合
    [[-0.15772275000000002, 1.2253301166666664]]
    //

    for j in range(m):  # calc initial Error for each point
    
//j:循环每个点
      0
    //

     clusterAssment[j, 1] = distMeas(np.mat(centroid0), dataSet[j, :]) ** 2
     
//clusterAssment:依次更新全部点聚点和到误差距离
     [[ 0.         14.78535669]
     [ 0.          0.        ]
     ....
     [ 0.          0.        ]]
     //

    while (len(centList) < k):
      
//未找到全部聚点前//
  
        lowestSSE = np.inf #init SSE
//lowestSSE:记录最大的sse值
inf//

        for i in range(len(centList)):#for every centroid
//i:循环每个现有的中心点
  0
//

            ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:, 0].A == i)[0],:]  # get the data points currently in cluster i
    
//ptsInCurrCluster:记录中心点为当前点的全部数据点
      [[ 3.275154  2.957587]
       ...
      [ 0.639276 -3.41284 ]]
    //

            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)# k=2,kMeans
    
//重新聚类
      centroidMat:新的中心点
       [[-0.45965615 -2.7782156 ]
[-0.00675605  3.22710297]]
      splitClustAss:各点的中心点和误差大小
              [[1.00000000e+00 1.08435724e+01]
 [1.00000000e+00 1.15291655e+01]
 [0.00000000e+00 1.02184582e+00]
 ....
 [0.00000000e+00 1.61040000e+00]]
    //

            sseSplit = sum(splitClustAss[:, 1])  # compare the SSE to the currrent minimum
    
//sseSplit:以本中心点得到新的聚类的误差和大小
      453.03348958
    //

            sseNotSplit = sum(clusterAssment[np.nonzero(clusterAssment[:, 0].A != i)[0], 1])
    
//sseNotSplit:没有划分前不以本中心点为中心的点的误差和大小
      0//

            print("sseSplit, and notSplit: ", sseSplit, sseNotSplit)
            if (sseSplit + sseNotSplit) < lowestSSE: #judge the error
    
//若误差和减小则记录可以建议以该点的划分为新的划分
      当然若其他点的划分比这个还好则用其他点划分
    //

                bestCentToSplit = i
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit
        #new cluster and split cluster
//循环完毕得到
bestCentToSplit:最好的划分中心
        bestNewCents:以最好的划分中心得到的新的中心点
bestClustAss:以最好的划分中心得到的点集的关系
//

        bestClustAss[np.nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)  # change 1 to 3,4, or whatever
//因为是2分划分,所以需要将新划分得到的bestClustAss的中心点序号更新一下
//

        bestClustAss[np.nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit
//因为是2分划分,所以需要将新划分得到的bestClustAss的中心点序号更新一下(以前的中心也变了)
//

        print('the bestCentToSplit is: ', bestCentToSplit)
        print('the len of bestClustAss is: ', len(bestClustAss))
        centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]  # replace a centroid with two best centroids
        centList.append(bestNewCents[1, :].tolist()[0])
//上面的两步将旧的一个中心点替换成两个新的中心点//

        clusterAssment[np.nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0],:] = bestClustAss  # reassign new clusters, and SSE
//替换旧的点集对应的中心点以及误差和

    return np.mat(centList), clusterAssment