【Golang】Ward法で階層的クラスタリングするパッケージを書いた

背景

言語処理100本ノックのQ98を解くにあたって、Go実装がなかったので実装し、goClusteringというパッケージにしました。k-meansもQ97で実装したので、将来的には他のクラスタリングアルゴリズムも統合するかもしれません。

概要

内部的には、階層構造を二分木で表現し、距離尺度に分散を用いて2つのグループを一つにまとめる操作を再帰で実装しています。 実装はこちら。

可視化には、gonum/plotを用いています。 こちらも樹形図は自前で実装しています。 以下のように可視化できます。

f:id:cipepser:20180407145255p:plain

使い方

READMEにも記載していますが、こちらでも紹介します。

How to Install

go getでインストールします。

go get github.com/cipepser/goClustering/...

可視化でgonum/plotを使うのでこちらもgo getします。

go get gonum.org/v1/plot/...

How to Use

入力はn * dの行列Xです。ここでnは観測データ数、dは特徴ベクトルの次元です。 以下を実行することで、ward.Tree型の結果を得られます。

T := ward.Ward(X)

次にこれを可視化します。

d, _ := plotter.NewDendrogram(T)
p, err := plot.New()
p.Add(d)

図のタイトルや軸名を設定します。

p.Title.Text = "Dendrogram"
p.X.Label.Text = "data"
p.Y.Label.Text = "distance"

葉ノードを設定します。要素が多くなった場合には回転することもできます。

p.NominalX("aaa", "bbb", "ccc", "ddd", "eee", "fff")
p.X.Tick.Label.Rotation = math.Pi / 3
p.X.Tick.Label.YAlign = draw.YCenter
p.X.Tick.Label.XAlign = draw.XRight

Example

package main

import (
    "math"

    "github.com/cipepser/goClustering/ward"
    "github.com/cipepser/goClustering/vis"

    "gonum.org/v1/plot"
    "gonum.org/v1/plot/vg"
    "gonum.org/v1/plot/vg/draw"
)

func main() {
    // input data set
    X := [][]float64{
        {0, 0},
        {2, 2},
        {1, 1},
        {2, -1.2},
        {3, 2.2},
        {3.5, 0.5},
    }

    // Ward's method
    T := ward.Ward(X)

    // draw the dendrogram
    d, err := plotter.NewDendrogram(T)
    if err != nil {
        panic(err)
    }

    p, err := plot.New()
    if err != nil {
        panic(err)
    }
    p.Add(d)

    p.Title.Text = "Dendrogram"
    p.X.Label.Text = "data"
    p.NominalX("aaa", "bbb", "ccc", "ddd", "eee", "fff")

    p.X.Tick.Label.Rotation = math.Pi / 3
    p.X.Tick.Label.YAlign = draw.YCenter
    p.X.Tick.Label.XAlign = draw.XRight

    p.Y.Label.Text = "distance"

    // save as a png file
    file := "img.png"
    if err = p.Save(10*vg.Inch, 6*vg.Inch, file); err != nil {
        panic(err)
    }
}

f:id:cipepser:20180407145255p:plain

References