k- W707 1 / 39

Size: px

Start display at page:

Download "k- W707 1 / 39"

このかあると
5 years ago
Views:

1 k- W707 1 / 39

2 7/7 2 / 39

3 k- k- 3 / 39

4 1 k- k- k 2 k- 3 4 / 39

5 k- 5 / 39

6 k- k- 6 / 39

7 1 k- k- k 2 k- 3 7 / 39

8 k- {X i } n i=1 : (d ) k- (k-nearest neighbor) 1 k 1 2 x k {X (1), X (2),..., X (k) } X (k) 3 : ˆp(x) = k nv d x X (k) d. V d d ({x R d x 1}) V d = πd/2 Γ(d/2+1). x ˆp(x) ˆp(x) 8 / 39

9 k- k = 10 k- 9 / 39

10 k- x R S : S := {x R d x x R}. S P : P = p(x )dx. n k S ( ) n P( {X i S} = k) = P k (1 P) n k k [ ] k E = P, Var n S [ ] k = n n P(1 P). n P k n k S 10 / 39

11 R P = ( ) S p(x )dx V (S)p(x) V (S)p(x) k n p(x) k nv (S). R x X (k) k- V d V (S) = V d R d 11 / 39

12 k- knn Density Estimation p(x) x k = 100, n = / 39

13 k- k n = 100 knn Density Estimation knn Density Estimation knn Density Estimation p(x) p(x) p(x) x x x k = 1 k = 10 k = / 39

14 k- k n = knn Density Estimation knn Density Estimation knn Density Estimation p(x) p(x) p(x) x x x k = 1 k = 10 k = / 39

15 k- k n = knn Density Estimation knn Density Estimation p(x) p(x) x x k = 50 k = 500 k 13 / 39

16 1 k- k- k 2 k / 39

17 k- k knn Density Estimation p(x) knn with various k true k=10 k=200 k= x k 15 / 39

18 1 k- k- k 2 k / 39

19 k 1 k- ˆp(x) = k nv d x X (k) d ˆp x (Mean Squared Error) : MSE(ˆp(x), k) := E[(ˆp(x) p(x)) 2 ]. E[ ] {X i } n i=1 Q: k 17 / 39

20 n k MSE(ˆp(x), k) = p2 (x) k + c2 (x) p 4/d (x) ( ) ( 4/d k 1 + o n k + ( ) 1 d + 2 c(x) = 2(d + 2)π Γ2/d Tr[ f (x)]. 2. Biau et al. (2011) k f k 2+4/d (x)d = 4c 2 n 4/(d+4) n 4/(d+4) (x) ( ) ) 4/d k, n MSE(ˆp(x), k ) = O(n 4 d+4 ). ( pdf ) 18 / 39

21 MSE(ˆp(x), k ) = O ( ) n 4 d+4 d 19 / 39

22 1 k- k- k 2 k / 39

23 k- k- 21 / 39

24 k- {(X i, Y i )} n i=1 Rd {1,..., Q} Y i {1, 2,..., Q} Q x Q n 1, n 2,..., n Q : q ( Q q=1 n q = n) 1 x k {(X (1), Y (1) ), (X (2), Y (2) ),..., (X (k), Y (k) )} 2 k x : k q k q ( L q=1 k q = k) ˆq(x) = argmax q=1,...,q k q. 22 / 39

25 x q P(q x) p(x q)p(q) p(x q)p(q) P(q x) = Q = q=1 p(x q)p(q) p(x) p(x q) q p(x) x P(q) q 23 / 39

26 p(x) k- P(q) ( ): p(x q) k- ˆp(x q) = ˆP(q) = n q n. k q n q V d X (k) x d ( X (k) x k q ) ˆP(q x) = ˆp(x q)ˆp(q) ˆp(x) = k q n q V d X (k) nq x d n k nv d X (k) x d = k q k. ˆq(x) 24 / 39

27 k / 39

28 k- 15 nearest neighbour 25 / 39

29 Cross Validation k J-fold 1 J 2 J j I j : {(X i, Y i )} i Ij (j = 1,..., J). 3 ˆf(j) : R d {1, 2,..., Q} j I j 4 Ê(k) : J Ê(k) = 1 1[ˆf (j) (X i ) Y i ]. I j j=1 i I j 5 Ê(k) k 26 / 39

30 d k- ( ): X i,j X i,j /std(x :,j ). V d x X (k) d 27 / 39

31 1 k- k- k 2 k / 39

32 k- R k- knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE): FNN l use.all knn.dist KD k- kknn: kknn k- 29 / 39

33 k = 30 area e+07 4e+07 6e+07 8e+07 price 30 / 39

34 k = 30 0e+00 2e+07 4e+07 6e+07 8e k=30 price area / 39

35 estimated density k = 30 price area 30 / 39

36 estimated density 5e e 10 1e 10 ( ) area area e e 10 4e 10 3e 10 4e e e 10 2e+07 4e+07 6e+07 8e+07 price 0e+00 2e+07 4e+07 6e+07 8e+07 1e+08 price price area 31 / 39

37 1K, 1DK, 1LDK 2LDK k = e+07 4e+07 6e+07 8e area / 39

38 MNIST : , csv 33 / 39

39 / 39

40 k- k = % > res = knn(data.train_origin[,1:dimx], data.test[,1:dimx], data.train_origin[,dimy], k = 10, prob=false) > (clerr = mean(res!=data.test[,dimy])) #0.0335, 96.65% [1] > table(res,data.test[,dimy]) res / 39

41 / 39

42 k- 1 2 k 37 / 39

43 ( ) 1 autopoll.csv 2 x k (λ j ). Yk: k Lk: k (λ 1,..., λ k ) Vk: k 3 R princomp 4 ken-c-kakou.csv zip x <- read.csv("ken-c-kakou.csv",header=true) 5 (optional) 38 / 39

44 n R pdf ( tex ) action=t0300&gakubucd=100&gakkacd=15&kougicd=5522& Nendo=2015&Gakki=1&lang=JA&vid=03 dataanalysis.html 39 / 39

45 G. Biau, F. Chazal, D. Cohen-Steiner, L. Devroye, and C. Rodríguez. A weighted k-nearest neighbor density estimate for geometric inference. Electron. J. Statist., 5: , doi: /11-EJS606. URL 39 / 39

7/7 2 / 34

W707 s-taiji@is.titech.ac.jp 1 / 34 7/7 2 / 34 3 / 34 1 4 / 34 (...) 5 / 34 Kernel Density Estimation (gauss) p(x) 0.0 0.1 0.2 0.3 0.4 0.5 0.6 3 2 1 0 1 2 3 x 6 / 34 O(n) 7 / 34 1 8 / 34 {X i } n i=1 :