1,a) 2 2 2 3 4 2 2014 5 28 2014 7 18, 2014 9 5 Anomaly Detection Based on Density Estimation of Normal Data in Cone-restricted Subspace Yudai Yamazaki 1,a) Hirokazu Nosato 2 Masaya Iwata 2 Eiichi Takahashi 2 Ayumi Izumori 3 Takuji Iwase 4 Hidenori Sakanashi 2 Received: May 28, 2014, Revised: July 18, 2014, Accepted: September 5, 2014 Abstract: A cone-restricted subspace method can express learning patterns accurately by generating a convex cone for non-negative feature vectors. Classification of conventional method is performed based on the angle between the input vector and the cone. However, recognition performance is reduced if the spread of the convex cone is large, because it is impossible to distinguish between vectors near the surface and those around the center of the cone. This paper proposes an anomaly detection method based on probability density of normal data in cone-restricted subspace. Classification by the proposed method is based on the probability contained in the convex cone. We demonstrate anomaly detection from breast ultrasound images using proposed method, and confirmed effectiveness of the method. Keywords: cone-restricted subspace, density estimation, anomaly detection, pattern recognition 1 Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305 8573, Japan 2 Information Technology Research Institute, National Institute of Advanced Industrial Science and Technology, Tsukuba, Ibaraki 305 8568, Japan 3 Department of Surgery, Takamatsu Heiwa Hospital, Takamatsu, Kagawa 760 8530, Japan 4 Breast Oncology Center, The Cancer Institute Hospital of the Japanese Foundation for Cancer Research, Koto, Tokyo 135 8550, Japan 1. a) yamazaki-yudai@aist.go.jp c 2015 Information Processing Society of Japan 28
[1] [2] 0 2. 2.1 [1], [3] HLAC [4] SIFT [5] LBP [6] [2] 2.2 D C N C = {x x = α i ξ i =Ξα,α i 0} (1) i=1 where Ξ = {ξ 1, ξ 2,...,ξ N } α = {α 1,α 2,...,α N } T N ξ i R D α i S N S = {x x = α i ξ i =Ξα} (2) i=1 (1) (2) C S α i 2.3 y C θ θ 1 y C x c 2015 Information Processing Society of Japan 29
Fig. 1 1 Angle between the input vector and the cone. θ = arcsin(min y x / y ) x C N / =arcsin min y α i ξ i 2 y (3) α i 0 i=1 (3) min αi 0 y N i=1 α iξ i 2 [7] y C y ξ i (3) y = N i=1 α iξ i θ 0 Algorithm 1 C input :X =[x 1,...,x M ](M ) :θ th ( 0) initialize :t 0 C :C X C N t :N 0 M repeat step1 X X S X S step2 x i X S X S x i C Sī θ i θ i <θ th X X S x i step3 x j X S X S C S θ j θ j <θ th X x j step4 :t t +1 C :C X C N :N t [X ] until (N t = N t 1 ) output :C θ 0 θ π 2 2.4 [2] 3 X Algorithm 1 C (3) θ th 0 2.5 (3) 2 y 1 y 2 C 0 2 Fig. 2 Feature vectors in cone. 1 [2] (3) 3. c 2015 Information Processing Society of Japan 30
3 Fig. 3 Flowchart of proposed method. Fig. 4 4 Space that represents the spread direction of cone. 3 3 3.1 N X =[x 1,...,x N ] x i D 1 ˆx i = x i x i (i =1,...,N) ˆX =[ˆx 1,...,ˆx N ] R ˆX R ˆX = ˆX ˆX T R ˆX R ˆXU = UΛ U = {u 1,...,u D } u i Λ =diag λ 1,...,λ D λ i 1 u 1 2 U E U E = {u 2,...,u M+1 } (1 M D 1) U E M M 4 3 D =3 2 M =2 3.2 1 [8] ˆx i x E i x E i = UE T ˆx i (i =1,...N) p(t) c 2015 Information Processing Society of Japan 31
p(t) = 1 N N i=1 where k(x) = 1 h M k( t xe i h ) (4) 1 (2π) M/2 exp( 1 2 xt x) t M h k(x) k(x) h M M h M h 4.2.2 4.3.2 3.3 (4) y y E y E = UE T ŷ where ŷ = y y y E p(y E ) p th 4. 2 (1) 3 2 (2) 4.1 ROC Receiver Operating CharacteristicROC False Positive Rate True Positive Rate ROC 100% 0% ROC AUC Area Under the Curve AUC ROC 1 0.5 4.2 3 2 1 2 3 3 4.2.1 2 5 (a) 1 (x, y, z) =(1, 1, 1), (2, 1, 2) μ =(0, 0) σ 2 =0.5 5(b) 6 (a) 2 1 6(b) 1000 1000 1000 4.2.2 1 2 ROC 7 (a) 7(b) 1 M =2 h =0.25 2 M =2 h =0.2 M =2 h 0.01 20 0.01 AUC 1 1 3 0.5 1 2 AUC c 2015 Information Processing Society of Japan 32
情報処理学会論文誌 数理モデル化と応用 Vol.8 No.1 28 37 (Mar. 2015) 図 5 人工データ 1 凸形状の錐 Fig. 5 Synthetic dataset1: Convex cone. 図 6 人工データ 2 非凸形状の錐 Fig. 6 Synthetic dataset2: None convex cone. 図 7 人工データに対する ROC 曲線 Fig. 7 ROC curve of synthetic dataset. 錐制約部分空間法では 錐の中に含まれる特徴ベクトルと 次に 人工データ 2 を用いたときの結果について述べる 錐とのなす角度がすべて 0 となり 錐の中にある異常デー 比較手法 1 と 2 では真陽性率が 1 に達することはなく 異 タをすべて正常として判定し 異常を見落としてしまった 常の見落としが発生している 両手法ともに錐の表面付近 ことが原因である と中心付近を区別できなかったためであると推察される c 2015 Information Processing Society of Japan 33
3 1 2 AUC AUC 2 1 3 AUC 1 2 AUC Fig. 8 8 Example of the breast ultrasound image. 4.3 16 1 [9], [10] [11], [12] 2 1 2 1 2 1 2 2 ROC 4.2 3 4.3.1 256 800 600 30 fps 8 7 A G 50 50 1 9 Fig. 9 Examples of experiment data. 1 Table 1 Number of samples in each patients. A 4167 976 2 B 3180 50 1 C 3098 70 1 D 3811 79 1 E 2411 63 1 F 662 69 1 G 4712 56 1 22041 1363 9 9 (a) 9(b) 1 Higher-order Local Autocorrelation; HLAC [4] 2 1 2 HLAC 4.3.2 7 10000 HLAC c 2015 Information Processing Society of Japan 34
1000 1363 M =1 h =0.25 M 1 34 h 0.01 20 0.01 AUC 10 1 2 1 1 3 0.6 1 2 11 (a) 2 11 (b) 11 (b) 11 (a) 2 11 (b) 4.3.3 7 6 1 AUC 2 2 1 AUC 2 AUC 1 2 AUC Fig. 10 10 ROC ROC curves of achieved by the proposal method and comparison methods. 11 Fig. 11 Examples of tumor images. 2 Table 2 AUC AUC values in each patients. 1 2 3 1 2 1 2 1 2 1 2 A 0.93 0.93 0.90 0.85 0.93 0.93 0.93 0.93 B 0.50 0.47 0.65 0.58 0.74 0.74 0.77 0.75 C 0.72 0.70 0.56 0.49 0.60 0.59 0.76 0.73 D 0.83 0.83 0.83 0.82 0.91 0.91 0.91 0.91 E 0.49 0.49 0.29 0.24 0.22 0.21 0.61 0.51 F 0.76 0.75 0.79 0.73 0.78 0.78 0.86 0.82 G 0.59 0.58 0.57 0.54 0.70 0.69 0.83 0.81 c 2015 Information Processing Society of Japan 35
12 Fig. 12 Tumor images of different patients. AUC A E AUC 12 (a) 12 (b) A E HLAC E 5. 2 local autocorrelation feature extraction for classification of histopathological images, IPSJ Trans. CVA, Vol.3, pp.211 221 (2011). [4] Otsu, N. and Kurita, T.: A new scheme for practical flexible and intelligent vision systems, pp.431 435 (1988). [5] Lowe, D.: Object recognition from local scale-invariant features, Proc. 7th IEEE International Conference on Computer Vision, Vol.2 (1999). [6] Ojala, T., Pietikäinen, M. and Harwood, D.: A comparative study of texture measures with classification based on featured distributions, Pattern recognition, Vol.29, pp.51 59 (1996). [7] Bro, R. and De Jong, S.: A fast non-negativityconstrained least squares algorithm, Journal of chemometrics, Vol.11, No.5, pp.393 401 (1997). [8] Silverman, B.W.: Density estimation for statistics and data analysis, Vol.26, CRC press (1986). [9] 1958 2012 http://ganjoho.jp/professional/statistics/ statistics.html. [10] 1975 2008 http://ganjoho.jp/professional/ statistics/statistics.html. [11] Journal of N.D.I Vol.60, No.12, pp.686 693 (2011). [12] CAD JABTS Journal of breast and thyroid sonology Vol.2, No.3, pp.18 24 (2013). 1989 2012 2014 3 4 [1] Nanri, T. and Otsu, N.: Unsupervised abnormality detection in video surveillance, MVA, pp.574 577 (2005). [2] D Vol.92, No.1, pp.104 111 (2009). [3] Nosato, H., Kurihara, T., Sakanashi, H., Murakawa, M., Kobayashi, T., Furuya, T., Higuchi, T., Otsu, N., Terai, K. and Hiruta, N.: An extended method of higher-order c 2015 Information Processing Society of Japan 36
1975 2003 2006 2011 2007 1965 1993 1993 1994 1994 1954 1981 1987 1989 1996 2003 2005 2011 1996 1998 1963 1993 3 4 IEEE 1969 1995 2005 2010 2011 13 2011 Best English Paper of the Year c 2015 Information Processing Society of Japan 37