クラスタリングと次元削減のしくみ：k-means・DBSCAN・PCA・t-SNE
ここまでの機械学習の記事は、画像と「猫」のような、入力と正解の組から学ぶ 教師あり学習が中心でした。ところが、実際の仕事では正解のラベルが付いていないデータのほうがずっと多くあります。購買の記録から似た客のグループを見つけたい、何十列もあるデータを 2 次元のグラフで眺めたい、といったときに使うのが、ラベルなしでデータの構造を見つける 教師なし学習です。
この記事では、教師なし学習の代表である クラスタリング（似たデータをまとまりに分ける）と 次元削減（たくさんの特徴を、少ない数にまとめる）を、NumPy で実装しながら説明します。
結論を先に書くと、次のように整理できます。
| 手法 | 種類 | 考え方 | 注意点 |
|---|---|---|---|
| k-means | クラスタリング | 「いちばん近い中心に割り当てる」「中心を平均に動かす」をくり返す | まとまりの数 k を決める必要がある。丸いまとまりしか見つけられない |
| DBSCAN | クラスタリング | 点が密に集まっている場所をつないでいく | 「近い」とみなす距離の決め方で結果が大きく変わる |
| 主成分分析（PCA） | 次元削減 | データのばらつきがいちばん大きい向きを順に軸にする | まっすぐな（線形の）関係しかとらえられない。特徴の単位をそろえる必要がある |
| t-SNE | 次元削減（可視化） | 近所どうしの関係を保つように平面に並べる | まとまりの大きさや、まとまりどうしの距離はそのまま読めない |
説明の途中に出てくる計算例は、Python と NumPy で実際に動かした結果です。
環境
計算例を動かした環境です。
| 項目 | バージョン |
|---|---|
| Python | 3.13 |
| NumPy | 2.5 |
k-means：中心を決めて割り当てる
2 つの手順のくり返し
k-means 法は、データを決まった数 k のまとまり（クラスタ）に分ける、いちばんよく使われる方法です。各クラスタには「中心」があり、次の 2 つをくり返します。
- 割り当て: それぞれの点を、いちばん近い中心のクラスタに入れる
- 更新: それぞれのクラスタの中心を、そこに入った点の平均の位置に動かす
割り当てが変わらなくなったら終わりです。くり返すたびに「各点から自分の中心までの距離の 2 乗の和」（SSE）が小さくなっていくので、必ずどこかで止まります。
3 つのまとまりがある平面上の 150 個の点で試してみます。
import numpy as np
# 3 つのまとまりを持つ平面上の点（各 50 個）
rng = np.random.default_rng(0)
centers_true = np.array([[0, 0], [5, 5], [0, 6]])
X = np.vstack([rng.normal(c, 1.0, (50, 2)) for c in centers_true])
def kmeans(X, k, init, max_iter=100):
centers = init.copy()
for it in range(1, max_iter + 1):
d = ((X[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2)
labels = d.argmin(axis=1) # 1. いちばん近い中心に割り当てる
new = np.array([X[labels == j].mean(axis=0) for j in range(k)]) # 2. 中心を平均に動かす
if np.allclose(new, centers):
break
centers = new
sse = float(((X - centers[labels]) ** 2).sum()) # 中心までの距離の 2 乗の和
return labels, centers, sse, it
init = X[rng.choice(len(X), 3, replace=False)] # ランダムに選んだ 3 点から始める
labels, centers, sse, it = kmeans(X, 3, init)
print(it, round(sse, 1))
print(np.round(centers, 2))
print(np.bincount(labels))実行結果:
4 299.9
[[-0.41 6.06]
[-0.01 0.18]
[ 4.83 5.07]]
[49 50 51]4 回のくり返しで止まり、見つかった中心は (−0.41, 6.06)・(−0.01, 0.18)・(4.83, 5.07) と、データを作ったときの中心 (0, 6)・(0, 0)・(5, 5) にほぼ一致しました。クラスタに入った点の数も 49・50・51 と、各 50 個にほぼ分かれています。
ラベルを一切使っていないのに、データの中のまとまりを見つけられたことになります。ただし、見つかったクラスタに「何のまとまりか」という意味を付けるのは人の仕事です。
初期値しだいで悪い答えに止まる
k-means は、最初の中心の置き方によっては、悪い答えで止まってしまうことがあります。たとえば 2 つの中心が同じまとまりの中に置かれると、そのまとまりを 2 つに割り、別の 2 つのまとまりを 1 つの中心で受け持ったまま動けなくなります。
これを減らす方法が k-means++ です。最初の中心を 1 つランダムに選んだら、次の中心は「すでに選んだ中心から遠い点ほど選ばれやすい」確率で選びます。中心がばらけて置かれるので、同じまとまりに 2 つ入りにくくなります。初期値を変えて 100 回ずつ試し、SSE を比べてみます。上のコードの続きです。
def kmeanspp_init(X, k, rng):
"""k-means++：すでに選んだ中心から遠い点ほど選ばれやすくする"""
centers = [X[rng.integers(len(X))]]
for _ in range(k - 1):
d = ((X[:, None, :] - np.array(centers)[None, :, :]) ** 2).sum(axis=2).min(axis=1)
centers.append(X[rng.choice(len(X), p=d / d.sum())])
return np.array(centers)
for name, make_init in [("ランダム", lambda: X[rng.choice(len(X), 3, replace=False)]),
("k-means++", lambda: kmeanspp_init(X, 3, rng))]:
sses = [kmeans(X, 3, make_init())[2] for _ in range(100)]
print(name, round(min(sses), 1), round(max(sses), 1), sum(s > 300 for s in sses))実行結果:
ランダム 299.9 1121.1 3
k-means++ 299.9 980.2 1左から、初期化の方法、100 回の中でいちばん良い SSE、いちばん悪い SSE、良い答え（299.9）にたどり着けなかった回数です。ランダムな初期化では 100 回中 3 回、k-means++ でも 1 回、SSE が 3 倍以上の悪い答えで止まりました。まとまりが 3 つしかないこの例では差は小さいですが、まとまりの数が多いほど k-means++ の効果は大きくなります。
k-means++ でも悪い答えをなくすことはできないので、実際には初期値を変えて何回か実行し、SSE がいちばん小さい結果を使います。
k の決め方：エルボー法とシルエット係数
k-means では、まとまりの数 k を自分で決める必要があります。ところが SSE は、k を増やすほど必ず小さくなる（k をデータの数にすれば 0 になる）ので、SSE が最小の k を選ぶことはできません。そこで、次の 2 つがよく使われます。
| 方法 | 見るもの |
|---|---|
| エルボー法 | k を増やしたときの SSE の下がり方。急に下がらなくなる「ひじ」の k を選ぶ |
| シルエット係数 | 各点について、自分のクラスタの中の平均距離 a と、いちばん近い別のクラスタまでの平均距離 b から (b − a) ÷ max(a, b) を求め、全点で平均する。−1〜1 で、大きいほど「中ではまとまり、外とは離れている」 |
上のコードの続きで、k = 1〜6 を比べてみます。
def silhouette(X, labels):
"""シルエット係数：(近くの別のまとまりまでの平均距離 − 自分のまとまりの中の平均距離) ÷ 大きいほう"""
D = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(axis=2))
scores = []
for i in range(len(X)):
same = labels == labels[i]
a = D[i, same].sum() / (same.sum() - 1)
b = min(D[i, labels == j].mean() for j in set(labels) if j != labels[i])
scores.append((b - a) / max(a, b))
return float(np.mean(scores))
for k in range(1, 7):
best = min((kmeans(X, k, kmeanspp_init(X, k, rng)) for _ in range(10)), key=lambda r: r[2])
sil = silhouette(X, best[0]) if k > 1 else float("nan")
print(k, round(best[2], 1), round(sil, 3))実行結果:
1 2147.2 nan
2 1011.7 0.523
3 299.9 0.664
4 256.8 0.557
5 219.3 0.453
6 184.2 0.369左から k、SSE、シルエット係数です（k = 1 ではシルエット係数は計算できません）。SSE は k = 2 から 3 で 1011.7 → 299.9 と大きく下がり、そのあとは 256.8・219.3 とゆるやかにしか下がりません。k = 3 が「ひじ」です。シルエット係数も k = 3 の 0.664 がいちばん大きく、どちらの方法でも、データを作ったときと同じ k = 3 が選ばれました。
実際のデータでは、ひじがはっきりしないことも多く、最終的には「分けた結果が使い道に合っているか」で決めることになります。
このサイトの k-means 法の可視化 では、割り当てと中心の更新をくり返してクラスタが決まっていく様子を 1 手ずつ見られます。ランダムな初期化と k-means++ の違い、エルボー法のグラフ、三日月や同心円のデータで k-means がうまく分けられない様子も確かめられます。
DBSCAN：密に集まっている場所をつなぐ
k-means が苦手な形
k-means は、各点を「いちばん近い中心」に割り当てるので、見つけられるのは中心のまわりに丸く集まったまとまりだけです。同心円のように、まとまりが中心のまわりに丸く集まっていないデータは分けられません。
DBSCAN は、中心を使わず、点の 密度でまとまりを見つけます。
- 半径 eps の中に min_pts 個以上の点がある点を「密な点」とする
- 密な点から始めて、半径 eps の中にある点を同じまとまりに入れ、入った点が密な点なら、さらにその近くの点も入れる、と広げていく
- どのまとまりにも入らなかった点は 外れ値とする
点がつながっていれば、まとまりがどんな形でも 1 つとして見つけられます。また、まとまりの数を先に決める必要がなく、外れ値を外れ値として扱えるのも長所です。
同心円のデータで、k-means（k = 2）と DBSCAN を比べてみます。
import numpy as np
# 同心円：内側の円（半径 1）と外側の円（半径 3）に 150 個ずつ
rng = np.random.default_rng(0)
angle = rng.uniform(0, 2 * np.pi, 300)
radius = np.where(np.arange(300) < 150, 1.0, 3.0) + rng.normal(0, 0.1, 300)
X = np.column_stack([radius * np.cos(angle), radius * np.sin(angle)])
truth = (np.arange(300) >= 150).astype(int)
def agreement(labels, truth):
"""2 つのまとまりの分け方が正解とどれだけ一致するか（番号の付け方の違いは無視）"""
return max((labels == truth).mean(), (labels == 1 - truth).mean())
# k-means（k = 2）
centers = X[rng.choice(300, 2, replace=False)]
for _ in range(100):
labels = ((X[:, None] - centers[None]) ** 2).sum(axis=2).argmin(axis=1)
centers = np.array([X[labels == j].mean(axis=0) for j in range(2)])
print("k-means", round(float(agreement(labels, truth)), 3))
def dbscan(X, eps, min_pts):
"""DBSCAN：半径 eps の中に min_pts 個以上の点がある「密な点」から、つながる点を広げていく"""
D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(axis=2))
neighbors = [np.flatnonzero(D[i] <= eps) for i in range(len(X))]
labels = np.full(len(X), -1) # −1 はまだどこにも入っていない（最後まで残れば外れ値）
cluster = 0
for i in range(len(X)):
if labels[i] != -1 or len(neighbors[i]) < min_pts:
continue
labels[i] = cluster
queue = list(neighbors[i])
while queue:
j = queue.pop()
if labels[j] == -1:
labels[j] = cluster
if len(neighbors[j]) >= min_pts: # 密な点なら、その近くの点も同じまとまりに入れる
queue.extend(neighbors[j])
cluster += 1
return labels
for eps in [0.5, 1.0, 2.5]:
labels = dbscan(X, eps=eps, min_pts=5)
n_clusters = len(set(labels) - {-1})
score = round(float(agreement(labels, truth)), 3) if n_clusters == 2 else "-"
print("DBSCAN", eps, n_clusters, int((labels == -1).sum()), score)実行結果:
k-means 0.53
DBSCAN 0.5 7 2 -
DBSCAN 1.0 2 0 1.0
DBSCAN 2.5 1 0 -k-means は、平面を直線で 2 つに割るような分け方しかできず、正解との一致は 53% と、でたらめに分けたのとほとんど変わりません。
DBSCAN の行は、左から eps、見つかったまとまりの数、外れ値の数、正解との一致（まとまりが 2 つのときだけ）です。eps = 1.0 では、内側と外側の円を 2 つのまとまりとして完全に見分けました。ただし、eps = 0.5 では外側の円の点のすき間をつなげず 7 つにちぎれ、eps = 2.5 では 2 つの円がつながって 1 つになりました。DBSCAN は形には強い一方、「近い」とみなす距離の決め方に敏感です。また、密度がまとまりごとに大きく違うデータは苦手です。
次元削減：たくさんの特徴を少ない数にまとめる
なぜ次元を減らすのか
データの特徴（列）の数を 次元と呼びます。次元が多いと、次のような困りごとがあります。
- グラフにして目で見られない（見られるのは 2〜3 次元まで）
- 計算に時間がかかり、保存にも場所を取る
- 似た特徴が重なっていると、モデルが不安定になったり、過学習しやすくなったりする
- 次元が多いほど、どの点もほかの点から同じくらい遠くなり、「近さ」を使う手法が効きにくくなる（次元の呪い）
次元削減は、データの情報をなるべく残したまま、特徴の数を減らす方法です。
主成分分析（PCA）：ばらつきの大きい向きを軸にする
2 つの特徴を 1 つにまとめる
主成分分析（PCA）は、データのばらつき（分散）がいちばん大きい向きを第 1 の軸、それと直角な向きのうちで次にばらつきの大きい向きを第 2 の軸、のように新しい軸を選び直し、ばらつきの大きい軸だけを残す方法です。新しい軸を 主成分と呼びます。
主成分は、データの 分散共分散行列の固有ベクトルとして求まり、固有値はその軸の向きの分散を表します。強く関係している身長と体重の 200 人分のデータ（乱数で作ったもの）で計算してみます。
import numpy as np
# 身長（cm）と体重（kg）。強く関係している 2 つの特徴
rng = np.random.default_rng(0)
height = rng.normal(170, 7, 200)
weight = 0.9 * (height - 170) + 65 + rng.normal(0, 3, 200)
X = np.column_stack([height, weight])
Xc = X - X.mean(axis=0) # 平均を 0 にずらす
cov = Xc.T @ Xc / (len(X) - 1) # 分散共分散行列
eigvals, eigvecs = np.linalg.eigh(cov)
order = np.argsort(eigvals)[::-1] # 分散の大きい順に並べる
eigvals, eigvecs = eigvals[order], eigvecs[:, order]
eigvecs *= np.sign(eigvecs.sum(axis=0)) # 向きの符号をそろえる（どちら向きでも同じ軸）
print(np.round(eigvals, 2), np.round(eigvals / eigvals.sum(), 3))
print(np.round(eigvecs[:, 0], 3)) # 第 1 主成分の向き
z = Xc @ eigvecs[:, 0] # 1 つの数（第 1 主成分の値）に圧縮
print(np.round(z[:3], 2), np.round(X[:3], 1))実行結果:
[84.32 5.11] [0.943 0.057]
[0.714 0.7 ]
[-0.17 -2.49 2.7 ] [[170.9 63.8]
[169.1 62.3]
[174.5 64.2]]1 行目は、2 つの主成分の分散と、全体の分散に占める割合（寄与率）です。第 1 主成分だけで、ばらつきの 94.3% を説明できています。2 行目は第 1 主成分の向き (0.714, 0.7) で、「身長と体重がそろって大きい・小さい」という向き、いわば「体の大きさ」の軸です。3 行目は、最初の 3 人を第 1 主成分の値 1 つに圧縮したもので、身長も体重も大きい 3 人目（174.5 cm・64.2 kg）が 2.7 といちばん大きな値になっています。
2 つの数を 1 つにしても、情報の 94% が残るということです。画像生成 AI の記事 で説明したオートエンコーダーは、エンコーダーとデコーダーを線形にすると PCA と同じ圧縮になります。
たくさんの特徴の中から本当の要因を見つける
PCA が役に立つのは、特徴が多いのに、実は少ない数の要因で決まっているデータです。20 個の特徴が、3 つの要因とノイズで作られているデータで、主成分ごとの寄与率を見てみます。
import numpy as np
# 20 個の特徴があるが、実は 3 つの要因でほぼ決まっているデータ
rng = np.random.default_rng(0)
factors = rng.standard_normal((500, 3))
X = factors @ rng.standard_normal((3, 20)) + 0.3 * rng.standard_normal((500, 20))
Xc = X - X.mean(axis=0)
s = np.linalg.svd(Xc, compute_uv=False) # 特異値分解でも主成分の分散が求まる
ratio = s**2 / (s**2).sum()
print(np.round(ratio[:6], 3))
print(np.round(np.cumsum(ratio)[:6], 3))実行結果:
[0.524 0.272 0.171 0.003 0.002 0.002]
[0.524 0.796 0.967 0.97 0.972 0.974]1 行目は第 1〜6 主成分の寄与率、2 行目はその累積です。第 3 主成分までで 96.7% に達し、第 4 主成分からは 0.3% 以下と急に小さくなりました。20 個の特徴が、実は 3 つの要因でほぼ決まっていることを、PCA が見つけたということです。k-means のエルボー法と同じように、寄与率が急に小さくなるところまでを残すのが、主成分の数の決め方の目安です。
特徴の単位をそろえる
PCA は分散の大きい向きを選ぶので、特徴の単位（大きさ）がそろっていないと、値の大きい特徴に引っぱられます。年収（万円）と年齢（歳）のデータで、そのまま PCA をした場合と、特徴ごとに平均 0・標準偏差 1 にそろえる 標準化をしてから PCA をした場合を比べます。
import numpy as np
# 年収（万円）と年齢（歳）。単位も大きさも違う 2 つの特徴
rng = np.random.default_rng(0)
age = rng.uniform(25, 60, 300)
income = 10 * (age - 25) + 300 + rng.normal(0, 100, 300)
X = np.column_stack([income, age])
def first_component(X):
Xc = X - X.mean(axis=0)
eigvals, eigvecs = np.linalg.eigh(np.cov(Xc.T))
v = eigvecs[:, eigvals.argmax()]
return np.round(v * np.sign(v.sum()), 3), round(float(eigvals.max() / eigvals.sum()), 3)
print(*first_component(X))
Xs = (X - X.mean(axis=0)) / X.std(axis=0) # 標準化：特徴ごとに平均 0・標準偏差 1 にそろえる
print(*first_component(Xs))実行結果:
[0.999 0.054] 0.997
[0.707 0.707] 0.861標準化しないと、第 1 主成分の向きは (0.999, 0.054) で、ほぼ年収だけの軸になり、寄与率は 99.7% と出ます。年収の値の幅（数百）が年齢の幅（数十）よりずっと大きいので、分散の大部分を年収が占めてしまうためです。これは「年収と年齢の関係」をとらえたのではなく、単位の違いを見ているだけです。標準化すると、向きは (0.707, 0.707) になり、「年齢が高いほど年収も高い」という 2 つの特徴の関係を表す軸になりました。
単位の違う特徴を PCA に入れるときは、標準化してから使うのが基本です。k-means や k 近傍法のように距離を使う手法でも同じです。
t-SNE：近所どうしの関係を保って平面に並べる
曲がった構造を可視化する
PCA は、データをまっすぐな軸に投影するだけなので、曲がった構造を持つデータでは、離れているはずのまとまりが重なって見えることがあります。t-SNE は、データを 2 次元のグラフで眺めるための次元削減の方法で、「元の空間で近所どうしだった点は、平面でも近所どうしになる」ように点を並べます。
- 元の空間で、各点から見て「ほかの点が近所である確率」P を、正規分布の形で作る。分布の幅は点ごとに、近所とみなす点の数がおよそ perplexity（ここでは 30）個になるように決める
- 平面に点をランダムに置き、平面での近所の確率 Q を、裾の重い t 分布の形で作る
- Q が P に近づくように（KL ダイバージェンスが小さくなるように）、勾配降下法で平面の点を動かす
平面で t 分布を使うのは、元の空間で中くらいに離れていた点を、平面ではもっと離して置けるようにするためです。これにより、まとまりどうしがはっきり分かれて見えます。
まとまりの大きさと距離は信用できない
10 次元の 3 つのまとまりで、t-SNE を実装して試してみます。まとまり A は広がりが小さく遠くにあり、B と C は比較的近く、C は広がりが大きくなるように作りました。
import numpy as np
# 10 次元の 3 つのまとまり。A は広がりが小さく、C は大きい。B と C は近く、A だけ遠い
rng = np.random.default_rng(0)
means = np.zeros((3, 10)); means[1, 0] = 6; means[2, 0] = 20; means[0, 1] = 40
spreads = [0.5, 1.0, 3.0]
X = np.vstack([rng.normal(means[i], spreads[i], (60, 10)) for i in range(3)])
group = np.repeat([0, 1, 2], 60)
def tsne(X, perplexity=30, steps=1000, seed=0):
n = len(X)
D = ((X[:, None] - X[None]) ** 2).sum(axis=2)
# 1. 元の空間で「点 i から見て点 j が近所である確率」P を作る。
# 幅（σ）は点ごとに、近所の数がおよそ perplexity 個になるよう二分探索で決める
P = np.zeros((n, n))
for i in range(n):
lo, hi = 1e-10, 1e10
for _ in range(60):
beta = np.sqrt(lo * hi) # beta = 1 / (2σ²)
d = D[i].copy(); d[i] = np.inf
p = np.exp(-(d - d.min()) * beta); p /= p.sum()
entropy = -(p[p > 0] * np.log(p[p > 0])).sum()
if np.exp(entropy) > perplexity:
lo = beta
else:
hi = beta
P[i] = p
P = (P + P.T) / (2 * n)
# 2. 平面の点 Y を、t 分布で作った近所の確率 Q が P に近づくように動かす
rng = np.random.default_rng(seed)
Y = rng.normal(0, 1e-4, (n, 2))
velocity = np.zeros_like(Y)
for t in range(steps):
exaggerate = 12 if t < 250 else 1 # 最初はまとまりを作りやすくするため P を強調する
diff = Y[:, None] - Y[None]
num = 1 / (1 + (diff**2).sum(axis=2)); np.fill_diagonal(num, 0)
Q = num / num.sum()
grad = 4 * (((exaggerate * P - Q) * num)[:, :, None] * diff).sum(axis=1)
velocity = (0.5 if t < 250 else 0.8) * velocity - 200 * grad
Y += velocity
return Y
Y = tsne(X)
def spread(Z, g):
return float(np.sqrt(((Z[group == g] - Z[group == g].mean(axis=0)) ** 2).sum(axis=1).mean()))
def center_dist(Z, a, b):
return float(np.linalg.norm(Z[group == a].mean(axis=0) - Z[group == b].mean(axis=0)))
print([round(spread(X, g), 1) for g in range(3)], [round(spread(Y, g), 1) for g in range(3)])
print([round(center_dist(X, *p), 1) for p in [(0, 1), (1, 2), (0, 2)]],
[round(center_dist(Y, *p), 1) for p in [(0, 1), (1, 2), (0, 2)]])実行結果:
[1.6, 3.0, 9.7] [1.9, 2.0, 4.1]
[40.5, 14.4, 45.2] [54.4, 22.2, 52.7]1 行目は、A・B・C の広がり（中心からの距離の 2 乗の平均の平方根）を、元の 10 次元と t-SNE の平面で比べたものです。元の空間では C は A の 6 倍の広がりがあるのに、平面では 2 倍ほどにしかなりません。A と B の広がりは、元の空間では 2 倍近く違うのに、平面ではほぼ同じ（1.9 と 2.0）です。t-SNE は、点ごとに近所の数が perplexity 個になるように幅を決めるので、密なまとまりは広げ、まばらなまとまりは縮めて、どのまとまりも同じくらいの大きさに描く傾向があるからです。
2 行目は、まとまりの中心どうしの距離（A–B・B–C・A–C）です。この例では「A だけが遠い」という並びは平面でも保たれていますが、t-SNE は近所の関係を保つことしか目指していないので、離れたまとまりどうしの距離がいつも正しく描かれるとは限りません。
t-SNE のグラフを読むときは、次の点に気をつけます。
- まとまりの大きさは、元のデータの広がりを表していない
- まとまりどうしの距離は、そのまま比べられるとは限らない
- perplexity を変えると、見た目が大きく変わる。いくつかの値で描いて比べる
- 乱数の初期値で結果が変わる。何度か描いて、いつも現れる構造だけを信じる
t-SNE は計算に時間がかかる（データの数の 2 乗に比例する）ため、大きなデータでは、2018 年に提案された UMAP もよく使われます。UMAP も考え方は近く、同じ注意が当てはまります。
教師なし学習の手法の流れ
この記事で紹介した手法を年代順に並べます。
| 年 | 手法 | ポイント |
|---|---|---|
| 1901 | 主成分分析（ピアソン） | ばらつきの大きい向きを軸にする。1933 年にホテリングが発展させる |
| 1957 | k-means（ロイド） | 割り当てと中心の更新をくり返す（論文として公開されたのは 1982 年） |
| 1963 | 階層的クラスタリング（ウォード法） | 近いまとまりから順に 1 つずつ併合していく |
| 1967 | 「k-means」の名前（マックイーン） | k 個の平均でまとまりを表す方法として名付ける |
| 1977 | EM アルゴリズム | 正規分布を重ねたモデル（混合ガウスモデル）で、確率的にまとまりを見つけられる |
| 1987 | シルエット係数 | まとまりの中の近さと外との離れ具合で、分け方を評価する |
| 1996 | DBSCAN | 密度でまとまりを見つけ、外れ値も扱う |
| 2007 | k-means++ | 中心をばらけて選び、悪い答えで止まりにくくする |
| 2008 | t-SNE | 近所の関係を保って、高い次元のデータを平面に描く |
| 2018 | UMAP | t-SNE より速く、大きなデータを可視化する |
まとめ
- 教師なし学習は、正解のラベルなしでデータの構造を見つける。代表はクラスタリングと次元削減
- k-means は「いちばん近い中心に割り当てる」「中心を平均に動かす」をくり返す。初期値しだいで悪い答えに止まるので、k-means++ で初期化し、何回か試して良い結果を使う
- k はエルボー法やシルエット係数を目安に選ぶ
- k-means は丸いまとまりしか見つけられない。DBSCAN は密度でつなぐので形に強いが、距離のしきい値に敏感
- PCA はばらつきの大きい向きを順に軸にし、寄与率が大きい軸だけを残して次元を減らす。単位の違う特徴は標準化してから使う
- t-SNE は近所の関係を保って平面に並べる可視化の方法。まとまりの大きさや距離はそのまま読めず、perplexity で見た目が変わる
参考
- K. Pearson, "On Lines and Planes of Closest Fit to Systems of Points in Space", Philosophical Magazine 1901
- H. Hotelling, "Analysis of a complex of statistical variables into principal components", Journal of Educational Psychology 1933
- J. H. Ward, "Hierarchical Grouping to Optimize an Objective Function", Journal of the American Statistical Association 1963
- J. MacQueen, "Some Methods for Classification and Analysis of Multivariate Observations", Berkeley Symposium on Mathematical Statistics and Probability 1967
- A. P. Dempster, N. M. Laird and D. B. Rubin, "Maximum Likelihood from Incomplete Data via the EM Algorithm", Journal of the Royal Statistical Society: Series B 1977
- S. P. Lloyd, "Least Squares Quantization in PCM", IEEE Transactions on Information Theory 1982
- P. J. Rousseeuw, "Silhouettes: A graphical aid to the interpretation and validation of cluster analysis", Journal of Computational and Applied Mathematics 1987
- M. Ester et al., "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD 1996
- D. Arthur and S. Vassilvitskii, "k-means++: The Advantages of Careful Seeding", SODA 2007
- L. van der Maaten and G. Hinton, "Visualizing Data using t-SNE", JMLR 2008
- M. Wattenberg et al., "How to Use t-SNE Effectively", Distill 2016（distill.pub/2016/misread-tsne）
- L. McInnes et al., "UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction", 2018（arXiv:1802.03426）