Detaillierte Erläuterung der Python-Implementierung des kMeans-Algorithmus

Clustering ist eine Art unbeaufsichtigtes Lernen. Das Einordnen ähnlicher Objekte in denselben Cluster ähnelt einer vollautomatischen Klassifizierung. Je ähnlicher die Objekte im Cluster sind, desto größer ist der Unterschied zwischen den Objekten in den Clustern Clustering-Effekt wird gut sein. In diesem Artikel wird hauptsächlich die Implementierung des kMeans-Algorithmus in Python ausführlich vorgestellt, der einen gewissen Referenzwert hat. Interessierte Freunde können darauf verweisen und hoffen, dass er allen helfen kann.

1. k-means-Clustering-Algorithmus

k-means-Clustering unterteilt die Daten in k Cluster, und jeder Cluster übergibt seinen Schwerpunkt, d. h Mittelpunkt des Clusters Beschreiben Sie den Mittelpunkt aller Punkte. Zuerst werden k Anfangspunkte zufällig als Schwerpunkte bestimmt und dann wird der Datensatz dem nächstgelegenen Cluster zugeordnet. Der Schwerpunkt jedes Clusters wird dann aktualisiert, um dem Durchschnitt aller Datensätze zu entsprechen. Teilen Sie den Datensatz dann ein zweites Mal, bis sich die Clustering-Ergebnisse nicht mehr ändern.

Der Pseudocode lautet

Erstellt zufällig k Clusterschwerpunkte
Wenn sich die Clusterzuordnung eines beliebigen Punkts ändert:
Für jeden Punkt im Datensatz Daten Punkte:
Für jeden Schwerpunkt:
Berechnen Sie den Abstand vom Datensatz zum Schwerpunkt.
Ordnen Sie den Datensatz dem Cluster zu, der dem nächstgelegenen Schwerpunkt entspricht.
Berechnen Sie für jeden Cluster den Mittelwert aller Punkte im Cluster Und verwenden Sie den Mittelwert als Schwerpunkt

Python-Implementierung

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(&#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. Halbierungs-k-Mittelwert-Algorithmus

Der K-Mittelwert-Algorithmus kann eher zu einem lokalen Minimum als zu einem globalen Minimum konvergieren. Eine Metrik zur Messung der Clustering-Effektivität ist die Summe der quadratischen Fehler (SSE). Da das Quadrat eingenommen wird, wird mehr Wert auf den Punkt im Zentrum des Prinzips gelegt. Um das Problem zu überwinden, dass der k-means-Algorithmus zu einem lokalen Minimum konvergieren kann, hat jemand den Bisection-k-means-Algorithmus vorgeschlagen.
Behandeln Sie zunächst alle Punkte als Cluster, teilen Sie dann den Cluster in zwei Teile und wählen Sie dann unter allen Clustern den Cluster aus, dessen Teilung den SSE-Wert am stärksten reduzieren kann, bis die angegebene Anzahl von Clustern erreicht ist.

Pseudocode

Betrachten Sie alle Punkte als Cluster
Berechnen Sie SSE
while Wenn die Anzahl der Cluster kleiner als k ist:
für jeden Cluster :
Berechnen Sie den Gesamtfehler.
Führen Sie k-means-Clustering (k=2) für den gegebenen Cluster durch.
Berechnen Sie den Gesamtfehler der Teilung des Clusters in zwei.
Wählen Sie den Cluster aus, der den Fehler minimiert. Führen Sie die Teilung durch Betrieb

Python-Implementierung

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(&#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)

Code- und Datensatz-Download: K-means

Verwandte Empfehlungen:

Lassen Sie die Mahout KMeans-Clustering-Analyse auf Hadoop ausführen

cvKMeans2 Mean-Clustering-Analyse + Code-Analyse + Graustufen-Farbbild Clustering

Beispiel für eine detaillierte Erklärung des einfachen Erfassens von Webseitenbildern in Python

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Python-Implementierung des kMeans-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!