ryamadaのコンピュータ・数学メモ

2013-06-18

k-NN entropy

情報量エントロピー R FNN

NN entropy: Nearest Neighbor entropyは、標本座標が与えられたときに、各標本の最近傍点との距離を用いて標本の母集団のエントロピーを推定する方法のこと
k-NN entropyは最近傍点の代わりに、第k近傍点を用いる方法のこと
標本座標の次元をm、標本数をn、を第i点の第k近傍点までの(ユークリッド)距離、はオイラー定数(0.5772...)、とすると、それは
- $\hat{H}_{n,k} = \frac{m}{n}\sum_{i=1}^n \ln{R_{i,k,n}} + \ln{\frac{\pi^{\frac{m}{2}}}{\Gamma(\frac{m}{2}+1)}} + \gamma -L_{k-1}+\ln{n}$ と計算するという
- もしくは $L_{k-1}-\gamma$ はdigamma(k)であるので
- $\hat{H}_{n,k} = \frac{m}{n}\sum_{i=1}^n \ln{R_{i,k,n}} + \ln{\frac{\pi^{\frac{m}{2}}}{\Gamma(\frac{m}{2}+1)}} - digamma(k)+\ln{n}$
式の参照先

library(FNN)
# m次元データを作る
m <- 2
n.pt <- 100
X <- matrix(rnorm(n.pt*m),ncol=m)
# 点間ユークリッド距離を計算
D <- as.matrix(dist(X))
# 第k-th近傍距離にする(第１列はすべて距離０(自身との距離)になる)
D.sorted <- t(apply(D,1,sort))
# エントロピーの推定式用に、対数にして全点について足し合わせる
sum.kNNdist <- apply(log(D.sorted),2,sum)
# K-th近傍まで計算する
K <- 10
# 計算式
H <- m/n.pt * sum.kNNdist[2:(K+1)] + m/2*log(pi)-lgamma(m/2+1)-digamma(1:K)+log(n.pt)
# FNNパッケージの関数(この関数では近傍は全ペアの距離を計算して求めるのではなく、探索アルゴリズムを用いている)
H.fnn <- entropy(X,k=K)
# 比較する
print(H)
print(H.fnn)