CLARANSをJavaScriptで実装した

はじめに

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

今回はPAMおよびCLARANSの実装について解説します。

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

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

概説

朱鷺の杜Wikiのアルゴリズムをコードに起こしただけです。

※PAMは認証モジュールのことではありませんのでご注意ください。

PAM(Partitioning Around Medoids)

最初にランダムにセントロイドを選択します。
そのセントロイドの中から一つをガリガリと入れ替え、最善のコストになる場所を見つけます。
fit関数一回の呼び出に対して、最善の入れ替えを各セントロイドで一回ずつ行います。

コストはセントロイドとそのカテゴリに属するデータとの距離の総和とし、それもガリガリと計算しています。
k-medois法と同じようなものですが、それとは異なり全パターンをチェックすることになります。

なんとなく間違っているような気がしているため、GUI側からは使用できないようにしています。

CLARA(Clustering LARge Applications)

イメージがいまいちつかめていないため、実装していません。

CLARANS(Clustering Large Applications based on RANdomized Search)

隣接した分割は、一つのデータだけカテゴリを変更した状態と考えます。

本質的なアルゴリズムは単純です。
全データ中から一つデータを選択し、そのカテゴリをランダムに変更してコストを計算、そしてコストが小さくなれば採用する、ということを繰り返します。
この繰り返しに対して、numlocalとmaxneighborという細かい条件を付けているだけです。

使用するコストは、カテゴリに属するデータの重心と各データとの距離の総和とします。

コード

PAM

this._centroidsには各クラスタのセントロイドとするデータのインデックスが設定されます。

class PAM {
	// http://ibisforest.org/index.php?CLARANS
	constructor(k) {
		this._k = k
	}

	_distance(a, b) {
		return Math.sqrt(a.reduce((acc, v, i) => acc + (v - b[i]) ** 2, 0));
	}

	_cost(centroids) {
		const c = centroids.map(v => this._x[v])
		const n = this._x.length
		let cost = 0;
		for (let i = 0; i < n; i++) {
			const category = argmin(c, v => this._distance(this._x[i], v))
			cost += this._distance(this._x[i], c[category])
		}
		return cost
	}

	init(datas) {
		this._x = datas;
		const idx = []
		for (let i = 0; i < this._x.length; idx.push(i++));
		shuffle(idx)
		this._centroids = idx.slice(0, this._k);
	}

	fit() {
		const n = this._x.length
		let init_cost = this._cost(this._centroids)
		for (let k = 0; k < this._k; k++) {
			let min_cost = Infinity;
			let min_idx = -1;
			for (let i = 0; i < n; i++) {
				if (this._centroids.some(c => c === i)) {
					continue
				}
				const new_c = this._centroids.concat()
				new_c[k] = i
				const new_cost = this._cost(new_c);
				if (new_cost < min_cost) {
					min_cost = new_cost
					min_idx = i
				}
			}
			if (min_cost < init_cost) {
				this._centroids[k] = min_idx
				init_cost = min_cost
			}
		}
	}

	predict() {
		const c = this._centroids.map(v => this._x[v])
		return this._x.map(x => {
			return argmin(c, v => this._distance(x, v));
		});
	}
}

CLARANS

this._categoriesには各データのクラスタ番号が設定されます。

class CLARANS {
	// http://ibisforest.org/index.php?CLARANS
	constructor(k) {
		this._k = k
	}

	_distance(a, b) {
		return Math.sqrt(a.reduce((acc, v, i) => acc + (v - b[i]) ** 2, 0));
	}

	_cost(categories) {
		const n = this._x.length
		const centroids = []
		const count = []
		for (let i = 0; i < n; i++) {
			const cat = categories[i]
			if (!centroids[cat]) {
				centroids[cat] = this._x[i].concat()
				count[cat] = 1
			} else {
				for (let k = 0; k < this._x[i].length; k++) {
					centroids[cat][k] += this._x[i][k]
				}
				count[cat]++
			}
		}
		for (let i = 0; i < centroids.length; i++) {
			for (let k = 0; k < centroids[i].length; k++) {
				centroids[i][k] /= count[i]
			}
		}
		let cost = 0;
		for (let i = 0; i < n; i++) {
			cost += this._distance(this._x[i], centroids[categories[i]])
		}
		return cost;
	}

	init(datas) {
		this._x = datas;
		this._categories = [];
		for (let i = 0; i < this._x.length; i++) {
			this._categories[i] = Math.floor(Math.random() * this._k);
		}
	}

	fit(numlocal, maxneighbor) {
		const n = this._x.length
		const categories = this._categories;
		let i = 1;
		let mincost = Infinity
		while (i <= numlocal) {
			let j = 1
			let cur_cost = this._cost(categories)
			while (j <= maxneighbor) {
				const swap = Math.floor(Math.random() * n)
				const cur_cat = categories[swap]
				const new_cat = Math.floor(Math.random() * (this._k - 1));
				categories[swap] = (new_cat >= cur_cat) ? new_cat + 1 : new_cat;
				const new_cost = this._cost(categories)
				if (new_cost < cur_cost) {
					j = 1;
					cur_cost = new_cost
					continue
				}
				j++
				categories[swap] = cur_cat
			}
			if (cur_cost < mincost) {
				mincost = cur_cost
			}
			i++
		}
	}

	predict() {
		return this._categories
	}
}