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

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

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


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

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

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

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

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


算法执行流程

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