機械学習アルゴリズムまとめ--K平均アルゴリズム

参照先:

『機械学習』

機械学習&データマイニングノート_16(よくある面接の機械学習アルゴリズム思想の簡単な整理)

K-Means Clustering

スタンフォード大学公開課:機械学習課程

概要
K−平均は最も普及しているクラスタリングアルゴリズムであり,アルゴリズムはタグ付けされていないデータセットを受け入れ,その後,データを異なるグループにクラスタリングする.
K平均値は反復アルゴリズムであり、データをn個のグループにクラスタリングしたいと仮定し、その方法は以下の通りである.

まずK個のランダムな点を選択し、これをクラスタリング中心

と呼ぶ.

は、データセットの各データについて、K個の中心点からの距離に従って、最も近い中心点に関連付けられ、同一の中心点に関連付けられたすべての点が1つのクラス

に集約する.

各グループの平均値を算出する、そのグループに関連付けられた中心点を平均値の位置

に移動する.

は、中心点が

に変化しないまで、ステップ2-3を繰り返す.
このプロセスでは、2つの主要なステップに分けられます.1つ目は、訓練セットのサンプルポイントをクラスタ中心からの距離に基づいて、最も近いクラスタ中心に割り当て、2つ目は、各クラスのすべてのサンプルの平均値を計算し、この平均値を新しいクラスタ中心値として更新する3つ目のステップです.次に、終了条件に達するまで、この2つのステップを続け、一般には設定された反復回数に達することを意味する.
もちろん、この過程でクラスタリングセンターがデータポイントを割り当てていない場合があります.通常、クラスタリングセンターを削除したり、クラスタリングセンターを再選択したりして、クラスタリングセンターの数を保証したり、初期設定のK個を保証したりします.
目標の最適化
K平均最小化問題は、すべてのデータ点とそれに関連するクラスタリング中心との間の距離の和を最小化することであり、したがって、K平均値の対価関数(歪み関数とも呼ばれる)は、
J(c(1),c(2),…,c(m),μ1,μ2,…,μm)=1m∑mi=1||x(i)−μc(i)||2
内
μc(i)代表と
x(i)最近のクラスタリング中心点.
従って,我々の最適化目標は,代価関数の最小和c(1),c(2),...,c(m)およびμ1,μ2,…,μm : 
minc(1),c(2),…,c(m),μ1,μ2,…,μmJ(c(1),c(2),…,c(m),μ1,μ2,…,μm)
K平均反復アルゴリズムを振り返ると,最初のサイクルは減少に用いることが分かった.
c(i)による代価であり、第2のサイクルは減少するために用いられる
μiによる代価
反復のプロセスは、反復のたびに代価関数を減らしているに違いありません.そうしないと、エラーが発生します.
ランダム初期化
K平均アルゴリズムを実行する前に、まずすべてのクラスタリング中心点をランダムに初期化する必要があります.

は、まずKよりも小さい.

K個の訓練例をランダムに選択し、K個のクラスタリング中心をそれぞれこのK個の訓練例に等しくする

.
K平均値の問題は、初期化の状況に応じて、局所最小値にとどまる可能性があることである.
この問題を解決するためには、通常、K平均アルゴリズムを複数回実行し、毎回ランダム初期化を再開し、最後にK平均を複数回実行した結果を比較し、代価関数の最小結果を選択する必要がある.この方法はKが小さい(2−10)場合でも可能であるが,Kが大きい場合,この方法は著しく改善されない可能性がある.
メリットとデメリット
メリット

k-meansアルゴリズムはクラスタリング問題を解決する古典的なアルゴリズムであり、アルゴリズムは簡単で、迅速である.

は、その複雑さが約O(nkt)であり、nはすべてのオブジェクトの数であり、kはクラスタの数であり、tは反復の回数であるため、大きなデータセットを処理する.通常k<

アルゴリズムは,二乗誤差関数の数値を最小にするk個の区分を見つけようと試みた.クラスタが密集している、球状またはクラスタ状であり、クラスタとクラスタの違いが明らかである場合、クラスタ効果は比較的良好である.

欠点

k−平均メソッドは、クラスタの平均値が定義されている場合にのみ使用され、分類属性の一部のデータには適していない.

は、生成するクラスタの数kを事前にユーザに与えなければならないことを要求する.

は初期値に敏感であり、異なる初期値に対して異なるクラスタリング結果をもたらす可能性がある.

は、非凸面形状のクラスタを発見したり、大きさの差が大きいクラスタを発見したりするのに適していない.

は「ノイズ」および孤立点データに敏感であり、少量のデータは平均値に大きな影響を及ぼすことができる.

コード実装
コードはK-Means Clusteringから参照してください.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time    : 2016/10/21 16:35
@Author  : cai

   K-Means     
"""

import numpy as np
import matplotlib.pyplot as plt
from scipy.io import loadmat
import os

#         
def find_closest_centroids(X, centroids):
    m = X.shape[0]
    k = centroids.shape[0]
    idx = np.zeros(m)

    for i in range(m):
        min_dist = 1000000
        for j in range(k):
            #                
            dist = np.sum((X[i, :] - centroids[j, :]) ** 2)
            if dist < min_dist:
                #                 
                min_dist = dist
                idx[i] = j

    return idx

#       
def compute_centroids(X, idx, k):
    m, n = X.shape
    centroids = np.zeros((k, n))

    for i in range(k):
        indices = np.where(idx == i)
        #          ，                          
        centroids[i, :] = (np.sum(X[indices, :], axis=1) / len(indices[0])).ravel()

    return centroids

#        
def init_centroids(X, k):
    m, n = X.shape
    centroids = np.zeros((k, n))
    #       k   [0,m]   
    idx = np.random.randint(0, m, k)

    for i in range(k):
        centroids[i, :] = X[idx[i], :]

    return centroids

#    kmeans   
def run_k_means(X, initial_centroids, max_iters):
    m, n = X.shape
    #        
    k = initial_centroids.shape[0]
    idx = np.zeros(m)
    centroids = initial_centroids

    for i in range(max_iters):
        idx = find_closest_centroids(X, centroids)
        centroids = compute_centroids(X, idx, k)

    return idx, centroids

dataPath = os.path.join('data', 'ex7data2.mat')
data = loadmat(dataPath)
X = data['X']

initial_centroids = init_centroids(X, 3)
# print(initial_centroids)
# idx = find_closest_centroids(X, initial_centroids)
# print(idx)

# print(compute_centroids(X, idx, 3))

idx, centroids = run_k_means(X, initial_centroids, 10)
#        
cluster1 = X[np.where(idx == 0)[0], :]
cluster2 = X[np.where(idx == 1)[0], :]
cluster3 = X[np.where(idx == 2)[0], :]

fig, ax = plt.subplots(figsize=(12, 8))
ax.scatter(cluster1[:, 0], cluster1[:, 1], s=30, color='r', label='Cluster 1')
ax.scatter(cluster2[:, 0], cluster2[:, 1], s=30, color='g', label='Cluster 2')
ax.scatter(cluster3[:, 0], cluster3[:, 1], s=30, color='b', label='Cluster 3')
ax.legend()
plt.show()

#         ，    
imageDataPath = os.path.join('data', 'bird_small.mat')
image = loadmat(imageDataPath)
# print(image)

A = image['A']
print(A.shape)

#         
A = A / 255.

#          
X = np.reshape(A, (A.shape[0] * A.shape[1], A.shape[2]))
#          
initial_centroids = init_centroids(X, 16)
#       
idx, centroids = run_k_means(X, initial_centroids, 10)

#             
idx = find_closest_centroids(X, centroids)
# map each pixel to the centroid value
X_recovered = centroids[idx.astype(int), :]
# reshape to the original dimensions
X_recovered = np.reshape(X_recovered, (A.shape[0], A.shape[1], A.shape[2]))

# plt.imshow(X_recovered)
# plt.show()

完全なコード例とデータはKmeans練習コードを表示することができます.