k-means法 - ITエンジニアノイのブログ

k-means法とは

k-meansは、教師なし学習の一つで、データをk個のクラスタに分けるアルゴリズムです。データの「重心」や「代表点」を用いて、データ間の類似性に基づいてグループ化します。

機械学習の中での位置付け

k-meansは教師なし学習の一部として位置づけられます。教師なし学習は、データにラベルが付与されていない場合に使用される手法で、データの構造やパターンを見つけ出すことを目的としています。

メリット・デメリット

メリット

シンプルで理解しやすい。
大量のデータにも適用可能。

デメリット

クラスタの数kを事前に決定する必要がある。
初期の代表点の選び方が精度に影響する。
クラスタの形が球状でないときには適切に動作しないことがある。

クラスタの形が球状とは

k-meansアルゴリズムは、データポイントとクラスタの中心（代表点）とのユークリッド距離を基にクラスタリングを行います。このユークリッド距離は、空間内の2点間の直線距離を示すもので、k-meansがクラスタを形成する際の基本的な距離尺度として使用されます。
球状のクラスタ: k-meansは、各クラスタの中心からの距離を最小化するようにデータポイントを割り当てるため、生成されるクラスタは通常、球状（または、高次元空間では超球状）になります。
等方性: k-meansは、すべての方向が等しく、特定の方向にバイアスがかかっていないと仮定します。これは、クラスタが球状であることの直接的な結果です。

これらの特性のため、データが球状のクラスタを形成しない場合、k-meansは適切にクラスタリングできないことがあります。例えば、データが長い楕円形や複雑な形状をしている場合、k-meansはその形状を正確に捉えることができません。このような場合、他のクラスタリング手法やカーネル化されたk-meansなどの変種を検討することが推奨されます。

効果的に活用できる課題

k-meansは、市場セグメンテーション、画像の圧縮、ドキュメントのクラスタリングなど、データのグループ化が必要な多くの問題に適用可能です。

使用時の注意点

kの値の選択は非常に重要であり、適切なkの値を選択するための手法や評価方法を使用することが推奨されます。
初期の代表点の選び方によって結果が大きく変わる可能性があるため、複数回の実行やk-means++のような改良手法の使用を検討すると良い。
データの前処理や正規化が結果に影響を与えるため、注意が必要です。

k-meansの手順

k個のグループに対応する代表ベクトルをランダムに生成
各データと代表ベクトルの距離を求める
各データをそれぞれ最も近い代表ベクトルに割り振る
割り振り後のグループに対して平均ベクトルを求める
得られた平均ベクトルから新たな代表ベクトルを作る　→変化がなくなるまで繰り返す

pythonのコード例

import numpy as np

def init_centroid(X, k, n_data):
    # 代表ベクトルとなるデータのインデックスをランダムに選択
    idx = np.random.permutation(n_data)[:k]
    # インデックスをもとにランダムにデータを選択
    centroids = X[idx]
    return centroids

#グループを決定するために代表ベクトルと各データの距離を求める
def compute_distances(X,k,n_data,centroids):
    distances = np.zeros((n_data,k))
    for idx_centroids in range(k):
        dist = np.sqrt(np.sum(( X - centroids[idx_centroids]) ** 2, axis = 1))
        distances[:,idx_centroids] = dist
    return distances

def k_means(k,X,max_iter=300):
    """
    X.shape=(データ数, 次元数)
    k=クラスタ数
    """

    n_data,n_features =X.shape

    #セントロイドの初期値
    init_centroids = init_centroid(X,n_data,k)
    centroids = init_centroids

    #新しいクラスタを格納するための配列
    new_cluster = np.zeros(n_data)

    #各データの所属クラスタを保存する配列
    cluster = np.zeros(n_data)
    for epoch in range(max_iter):
        #各データ点とセントロイドとの距離を計算
        distances = compute_distances(X,k,n_data, centroids)
        #距離が最小となるように新たな所属クラスタを計算
        new_cluster = np.argmin(distances,axis=1)
        #すべてのクラスタに対してセントロイドを再計算
        for idx_centroids in range(k):
            centroids[idx_centroids] = X[new_cluster == idx_centroids].mean(axis=0)
        #クラスタによるグループ分けに変化がなかったら終了
        if (new_cluster ==cluster).all():
            break
        cluster = new_cluster
    return cluster, centroids, init_centroids

# ランダムシードを設定
np.random.seed(42)  # 任意の整数をシードとして選択

# データ点の数
num_data_points = 100

# 各クラスタのデータポイント数を設定
num_data_cluster1 = 30
num_data_cluster2 = 40
num_data_cluster3 = 30

# クラスタ1のデータを生成
cluster1 = np.random.randint(1, 31, size=(num_data_cluster1, 2))
# クラスタ2のデータを生成
cluster2 = np.random.randint(31, 71, size=(num_data_cluster2, 2))
# クラスタ3のデータを生成
cluster3 = np.random.randint(71, 101, size=(num_data_cluster3, 2))

# すべてのデータポイントを結合
X = np.vstack((cluster1, cluster2, cluster3))

k = 3
n_data = len(X)

# クラスタリングを実行
cluster, centroids, init_centroids= k_means(k, X)

# クラスタごとに異なる色を割り当てる
colors = ['r', 'g', 'b', 'c', 'm', 'y']

# データ点をクラスタごとにプロット
plt.figure(figsize=(8, 6))
for i in range(k):
    plt.scatter(X[cluster == i, 0], X[cluster == i, 1], c=colors[i], label=f'Cluster {i + 1}')

plt.title('K-Means Clustering')

# セントロイドをプロット
plt.scatter(centroids[:, 0], centroids[:, 1], c='black', marker='x', s=100, label='Centroids')

plt.legend()
plt.show()

このコードでは、Xはデータセットを表す2次元のNumPy配列です。具体的には、X.shape=(データ数, 次元数)となっており、行数はデータの個数を、列数はそのデータの特徴の次元数を示しています。

例えば、100個の2次元のデータ点をクラスタリングする場合、Xは(100, 2)の形状を持つ2次元配列になります。具体的に、Xの中身はデータセットの各点の特徴ベクトルが入ります。以下は、Xがどのような値を持つかの具体的な例を示します。例えば、2次元のデータ点を考えると、以下のようになります

X = np.array([
    [1.5, 2.5],  # 1番目のデータ点の座標
    [3.0, 4.0],  # 2番目のデータ点の座標
    [5.5, 6.5],  # 3番目のデータ点の座標
    ...
])

この場合、Xは(3, 2)の形状を持つ2次元配列で、3つのデータ点が含まれています。各データ点は2つの値（2次元の座標）を持ちます。

このように、Xの各行はデータの1つの点を表し、その点の座標（または特徴ベクトル）が各列に格納されます。

代表ベクトル

K-meansの代表ベクトルは、各クラスタの中心または平均を表すベクトルです。K-meansクラスタリングアルゴリズムは、データをクラスタにグループ化する際に、各クラスタの代表ベクトル（セントロイド）を計算し、それを用いてデータポイントをクラスタに割り当てます。

K-meansの代表ベクトルは、クラスタ内のデータポイントを代表しており、クラスタの特性や特徴を表します。このアルゴリズムは非監観学習の一つであり、データのクラスタリングやクラスタセンターの見つけ方に広く利用されています。

「セントロイド」「代表ベクトル」「中心」「重心」

多くの文脈で同じものを指し、データポイントの集合やクラスタに関連して使用されます。

セントロイド (Centroid): 一般的に、セントロイドはクラスタ内のデータポイントの平均または中心を表すベクトルです。K-meansクラスタリングなどのクラスタリングアルゴリズムでは、各クラスタのセントロイドはクラスタ内のデータポイントの平均として計算されます。また、多くの場合、セントロイドはクラスタを代表する特徴ベクトルとして使用されます。
代表ベクトル (Representative Vector): 代表ベクトルもセントロイドと同様に、クラスタやデータポイントの代表を示すベクトルを指します。代表ベクトルは、クラスタの特性を要約するために使用されることがあります。代表ベクトルの計算方法は特定の文脈に依存します。
中心 (Center): 中心は通常、クラスタやデータセットの中央位置を指します。セントロイドは一種の中心であり、特にクラスタ内のデータポイントの平均を表す中心です。しかし、中心の用語は幅広い文脈で使用され、必ずしもデータクラスタリングに限定されるわけではありません。
重心 (Centroid): 重心もセントロイドと同様に、クラスタ内のデータポイントの平均を指す用語として使用されます。この用語は、特に物理学や幾何学の文脈で広く使用され、質量やポイントの平均位置を表します。

これらの用語は、文脈によって微妙に異なるかもしれませんが、一般的にはデータの中央点や代表点を指すものとして理解できます。クラスタリングやデータ解析の文脈では、これらの用語はクラスタの特性を理解しやすくするために使用されます。

ユークリッド距離

代表ベクトル（セントロイド）と各点との距離はユークリッド距離で求めます。ユークリッド距離（Euclidean distance）は、座標空間において2つの点間の距離を測るために使用される距離尺度の一つです。ユークリッド距離は、通常の直線距離を示すもので、ピタゴラスの定理に基づいて計算されます。ユークリッド距離は、2つの点がn次元空間内に存在する場合にも適用できます。

2つの点AとBのユークリッド距離は以下の数式で表されます：

[d(A, B) = \sqrt{\sum_{i=1}^{n} (A_i - B_i)²}]

(d(A, B)) は点Aと点Bのユークリッド距離を表します。
(A_i) および (B_i) はそれぞれ点Aと点Bのn次元座標の成分を示します。
(n) は次元数を表します。

pythonでの実行結果

実際に実行すると次のような結果が得られます。ランダムを使っているので、若干結果が変わるかもしれません。今回のデータでは意図的に3クラスとなるようにデータを生成しています。そのため、k=3としています。しかし、実データではクラスタがいくつになるのかはデータごとに分析する必要があります。このクラスタ数のしていが実際のデータでは課題になるかもしれません。