Help us understand the problem. What is going on with this article?

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)

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

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

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

コード

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
    }
}
norimy
趣味:プログラミング、好きな言語:c++、興味のある事柄:AI/機械学習
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away