機械学習アルゴリズム-k-means Clustering K平均クラスタリング

k-means ClusteringすなわちK平均クラスタリングアルゴリズムは,広く用いられているクラスタリングアルゴリズムである.
関連定義
クラスタリング
クラスタリングとは、オブジェクトを複数のグループまたはクラスタに分割して、同じグループのオブジェクト間で比較的類似し、異なるグループのオブジェクト間で大きな差があるようにすることです.
クラスタリング中にクラスタリング対象オブジェクトとの関連情報が入力されないため、クラスタリングは通常、監視学習なしと見なされる.
k−meansアルゴリズムは単純なクラスタリングアルゴリズムであり,主に反復によってデータセットを分類する.
アルゴリズムの説明
数学の説明
アルゴリズムの入力オブジェクトは、d次元ベクトル空間のいくつかの点、すなわち、集合D={xi|i=1,2,3,...,n}をクラスタリングし、xi∈Rdがi番目のデータ点を表すと見なすことができる.k-meansクラスタリングはD中のすべてのデータ点を処理し,クラスタリング中心はC={Ki|i=1,2,...,k}と表すことができ,各データ点はxi∈S(Kj)と記すことができ,すなわちi番目のデータ点がクラスタリング中心Kjに属することを示す.
クラスタリングアルゴリズムでは、通常、各データポイントがどのクラスタリングセンターに属するかを判断する根拠を定義する必要がありますが、この根拠は通常、代価関数と呼ばれます.一般的に、クラスタリング関数は次のように選択されます.
Cost=Σki=1Σx∈S(Ki)∥x−μi∥2
内
μiはi番目のクラスタに属する
S(Ki)のオブジェクト点の平均値、すなわちクラスタリング中心
Ki .クラスタリングの目標は、この代価関数を最小化し、各データポイントを
xiと最近のクラスタリングセンター
Kjのユークリッド距離の二乗と最小.
アルゴリズムステップ
入力:データセットD、クラスタリング数k出力:クラスタリングセットC、クラスタリングメンバーベクトルm⃗

k個の点を開始コア

として作成する.

任意の点のクラスタ割り当て結果が変更された場合

データセットの各データ点に対して、各コアに対して、コアとデータ点との間の距離

を計算する.

は、最も近い距離にあるクラスタ

にデータポイントを割り当てる.

各クラスタについて、クラスタ内のすべての点の平均値を計算し、新しいクラスタ中心

として平均値を使用する

アルゴリズムで初期のクラスタリング中心をどのように見つけるか、どのように計算するか、メトリック関数の選択については、後述します.
プログラム
python
そうかんほじょかんすう

from numpy import *

def loadDataSet(filename) :
    dataMat = []
    fr = open(filename) :
    for line in fr.readlines() :
        curLine = line.strip().split('\t')
        fltLine = map(float, curLine)
        dataMat.append(fltLine)
    return dataMat

#Eclud Distance
def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2)))

#Initial Random Clustering Centroids    
def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,J]) - minJ)
        centroids[:,J] = minJ + rangeJ * random.rand(k,1)
    return centroids

これは2つの補助的な関数で、最初の関数は私たちが前に言ったよく使われているメトリックであるユークリッド距離を定義し、ヨーロッパ式距離と略称します.2番目の補助関数は、centroidsがクラスタリング中心であり、dataSetがデータセットであり、kがクラスタリング中心の数であり、ランダム化の方法は、データの最小値と最大値を見つけ、この2つの数の間にk個のランダムな値を生成することである.
K-meansアルゴリズム

def kMeans(dataSet, k, distMeas = distEclud, createCent = randCent) :
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m) :
            minDist = inf
            minIndex = -1
            for j in range(k) :
                distJI = distMeas(centroids[j,:],dataSet[i,:])
                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[nonzero(clusterAssment[:,0].A == cent)[0]]
            centroids[cent,:] = mean(ptsInClust, axis = 0)

    return centroids, clusterAssment

この部分アルゴリズムでは、上記の説明に従って、クラスタリング中心を初期化し、各ターゲットポイントに最も近いクラスタリング中心を探し、クラスタリング中心の位置を更新し、クラスタリング中心が収束した場合にのみアルゴリズムを停止する3つの部分が含まれている.個人的には、ここでは一定の回数を反復するときに停止アルゴリズムを簡単に加えるべきだと思います.
アルゴリズムは、1つのm行、2列の1つのマトリクスclusterAssumentを初期化し、このマトリクスの各行は1つのターゲットポイントに対応し、各行の最初の位置はクラスタリング中心を記録し、2番目の位置はこのターゲットポイントからクラスタリング中心までの距離の平方を記録した.クラスタリング中心が変化するか否かを判断する際,プログラムの判断根拠は新しい距離とclusterAssumentに格納されている距離の対比である.
プログラムの最後の部分は、各クラスタリングセンターに対応するターゲットポイントの平均値を計算することによって、クラスタリングセンターを再計算することである.
アルゴリズムの限界
きょくぶさいてきかい
k‐meansアルゴリズムは本質的に非凸関数の貪欲な降下解アルゴリズムに属するので,理論的には最後に得られた収束解は局所最適解であり,グローバル最適解ではない.また、最終的にグローバル最適解を得ることができるかどうかは、初期のクラスタリング中心の位置にもある程度関係しており、同じデータセットに対して、最初に選択したクラスタリング中心が異なると、最終的にクラスタリングされた結果が異なる可能性がある.
従って,この問題を解決する上で,主に初期化されたクラスタリング中心を合理的に選択し,アルゴリズム上で最適化することによって局所最適解の出現を防止する.
Kの選択
実際には,データセットの分布について先験的な理解が欠けているため,予め知ることができない可能性がある.