PythonでkMeansアルゴリズムを実装

クラスタリングは無監督学習の一種であり、似ているオブジェクトを同じクラスタにまとめることができます。これは自動分類に似ており、クラスタ内のオブジェクトがより似ているほど、クラスタ間の差が大きくなるほど、クラスタリングの効果が良いとされます。

1、kメディアンクラスタリングアルゴリズム

kメディアンクラスタリングはデータをk個のクラスタに分類します。各クラスタはその質心、つまりクラスタ内のすべての点の中心で説明されます。まず、k個の初期点をランダムに決定し、データセットを最も近いクラスタに割り当てます。次に、各クラスタの質心をデータセットの平均として更新します。その後、データセットを再び分類し、クラスタリング結果が変化しなくなるまで繰り返します。

仮想コードは以下の通りです

ランダムに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.float)32)
 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）です。平方を取ることで、中心の原理の点をより重視します。Kメディアンクラスタリングが局所的最小値に収束する可能性を克服するために、二分Kメディアンクラスタリングが提案されました。
まずすべての点を一つのクラスタとして、そのクラスタを二つに分け、その後、SSEを最大限に減少させるクラスタを選択し、指定されたクラスタ数に達するまで繰り返します。

仮想コード

すべての点を一つのクラスタとして見なします
SSEを計算します
クラスタの数がk未満である場合に：
　　　 各クラスタごとに：
　　　　　　　 総エラーを計算します
　　　　　　　 指定されたクラスタでkメディアンクラスタリング(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.float)32)
 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

これで本文のすべてが終わりました。皆様の学習に役立つことを願っています。また、呐喊ガイドを多くの皆様に支持していただけると嬉しいです。

声明：本文の内容はインターネットから収集され、著作権者に帰属します。インターネットユーザーにより自発的に提供された内容であり、本サイトは所有権を有しない、また人工編集は行われていません。著作権侵害が疑われる内容がある場合は、メールを送信して：notice#oldtoolbag.com（メールを送信する際、#を@に置き換えてください。報告を行い、関連する証拠を提供してください。一旦確認がとれましたら、本サイトは即座に侵害疑いのコンテンツを削除します。）