FoF(friends of friends) アルゴリズムとは
アルゴリズムは超単純で，パラメータはたった一つで，それを敷居値 r とします．
- 空間内にN点あったときに，その中のとある一点に着目します．その一点から残りのN-1点までの距離を計算して，r 以下のものは friend と判定します．
- 次に，別の一点に着目して同じ計算をします．もし，先に決めたfriendと共通のものがあるなら，friend を追加します．もし，全く共通の要素がなければ，あたらしいfriendの族を生成します．
- これを繰り返すだけです．
pyfofのインストール
pyfof は，フレンド-フレンドクラスタリング (Friends of Friends cluster finding) を python で高速で可能にしたライブラリです．単純に，friends-of-friends algorithm を実装したのではなくて，R*-tree という方法で高速化を可能にしたようです(詳細は把握してません)．
インストールは，
pip install pyfof
だけでOKでした(@ google colab, 2020.8.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()
とすると，
のように，綺麗に２つにクラス分けできます．
次に，もう一つのクラスを真ん中に入れてみるとどうでしょう？
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 に小さくしたためです．
コードは google colab でも閲覧可能です．