クラスタリングとゆらぎ

似たような集団を分類するクラスタリングというアルゴリズムおもしろそうなので実装してみます。

マップ上にランダムな点を打って、分類するための開始点を分類したい数だけ設定します。
すべての点を開始点のどれか近いものに振り分けます。
振り分けられたらそのグループの重心点を決めます。
次はその重心点に近いものを新しく開始点にします。
それを繰り返していくとそれらしい分類ができます。
動かなくなったら終了のようです。

実装は端末の80x24の大きさにテキストで描くことにします。
点が重なったり、開始点が重なったりすると、
ゼロ割が発生するパターンがあるようなので重ならないように修正

また点をすべてランダムにするとただの縞模様になるようなので
指定位置から半径Rに打つというグループを開始点と同じ数作ってみました。

作成プログラムの開始点は実は同じ一つのグループから開始していますが分類できてます。
しかし、うまく分類できないパターンがあります。
とある開始点が別の開始にうまくかぶさって通せんぼしてしまい
結果共倒れして、漁夫の利を得た開始点が勢力を張るという。パターンも多いです。

そこで重心点の判断にゆらぎを加えてみました。
ゆらぎは単にランダムで重心点の判断をしないというだけのものですが
うまく行ったようです。

実行結果とソースです。
ubuntu18.04の端末80x24のサイズで動くように作成しています。
Python 3.6.5環境で作成していますが、特に新しい何かを使っているわけでもないので
python2でも動くのではないかと思います、

import random
import time

yuragi=3 #1から10 10は揺らがない

def put(x,y,st,m):
    m[y]=m[y][:x]+st+m[y][x+1:]

def write(m,s,c):
    global w,h
    m=[" "*w for i in range(h)]
    for i in s:
        x,y,d=i
        put(x,y,d,m)
    for i in c:
        x,y,d=s[i]
        put(x,y,"*",m)

    for i in m:print(i)

def getCenter(c):
    for i in range(len(c)):
        ax=0
        ay=0
        ac=0
        cn=str(i)
        for j in range(len(star)):
            x,y,d=star[j]
            if d==cn:
                ax+=x
                ay+=y
                ac+=1
        while 1:
            p=nearB(int(ax/ac),int(ay/ac))
            sw=1
            for k in range(i):
                if c[k]==p:
                    sw=0
            if sw==1:
                c[i]=p
                break

def nearB(nx,ny):
    global yuragi
    bl=100000
    bi=-1
    for i in range(len(star)):
        if random.randint(0,10)>yuragi:continue
        x,y,d=star[i]
        l=(nx-x)**2+(ny-y)**2
        if bl>l:
            bl=l
            bi=i
    return bi

def checkAppend(c):
    x,y,_=c
    for i in star:
        sx,sy,_=i
        if sx==x and sy==y:return
    star.append(c)

def reset(c):
    for i in range(len(star)):
        x,y,d=star[i]
        bl=100000
        bi=-1
        for j in range(len(c)):
            cx,cy,_=star[c[j]]
            l=(cx-x)**2+(cy-y)**2
            if bl>l:
                bl=l
                bi=j
        star[i]=(x,y,str(bi))
def circle(x,y,r,n):
    for i in range(n):
        checkAppend((x+random.randint(0,r*2)-r,y+random.randint(0,r*2)-r,"*"))

w,h=80,23
star=[]
sc=[" "*w for i in range(h)]
c=[0,1,2,3]

circle(10,15,5,8)
circle(45,5,5,16)
circle(70,15,7,8)
circle(35,15,5,8)

bc=""
for i in range(200):
    reset(c)
    getCenter(c)
    write(sc,star,c)
    tc=" ".join(str(i) for i in c)
    #if tc==bc:break
    bc=" ".join(str(i) for i in c)
    time.sleep(1)

syntax2html