Python实现K-Means与二分K-Means聚类算法详解
本文详细解析了Python中K-Means聚类算法及其改进版二分K-Means的实现原理。通过伪代码与完整Python代码示例，展示了如何初始化质心、计算距离、更新簇中心及评估聚类效果（SSE）。重点阐述了二分K-Means如何通过迭代分裂簇来克服局部最小值问题，适用于需要更高聚类精度的场景。
聚类属于无监督学习范畴，其核心目标是将相似的数据对象归入同一簇，这类似于自动化的分类过程。理想的聚类效果表现为簇内对象高度相似，而不同簇之间的对象差异显著。
1、K均值聚类算法
K均值聚类旨在将数据集划分为k个簇，每个簇由质心（即簇内所有数据点的中心位置）来表征。算法流程如下：首先随机选取k个初始点作为初始质心；接着，将数据集中的每个点分配给距离最近的质心所对应的簇；随后，根据当前簇内所有数据点的平均值更新该簇的质心位置。重复执行数据划分与质心更新步骤，直至聚类结果不再发生变化，即达到收敛状态。
其伪代码逻辑如下：
1. 随机创建k个簇的初始质心。 2. 当任意一个数据点的簇分配发生变动时，执行以下循环： - 遍历数据集中的每一个数据点： - 遍历每一个质心： - 计算该数据点到当前质心的距离。 - 将该数据点分配给距离最近的质心所对应的簇。 - 对每一个簇，计算其中所有数据点的均值，并将该均值更新为新的质心。
以下是使用Python语言的具体实现代码：
import numpy as np
import matplotlib.pyplot as plt
def loadDataSet(fileName):
dataMat = []
with open(fileName) as f:
for line in f.readlines():
line = line.strip().split('\t')
dataMat.append(line)
dataMat = np.array(dataMat).astype(np.float32)
return dataMat
def distEclud(vecA,vecB):
return np.sqrt(np.sum(np.power((vecA-vecB),2)))
def randCent(dataSet,k):
m = np.shape(dataSet)[1]
center = np.mat(np.ones((k,m)))
for i in range(m):
centmin = min(dataSet[:,i])
centmax = max(dataSet[:,i])
center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1)
return center
def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
m = np.shape(dataSet)[0]
clusterAssment = np.mat(np.zeros((m,2)))
centroids = createCent(dataSet,k)
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m):
minDist = np.inf
minIndex = -1
for j in range(k):
distJI = distMeans(dataSet[i,:],centroids[j,:])
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[np.nonzero(clusterAssment[:,0].A == cent)[0]]
centroids[cent,:] = np.mean(ptsInClust,axis = 0)
return centroids,clusterAssment
data = loadDataSet('testSet.txt')
muCentroids, clusterAssing = kMeans(data,4)
fig = plt.figure(0)
ax = fig.add_subplot(111)
ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A)
plt.show()
print(clusterAssing)
2、二分K均值算法
标准K均值算法存在收敛至局部最小值而非全局最小值的潜在风险。为了量化聚类效果，通常采用误差平方和（SSE）作为指标。由于采用了平方运算，SSE对远离中心点的异常值更为敏感。为了解决K均值可能陷入局部最优的问题，研究者提出了二分K均值算法。该算法首先将所有数据点视为一个初始簇，然后将其一分为二。在每一步分裂中，算法会选择那些能够最大程度降低整体SSE值的簇进行分裂，直到满足预设的簇数量k为止。
二分K均值算法的伪代码描述如下：
1. 将所有数据点初始化为一个簇。 2. 计算当前的总误差平方和（SSE）。 3. 当当前簇的数量小于目标簇数k时，执行循环： - 遍历每一个现有簇： - 计算该簇的总误差。 - 对该簇执行K均值聚类（设定k=2），将其一分为二。 - 计算分裂后的总误差。 - 选择使得总误差最小的那个簇进行实际的划分操作。
二分K均值算法的Python实现代码如下：
import numpy as np
import matplotlib.pyplot as plt
def loadDataSet(fileName):
dataMat = []
with open(fileName) as f:
for line in f.readlines():
line = line.strip().split('\t')
dataMat.append(line)
dataMat = np.array(dataMat).astype(np.float32)
return dataMat
def distEclud(vecA,vecB):
return np.sqrt(np.sum(np.power((vecA-vecB),2)))
def randCent(dataSet,k):
m = np.shape(dataSet)[1]
center = np.mat(np.ones((k,m)))
for i in range(m):
centmin = min(dataSet[:,i])
centmax = max(dataSet[:,i])
center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1)
return center
def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent):
m = np.shape(dataSet)[0]
clusterAssment = np.mat(np.zeros((m,2)))
centroids = createCent(dataSet,k)
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m):
minDist = np.inf
minIndex = -1
for j in range(k):
distJI = distMeans(dataSet[i,:],centroids[j,:])
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[np.nonzero(clusterAssment[:,0].A == cent)[0]]
centroids[cent,:] = np.mean(ptsInClust,axis = 0)
return centroids,clusterAssment
def biKmeans(dataSet,k,distMeans = distEclud):
m = np.shape(dataSet)[0]
clusterAssment = np.mat(np.zeros((m,2)))
centroid0 = np.mean(dataSet,axis=0).tolist()
centList = [centroid0]
for j in range(m):
clusterAssment[j,1] = distMeans(dataSet[j,:],np.mat(centroid0))**2
while (len(centList)<k):
lowestSSE = np.inf
for i in range(len(centList)):
ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A == i)[0],:]
centroidMat,splitClustAss = kMeans(ptsInCurrCluster,2,distMeans)
sseSplit = np.sum(splitClustAss[:,1])
sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A != i)[0],1])
if (sseSplit + sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat.copy()
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
print('the best cent to split is ',bestCentToSplit)
# print('the len of the bestClust')
bestClustAss[np.nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)
bestClustAss[np.nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
clusterAssment[np.nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:] = bestClustAss.copy()
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]
centList.append(bestNewCents[1,:].tolist()[0])
return np.mat(centList),clusterAssment
data = loadDataSet('testSet2.txt')
muCentroids, clusterAssing = biKmeans(data,3)
fig = plt.figure(0)
ax = fig.add_subplot(111)
ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A,cmap=plt.cm.Paired)
ax.scatter(muCentroids[:,0],muCentroids[:,1])
plt.show()
print(clusterAssing)
print(muCentroids)
完整代码及测试数据集可下载：K-means
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
