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('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. 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('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)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!
