FoF 알고리즘이란

알고리즘은 매우 간단하고 매개 변수는 하나이며 그것을 문턱값 r로 한다.

공간에 N점이 있을 때 그 중의 어느 한 점에 착안한다. 이 점에서 나머지 N-1점까지의 거리를 계산하면 r이하의 판정은friend이다.

다음에 우리는 다른 방면에 착안하여 같은 계산을 할 것이다. 만약에 이전에 결정한 여자친구와 같은 것이 있다면 여자친구를 추가할 것이다. 공통된 요소가 없다면 우리는 새로운 여자친구족을 생성할 것이다.

이것만 반복한다.

pyfof 설치

pyfofpythn에서 친구 그룹(Friends of Friends cluster finding)을 빠르게 실현하는 프로그램 라이브러리입니다.
설치 시,

pip install pyfof

OK (@Google colab, 2028.19)

실행 예

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import pyfof

npts = 10000
ndim = 2
nptsperdim = int(npts/ndim)
data = np.vstack((np.random.normal(-1,0.2,(nptsperdim,ndim)),\
                  np.random.normal(1,0.2,(nptsperdim,ndim))))

groups = pyfof.friends_of_friends(data, 0.4)

colors = cm.rainbow(np.linspace(0, 1, len(groups)))
for g,c in zip(groups, colors):
    plt.scatter(data[g,0], data[g,1], color=c, s=3)

plt.show() 

이렇게 되면,
R*-tree
이렇게 예쁘게 두 반으로 나눌 수 있다.
다음은 다른 반을 중간에 두는 게 어때요?

npts = 10000
ndim = 2
nptsperdim = int(npts/ndim)
data = np.vstack((np.random.normal(-1,0.2,(nptsperdim,ndim)),\
                  np.random.normal(1,0.2,(nptsperdim,ndim)),\
                  np.random.normal(0.,0.2,(nptsperdim,ndim))))

groups = pyfof.friends_of_friends(data, 0.4) # 0.4 だと大きすぎで，全部同じクラスに分類されてしまう．

colors = cm.rainbow(np.linspace(0, 1, len(groups)))
for g,c in zip(groups, colors):
    plt.scatter(data[g,0], data[g,1], color=c, s=3)

plt.show()

그러면 모두 같은 색깔이다. 즉, 같은 반이 된 것이다.

그럼 범위를 조금만 바꿔주세요.

npts = 10000
ndim = 2
nptsperdim = int(npts/ndim)
# ガウシアンのシグマを小さくする．
data = np.vstack((np.random.normal(-1,0.1,(nptsperdim,ndim)),\
                  np.random.normal(1,0.1,(nptsperdim,ndim)),\
                  np.random.normal(0.,0.1,(nptsperdim,ndim))))

groups = pyfof.friends_of_friends(data, 0.2) # 0.2して少し基準を小さくする．かつ，上のシグマを小さくした．

colors = cm.rainbow(np.linspace(0, 1, len(groups)))
for g,c in zip(groups, colors):
    plt.scatter(data[g,0], data[g,1], color=c, s=3)

plt.show()

보니,

고스인의 시그마를 축소하고 판정 기준을 0.4에서 0.2로 축소했기 때문에 꼬박 세 반으로 나뉘었다.
코드도 열람할 수 있다.