アドベントカレンダー日記13日目階層型クラスタリングの ASCII 描画

f:id:p1sces:20211213183641p:plain

本日データマイニングのテストがありました．紙面が半分も埋まらなかったです．その中で2変数データ列の complete linkage 階層型クラスタリングのグラフを書けという問題がありました．書けなかったんですけども．

ハフマン木みたいなイメージです．その場その場で小さいもの2つまとめて1つにする作業を残りひとつになるまでやります．テストにもっていってた PC にRの環境がなかったんで julia で必要そうなpackageを探すこと10分くらい， Distances.jl と Clustering.jl を見つけました． Distances.jl には pairwise，Clustering.jl には hclust まさに欲しい関数でした．

pairwise でデータ間の距離を取り，その結果で hclust が組まれます. しかし，この Hclust の Field, merges がよくわからなかった．こいつがどのように組まれているのかを示しています．

Hierarchical Clustering · Clustering.jl

に書いてある通りなんですけど頭が死んでいたので読めませんでした．

[-2 -5; -4 -6; -3 1; -1 3; 2 4]

merges はこんな感じで書かれています．負の値は葉となる元のデータ列のindex，正の値はすでに組まれた木のindexのことで， -3 1 の 1 は merges の1番目の -2 -5 で組まれた木の部分を指します．これが分かればなんとなく頭の中で木の構造が思い浮かべますね．

この問題が試験時間中にできなかったのが嫌で，その後はずっとこの木を表示することを考えていました．

でその結果がこれです．

f:id:p1sces:20211213191511p:plain

ちゃんとなってますね．コードはこれ．

# LICENSE CC0 https://creativecommons.org/publicdomain/zero/1.0/deed.ja
function htree(con::M; spl=2) where M <: Matrix
    conl = size(con)[1]

    tree = []
    for i in 1:conl
        l,r = con[i,:]
        lv,rv = map(x -> typeof(x) <: Signed && x > 0 ? tree[x] : x, con[i,:])
        push!(tree, (lv, rv))
    end

    vals = []
    ss = Any[(tree[end])]
    while !isempty(ss)
        s = pop!(ss)
        if typeof(s) <: Tuple
            push!(ss, s[2])
            push!(ss, s[1])
        else
            push!(vals, s)
        end
    end

    centers = []
    els = [0]
    sps = repeat(" ", spl)
    for v in vals
        print(v, sps)
        push!(centers, els[end] + length(string(v))÷2+1)
        push!(els, els[end] + length(string(v))+spl)
    end
    popfirst!(els)

    println()

    for i in 1:conl
        lc = 0
        for c in centers
            print(repeat(" ", c-lc-1), "|")
            lc = c
        end
        println()
        ind = 0
        j = 1
        lc = 0
        nvals = []
        ncenters = []
        while j <= length(centers)
            if con[i] == vals[j]
                c1 = centers[j]
                c2 = centers[j+1]
                print(repeat(" ", c1-lc-1))
                print(repeat("-", c2-c1 + 1))
                lc = c2
                push!(nvals, i)
                push!(ncenters, ((c2-c1)÷2 + c1))
                j += 1
            else
                c = centers[j]
                print(repeat(" ", c-lc-1), "|")
                lc = c
                push!(nvals, vals[j])
                push!(ncenters, centers[j])
            end
            j += 1
        end
        println()
        vals = nvals
        centers = ncenters
    end
end

やってることはシンプルです．本当はそれぞれの2つ合わさった値とか書きたいところですが，計算が面倒になるのでやめておきましょう． merges で正の値がすでに組まれた木を示すので，それ以外は葉となるようにしました．このプログラム初心者が取り組むのにいい問題っぽいですよね．

Julia は書くのが楽しい．

今日の日記は以上です．

f:id:p1sces:20211213192601p:plain

おさかなせいざ

プログラミングメモや日記がわりに

アドベントカレンダー日記13日目階層型クラスタリングの ASCII 描画