Spectral ClusteringをJavaScriptで実装した

はじめに

「色々な機械学習処理をブラウザ上で試せるサイトを作った」中で実装したモデルの解説の十一回目です。

今回はSpectral Clusteringの実装について解説します。

デモはこちらから。（TaskをClusteringにして、ModelのSpectral clusteringを選択）
実際のコードはspectral.jsにあります。

なお、可視化部分については一切触れません。

概説

やることは簡単で、ラプラシアン行列の固有ベクトルを求めて、その値でクラスタリングするだけです。

ラプラシアン行列や、それを求めるための重み行列にパターンがいくつかありまが、基本は同じです。

詳しい原理などはこちらに詳しく乗っていましたので、参考にしてください。

重み行列

重み行列$W$は、距離が近いと大きい値を持つような行列です。

実装では、K近傍とガウシアンカーネルを用いた距離を用意しています。

ラプラシアン行列

実装でのラプラシアン行列は以下の$L_{sym}$を採用しています。

\begin{eqnarray}
L_{sym} &=& D^{-1 / 2}LD^{-1 / 2}
\\
\\
L &=& D - W
\\
d_{i, i} &=& \left\{ \begin{array}{ll}
  \sum_j w_{i, j} & (i = j) \\
  0 & (i \not= j)
\end{array} \right.
\end{eqnarray}

コード

Spectral Clustering

class SpectralClustering {
	// https://mr-r-i-c-e.hatenadiary.org/entry/20121214/1355499195
	constructor(affinity = 'rbf', param = {}) {
		this._size = 0;
		this._epoch = 0;
		this._clustering = new KMeansModel();
		this._clustering.method = new KMeanspp();
		this._affinity = affinity;
		this._sigma = param.sigma || 1.0;
		this._k = param.k || 10;
	}

	get size() {
		return this._size;
	}

	get epoch() {
		return this._epoch;
	}

	init(datas, cb) {
		const n = datas.length;
		this._n = n;
		this._l = Matrix.zeros(n, n);
		const distance = new Matrix(n, n);
		for (let i = 0; i < n; i++) {
			distance.set(i, i, 0);
			for (let j = 0; j < i; j++) {
				let d = Math.sqrt(datas[i].reduce((acc, v, t) => acc + (v - datas[j][t]) ** 2, 0));
				distance.set(i, j, d);
				distance.set(j, i, d);
			}
		}

		let affinity_mat;
		if (this._affinity === 'knn') {
			const con = Matrix.zeros(n, n);
			for (let i = 0; i < n; i++) {
				const di = distance.row(i).value.map((v, i) => [v, i]);
				di.sort((a, b) => a[0] - b[0]);
				for (let j = 1; j < Math.min(this._k + 1, di.length); j++) {
					con.set(i, di[j][1], 1);
				}
			}
			con.add(con.t)
			con.div(2);
			affinity_mat = con;
		} else {
			affinity_mat = distance.copyMap(v => Math.exp(-(v ** 2) / (this._sigma ** 2)));
		}
		let d = affinity_mat.sum(1).value;
		this._l = Matrix.diag(d)
		this._l.sub(affinity_mat);

		d = d.map(v => Math.sqrt(v))
		for (let i = 0; i < this._n; i++) {
			for (let j = 0; j < this._n; j++) {
				this._l.set(i, j, this._l.at(i, j) / (d[i] * d[j]));
			}
		}

		this.ready = false
		this._l.eigenVectors(data => {
			this._ev = data;
			this.ready = true;
			cb && cb();
		});
	}

	add() {
		this._size++;
		this._clustering.clear();
		const s_ev = this._ev.select(null, this._n - this._size, null, this._n);
		this._s_ev = s_ev.toArray();
		for (let i = 0; i < this._size; i++) {
			this._clustering.add(this._s_ev);
		}
	}

	clear() {
		this._size = 0;
		this._epoch = 0;
		this._clustering.clear();
	}

	predict(datas) {
		return this._clustering.predict(this._s_ev);
	}

	fit(datas) {
		this._epoch++;
		return this._clustering.fit(this._s_ev);
	}
}