ホームページ >バックエンド開発 >Python チュートリアル >kMeansアルゴリズムのPython実装の詳細な説明

kMeansアルゴリズムのPython実装の詳細な説明

小云云
小云云オリジナル
2017-12-22 09:03:198548ブラウズ

クラスタリングは一種の教師なし学習であり、類似したオブジェクトを同じクラスターに入れます。これは、クラスター内のオブジェクトが類似しているほど、クラスター内のオブジェクト間の差異が大きいほど、より適切な分類に似ています。クラスタリング効果。この記事では主に Python での kMeans アルゴリズムの実装について詳しく紹介します。興味のある方は参考にしていただければ幸いです。

1. k 平均法クラスタリング アルゴリズム

k 平均法クラスタリングは、データを k 個のクラスターに分割し、各クラスターはクラスター内のすべての点の中心である重心によって記述されます。まず、k 個の初期点が重心としてランダムに決定され、データセットが最も近いクラスターに割り当てられます。次に、各クラスターの重心がすべてのデータ セットの平均になるように更新されます。次に、クラスタリングの結果が変化しなくなるまで、データ セットを 2 回分割します。

疑似コードは、

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('\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)
e

2、2 点 K 平均アルゴリズム


K 平均アルゴリズムは、大域最小値ではなく局所最小値に収束する可能性があります。クラスタリングの有効性を測定するために使用されるメトリックの 1 つは、誤差二乗和 (SSE) です。正方形をとるため、原理の中心の点がより強調されます。 K 平均法アルゴリズムが極小値に収束する可能性があるという問題を克服するために、誰かが二分 K 平均法アルゴリズムを提案しました。

まず、すべての点をクラスターとして扱い、次にクラスターを 2 つに分割し、指定されたクラスター数が満たされるまで、すべてのクラスターの中から SSE 値を最小化できるクラスターを選択します。



疑似コード

すべてのポイントを 1 つのクラスターとして処理します

SSE を計算します クラスターの数が k 未満の場合:
各クラスターについて:
合計誤差を計算します
指定されたクラスターに対して k-means クラスタリングを実行します ( 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-意味

関連する推奨事項:


Mahout KMeans クラスター分析を Hadoop 上で実行する

cvKMeans2 平均クラスター分析 + コード分析 + グレースケール カラー画像クラスタリング

シンプルな Web ページ画像キャプチャの Python 実装の詳細な説明例

を取る

以上がkMeansアルゴリズムのPython実装の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。