実践的な Golang の基本データ構造とアルゴリズム、k-means クラスタリングアルゴリズム

起源

最近読んだ本『はじめてのアルゴリズム』(石田康樹、宮崎修一)

この一連のノートは、Golangの実践を目的としたものです

k平均法クラスタリングアルゴリズム

クラスタリングとは、入力データが複数ある場合に、「類似した」データを 1 つのグループにまとめる操作です。 k-means アルゴリズムはクラスタリングアルゴリズムです。まず、クラスターの中心点としてランダムに k 個の点を選択し、「データを対応するクラスターに分割する」と「中心点を重心に移動する」という 2 つの操作を、中心点が変化しなくなるまで繰り返します。 k-means アルゴリズムでは、演算を繰り返すと中心点の位置がどこかに収束することが数学的に証明されています。石田康樹、宮崎修一著『はじめてのアルゴリズム』より抜粋

シナリオ

ある場所で突如として新型コロナウイルス感染症が発生しました。感染者の分布状況から、感染源の特定を急ぐことが防疫上急務となっています。
まず、ケース分布の座標をシステムに入力します
次に、k-meansアルゴリズムに従って、1から3までのkに応じてクラスタリングが実行されます。
クラスターの中心が病気の発生源である可能性がある

プロセス

サンプル数とサンプル距離計算機が与えられた場合、k 個のサンプル中心点を見つける必要があります。
まず、サンプルからk点をランダムに選択して中心点とする。
各サンプルをループする
1. サンプル点からk個の中心点までの距離をそれぞれ計算する
2. サンプルポイントからの距離が最小の中心点を決定する
3. サンプルを最小の中心点を持つクラスターに分割する
各クラスターの中心点を新しい中心点として計算する
1. クラスター内の各サンプルをループする
2. このサンプルからこのクラスター内の他のサンプルまでの距離の合計を計算します
3. 他のサンプルとの距離が最も短い点が新しい中心点となる
中心点が変化しなくなり計算が完了するまで、3～4を繰り返します。

デザイン

IPoint: サンプルポイントインターフェイス (実際には空のインターフェイス)
IDistanceCalculator: 距離計算インターフェース
IClassifier: 分類器インターフェース。サンプルを k にクラスタ化し、k の中心点を返します。
tPerson: ケースサンプルポイント、IPoint インターフェースを実装、x、y 座標を含む
tPersonDistanceCalculator: ケース距離計算機。x 座標と y 座標の 2 点間の直線距離を計算します。
tKMeansClassifier: k-means クラスタラー。IClassifier インターフェイスを実装します。

ユニットテスト

k_means_test.go

その他をパッケージ化する
輸入（
    km 「学習/gooop/その他/k_means」
 「文字列」
 「テスト」
 ）
関数Test_KMeans(t *testing.T) {
 // サンプルポイントを作成する
    サンプル:= []km.IPoint {
        km.NewPerson( 2 , 11 )、
        km.NewPerson( 2 , 8 )、
        km.NewPerson( 2 , 6 )、
        km.NewPerson( 3 , 12 )、
        km.NewPerson( 3 , 10 )、
        km.NewPerson( 4 , 7 )、
        km.NewPerson( 4 , 3 )、
        km.NewPerson( 5 , 11 )、
        km.NewPerson( 5 , 9 )、
        km.NewPerson( 5 , 2 )、
        km.NewPerson( 7 , 9 )、
        km.NewPerson( 7 , 6 )、
        km.NewPerson( 7 , 3 )、
        km.NewPerson( 8 , 12 )、
        km.NewPerson( 9 , 3 )、
        km.NewPerson( 9 , 5 )、
        km.NewPerson( 9 , 10 )、
        km.NewPerson( 10 , 3 )、
        km.NewPerson( 10 , 6 )、
        km.NewPerson( 10 , 12 )、
        km.NewPerson( 11 , 9 )、
    }
    fnPoints2String := func(points []km.IPoint) 文字列 {
        アイテム:= make([]文字列、len(ポイント))
 i ,it := 範囲ポイント {
            アイテム[i] = it.String()
        }
文字列を返します。Join (items, " " )
    }
 k:= 1 ;k<= 3 ;k++の場合
        センター:= km.KMeansClassifier.Classify(サンプル、 km.PersonDistanceCalculator、 k)
        t.Log(fnPoints2String(中心))
    }
 }

テスト出力

$ テストを実行 -v k_means_test.go
 === Test_KMeans を実行
    k_means_test.go: 53 : p( 7 , 6 )
    k_means_test.go: 53 : p( 5 , 9 ) p( 7 , 3 )
    k_means_test.go: 53 : p( 9 , 10 ) p( 3 , 10 ) p( 7 , 3 )
 --- 合格: Test_KMeans ( 0.00 秒)
合格
ok コマンドライン引数0.002s

アイポイント

サンプルポイントインターフェースは実際には空のインターフェースです

パッケージキロ
「fmt」をインポートする
IPointインターフェース型{
    fmt.ストリンガー
}

IDistanceCalculator.go

距離計算インターフェース

パッケージキロ
IDistanceCalculatorインターフェース型{
    Calc(a, b IPoint) int
 }

IClassifier.go

分類器インターフェース、サンプルをkにクラスタ化し、kの中心点を返す

パッケージキロ
IClassifierインターフェース型{
 //サンプルをk個のクラスターにクラスタ化し、k個の中心点を返す
    分類(サンプル[]IPoint、calc IDistanceCalculator、k int )[]IPoint
 }

tPerson.go

ケースサンプルポイント、IPointインターフェースを実装、x、y座標を含む

パッケージキロ
「fmt」をインポートする
tPerson構造体型{
    x整数
    y整数
}
 NewPerson関数(x, y int ) IPoint {
 &tPerson{x, y, }を返す
}
 func (me *tPerson) String() 文字列 {
 fmt.Sprintf( "p(%v,%v)" , me.x, me.y)を返します。
 }

tPersonDistanceCalculator.go

ケース距離計算機、x 座標と y 座標の 2 点間の直線距離を計算します

パッケージキロ
tPersonDistanceCalculator構造体型{
 }
 var gMaxInt = 0x7fffffff_ffffffff
 func newPersonDistanceCalculator() IDistanceCalculator {
 &tPersonDistanceCalculator{}を返します。
 }
 func (me *tPersonDistanceCalculator) Calc(a, b IPoint) int {
 a == bの場合{
 0を返す
    }
    p1、OK := a.(*tPerson)
 !okの場合{
 gMaxIntを返す
    }
    p2、OK := b.(*tPerson)
 !okの場合{
 gMaxIntを返す
    }
    dx := p1.x - p2.x
    dy := p1.y - p2.y
    d := dx*dx + dy*dy
 d < 0 の場合{
        パニック
    }
戻るd
 }
 var 人物距離計算機 = 新しい人物距離計算機()

tKMeansClassifier.go

k-means クラスタラー。IClassifier インターフェイスを実装します。

パッケージキロ
輸入（
 「数学/ランド」
 "時間"
 ）
 tKMeansClassifier構造体型{
 }
 tPointEntry構造体型{
    ポイント IPoint
    距離int
    インデックスint
 }
 func newPointEntry(p IPoint, d int , i int ) *tPointEntry {
 &tPointEntry{を返す
        p、d、i、
    }
 }
関数 newKMeansClassifier() IClassifier {
 &tKMeansClassifier{}を返す
}
 //サンプルをk個のクラスターにクラスタ化し、k個の中心点を返す
func (me *tKMeansClassifier) Classify(samples []IPoint, calc IDistanceCalculator, k int ) []IPoint {
    サンプル数:= len(サンプル数)
サンプル数 <= kの場合
サンプルを返却する
    }
 // 初期化、k 個の中心点をランダムに選択
    rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
    中心 := make([]IPoint, k)
選択された場合、i:= make(map[ int ]bool, 0 ), 0 ;i < k; {
        n := rnd.Intn(サンプル数)
        _,ok := 選択[n]
 !okの場合{
            選択された[n] = true
            センター[i] = サンプル[n]
            私は++
        }
    }
 // 中心点までの距離に応じてサンプルを分割します
のために{
        グループ := me.split(サンプル、センター、計算)
        新しい中心点:= make([]IPoint, k)
 i ,g := 範囲グループ {
            新しい中心[i] = me.centerOf(g, calc)
        }
 me.groupEquals(centers, newCenters)の場合{
返品センター
        }
        センター = newCenters
    }
 }
 // サンプルポイントと中心点の間の距離をクラスター化します
func (me *tKMeansClassifier) split(samples []IPoint, centers []IPoint, calc IDistanceCalculator) [][]IPoint {
    k := len(中心)
    結果:= make([][]IPoint, k)
 i := 0 ;i<k;i++ {の場合
        結果[i] = make([]IPoint, 0 )
    }
    エントリ := make([]*tPointEntry, k)
 i ,c := 範囲の中心 {
        エントリ[i] = newPointEntry(c, 0 , i)
    }
 _ ,p := 範囲サンプル {
 for _,e := 範囲エントリ {
            e.距離 = calc.Calc(p, e.ポイント)
        }
        中心 := me.min(エントリ)
        結果[センター.インデックス] = append(結果[センター.インデックス], p)
    }
結果を返す
}
 // サンプルのクラスターの重心を計算します。重心は、すべてのポイントまでの距離の合計が最小のポイントです。
 func (me *tKMeansClassifier) centerOf(samples []IPoint, calc IDistanceCalculator) IPoint {
    エントリ:= make([]*tPointEntry, len(サンプル))
 i ,src := 範囲サンプル {
        距離:= 0
 _ ,it := 範囲サンプル {
            距離 += calc.Calc(src, it)
        }
        エントリ[i] = newPointEntry(src, 距離, i)
    }
 me.min(entries).pointを返す
}
 // 2つの点の集合が同じかどうかを判定する
func (me *tKMeansClassifier) groupEquals(g1, g2 []IPoint) bool {
 len(g1) != len(g2)の場合{
偽を返す
    }
 i ,v := 範囲 g1 {
 g2[i] != v の場合
偽を返す
        }
    }
真を返す
}
 // 距離が最小の点を見つける
func (me *tKMeansClassifier) min(entries []*tPointEntry) *tPointEntry {
    最小値:= 0
    minD := gMaxInt
 i ,it := 範囲エントリ {
 it.distance < minD {の場合
            最小I = i
            minD = it.距離
        }
    }
エントリを返す[minI]
 }
 var KMeansClassifier = newKMeansClassifier()