집 >백엔드 개발 >파이썬 튜토리얼 >kMeans 알고리즘의 Python 구현에 대한 자세한 설명

kMeans 알고리즘의 Python 구현에 대한 자세한 설명

小云云원래의: 2017-12-22 09:03:198582검색

클러스터링은 유사한 객체를 동일한 클러스터에 배치하는 일종의 비지도 학습으로, 클러스터 내의 객체가 유사할수록 클러스터 내 객체 간의 차이가 클수록 더 좋습니다. 클러스터링 효과. 이 기사에서는 주로 Python에서 kMeans 알고리즘의 구현을 자세히 소개합니다. 이는 특정 참조 가치가 있으며 관심 있는 친구가 이를 참조하고 모든 사람에게 도움이 되기를 바랍니다.

1. k-평균 클러스터링 알고리즘

k-평균 클러스터링은 데이터를 k개의 클러스터로 나누고, 각 클러스터는 클러스터의 모든 지점의 중심인 중심으로 설명됩니다. 먼저 k개의 초기점을 중심으로 무작위로 결정한 후 가장 가까운 클러스터에 데이터 세트를 할당합니다. 그러면 각 클러스터의 중심이 업데이트되어 모든 데이터 세트의 평균이 됩니다. 그런 다음 클러스터링 결과가 더 이상 변경되지 않을 때까지 데이터 세트를 두 번째로 나눕니다.

의사 코드는 다음과 같습니다.

k개의 클러스터 중심을 무작위로 생성합니다.
어떤 포인트의 클러스터 할당이 변경될 때:
데이터 세트의 각 데이터 포인트에 대해:
각 중심에 대해:
데이터 세트에서 클러스터 중심까지의 거리를 계산합니다. centroid 数据에 따라 가장 가까운 거리의 클러스터에 해당하는 각 클러스터에 데이터 세트를 할당하고 계산 클러스터의 모든 포인트의 평균값과 평균값을 품질 하트로

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(&#39;\t&#39;)
   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(&#39;testSet.txt&#39;)
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, 2점 K. 평균 알고리즘

K-평균 알고리즘은 전역 최소값이 아닌 로컬 최소값으로 수렴할 수 있습니다. 클러스터링 효율성을 측정하는 데 사용되는 측정항목 중 하나는 SSE(제곱 오류 합계)입니다. 사각형을 취하기 때문에 원리의 중심에 있는 점을 더욱 강조하게 된다. k-평균 알고리즘이 국소 최소값으로 수렴할 수 있는 문제를 극복하기 위해 누군가 이등분 k-평균 알고리즘을 제안했습니다.

먼저 모든 포인트를 클러스터로 처리한 후 클러스터를 두 개로 나누고, 지정된 클러스터 수를 충족할 때까지 SSE 값을 최소화할 수 있는 모든 클러스터 중에서 클러스터를 선택합니다.

의사 코드

모든 포인트를 하나의 클러스터로 처리

SSE 계산 while 클러스터 수가 k보다 작을 때:
각 클러스터에 대해:
총 오류 계산
주어진 클러스터에서 k-평균 클러스터링 수행( k=2)
클러스터를 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(&#39;\t&#39;)
   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(&#39;the best cent to split is &#39;,bestCentToSplit)
#  print(&#39;the len of the bestClust&#39;)
  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(&#39;testSet2.txt&#39;)
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-

kMeans 알고리즘의 Python 구현에 대한 자세한 설명

관련 기사