## Guang-Ho Cha## |

Original, d = 30 | LPCA | KPCA | ||||
---|---|---|---|---|---|---|

Tau | AVRR/IAVRR | Precision | Tau | AVRR/IAVRR | Precision | |

95%, d = 14 | 0.41 | 3.50 | 0.60 | 0.69 | 3.15 | 0.71 |

90%, d = 10 | 0.37 | 3.75 | 0.56 | 0.64 | 3.30 | 0.66 |

85%, d = 9 | 0.36 | 3.80 | 0.51 | 0.61 | 3.45 | 0.62 |

Table 2.

Original, d = 80 | LPCA | KPCA | ||||
---|---|---|---|---|---|---|

Tau | AVRR/IAVRR | Precision | Tau | AVRR/IAVRR | Precision | |

95%, d = 30 | 0.45 | 3.48 | 0.59 | 0.61 | 3.27 | 0.69 |

90%, d = 25 | 0.42 | 3.45 | 0.54 | 0.06 | 3.27 | 0.64 |

85%, d = 22 | 0.39 | 3.68 | 0.50 | 0.58 | 3.35 | 0.61 |

Table 3.

Original, d = 35 | LPCA | KPCA | ||||
---|---|---|---|---|---|---|

Tau | AVRR/IAVRR | Precision | Tau | AVRR/IAVRR | Precision | |

95%, d = 15 | 0.42 | 3.63 | 0.57 | 0.62 | 3.35 | 0.68 |

90%, d = 11 | 0.40 | 3.73 | 0.51 | 0.60 | 3.47 | 0.61 |

85%, d = 10 | 0.37 | 3.85 | 0.52 | 0.59 | 3.45 | 0.61 |

Table 4.

Original, d = 256 | LPCA | KPCA | ||||
---|---|---|---|---|---|---|

Tau | AVRR/IAVRR | Precision | Tau | AVRR/IAVRR | Precision | |

95%, d = 164 | 0.42 | 3.63 | 0.57 | 0.62 | 3.35 | 0.68 |

90%, d = 113 | 0.40 | 3.73 | 0.51 | 0.60 | 3.47 | 0.62 |

85%, d = 77 | 0.37 | 3.85 | 0.50 | 0.59 | 3.45 | 0.61 |

To estimate objectively the performance of KPCA, we regard the concept of query as the category of image sets in which the digit character image is included, that is, one of the labels from “0” to “9” are assigned to each category of digit images.

We also assess the performance of precision of k-NN queries, where k is from 10 to 100, and calculate the precision by the ratio of the number of objects returned that are included in the query object category to the returned k objects.

We conduct k-NN queries 100 times and average the results. From MNIST database, the query objects (images) are selected randomly. We show results of 100-NN queries in Figs. 4–9 to assess the performance of KPCA. The experimental results using single query images were presented in Figs. 4 and 5. The query image is shown in the top-left corner. As shown in Fig. 5, there are actually many digit images not “9” when we used the LPCA algorithm. As shown in Fig. 4 where KPCA is applied, there are only two result images other than the query image (digit “9”). This result of experiments demonstrates the supremacy of KPCA. The results of multi-object queries are shown from Fig. 6 to Fig. 9 where we use two-digit images as query objects. Two query objects are shown in the top-left. The first query uses digit “4” as an input query image. In the second query, two images with digits “0” and “6” are used as query images. For this kind of multi-object queries, we adopt the aggregate similarity metric used in FALCON [23] in which the α constant is chosen as -3. From Fig. 6 to Fig. 9, it is shown that there are several digit images other than the query objects when we adopt the LPCA algorithm. However, the KPCA algorithm returns the uniform result and the precision is 99%. In this multi-object query, KPCA also demonstrates a better result.

Figs. 10 and 11 compare the performance of precision between KPCA and LPCA for single-point and multi-point queries, respectively. Fig. 10 shows that KPCA achieves more than the precision of 90% for k-NN queries, on the other hand, LPCA could not achieve this performance. As shown in Fig. 11 for precisions for multi-object k-NN queries, KPCA performs more than the precision of 80% in any case, on the other hand, LPCA could not achieve this efficiency.

In order to assess the statistical significance on the performance (i.e., the precision) superiority of KPCA to LPCA, we also conduct the paired t-test for the average precisions for KPCA and LPCA. Some symbols used for the paired t-test are defined as follows, where all k-NN queries are processed 100 times randomly and k = 10, 20, …,100:

[TeX:] $$a_{i} \text { and } b_{i}$$ for [TeX:] $$1 \leq i \leq 10:$$ average precisions of KPCA and LPCA, respectively.

[TeX:] $$a^{\prime} \text { and } b^{\prime} \text { : }$$ means of samples [TeX:] $$a_{i} \text { and } b_{i},$$ respectively.

[TeX:] $$m_{1}(=10) \text { and } m_{2}(=10) :$$ number of samples come out of average k-NN query precisions of KPCA and LPCA, respectively.

[TeX:] $$\alpha^{\prime 2} :$$ the population variance estimator and is defined by

[TeX:] $$\alpha^{\prime 2}=\frac{1}{m_{1}+m_{2}-2}\left(\sum_{i=1}^{m_{1}}\left(a_{i}-a^{\prime}\right)^{2}+\sum_{i=1}^{m_{2}}\left(b_{i}-b^{\prime}\right)^{2}\right)$$

We also make some assumptions as follows:

The populations of two techniques (that is, average precisions calculated from KPCA and LPCA) follow the normal distribution.

The variances of the two populations are the same.

We define the hypothesis to examine the average precision difference between KPCA and LPCA as follows:

[TeX:] $$T_{0}$$ is rejected with the significance level 5%, in other words, [TeX:] $$\theta_{1}>\theta_{2}$$ is justified if [TeX:] $$t \geq t_{m 1+m 2-2}(0.10)$$ in the t-distribution table.

t and [TeX:] $$t_{n 1+n 2-2}(0.10)$$ are calculated in our experiments as follows:

[TeX:] $$t=3.116 \text { for Fig. } 10, t=2.358 \text { for Fig. } 11 \text {, and } t_{m 1+m 2-2}(0.10)=1.732 \text {. }$$

Thus, in all cases, [TeX:] $$t \geq t_{m 1+m 2-2}(0.10)$$ and it is concluded that the performance of KPCA with respect to precision is better than that of LPCA.

This paper presents the superiority of KPCA to LPCA for feature extraction and dimensionality reduction in CBMR and the potential of the kernel trick. With the use of Gaussian radial basis kernel, it is demonstrated that KPCA can be used to extract nonlinear embeddings and is successively utilized for dimensionality reduction in high-dimensional feature spaces of large media databases. Compared to LPCA, KPCA demonstrated its superior performance with regard to not only the retrieval precision but also the retrieval quality in CBMR. Thus, it can be concluded that KPCA can be adopted effectively to nonlinearly extend the functionality LPCA.

Compared with other algorithms for nonlinear feature extraction, KPCA has merits that it only requires the solution for the eigenvector problem. Different kernels such as gaussian, sigmoid, and polynomial can lead to fine classification performances [18].

LPCA is actually widely used in many domains such as CBMR (i.e., image indexing and retrieval systems), the natural image analysis, density estimation, and noise reduction. KPCA can be employed to all applications where traditional LPCA has been successfully employed and where a nonlinear extension of feature extraction is needed.

He received the Ph.D. degree in computer science from the Korea Advanced Institute of Science and Technology, Daejeon, South Korea, in 1997. From 1999 to 2000, he was a visiting scientist at the IBM Almaden Research Center, San Jose, CA. He is currently a full professor in the Department of Computer Science and Engineering at the Seoul National University of Science and Technology, Seoul, South Korea. His research interests include content-based media indexing and retrieval, data mining, similarity search, and data management on new hardware.

- 1 W. Ahmad, R. Ali, "Information retrieval from social networks: a survey," in
*Proceedings of 2016 3rd International Conference on Recent Advances Information Technology (RAIT)*, Dhanbad, India, 2016;pp. 631-635. custom:[[[-]]] - 2 N. Beckmann, H. P. Kriegel, R. Schneider, B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles,"
*in Proceedings of the 1990 ACM SIGMOD International Conference on Management of DataAtlantic City, NJ*, pp. 322-331, 1990.custom:[[[-]]] - 3 A. W. C. Fu, P. M. S. Chan, Y. L. Cheung, Y. S. Moon, "Dynamic VP-tree indexing for n-nearest neighbor search given pair-wise distances,"
*The VLDB Journal*, vol. 9, no. 2, pp. 154-173, 2000.doi:[[[10.1007/PL00010672]]] - 4 S. S. Lee, M. Shishibori, C. Y. Han, "An improvement video search method for VP-tree by using a trigonometric inequality,"
*Journal of Information Processing Systems*, vol. 9, no. 2, pp. 315-332, 2013.doi:[[[10.3745/JIPS.2013.9.2.315]]] - 5 I. Kamel, C. Faloutsos, "Hilbert R-tree: an improved R-tree using fractals," in
*Proceedings of 20th International Conference on V ery Large Data Bases*, Santiago de Chile, Chile, 1994;pp. 500-509. custom:[[[-]]] - 6 G. H. Cha, C. W. Chung, "A new indexing scheme for content-based image retrieval,"
*Multimedia Tools and Applications*, vol. 6, no. 3, pp. 263-288, 1998.doi:[[[10.1023/A:1009608331551]]] - 7 R. Weber, H. J. Schek, S. Blott, "A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces," in
*Proceedings of 24rd International Conference on V ery Large Data Bases*, New York City, NY, 1998;pp. 194-205. custom:[[[-]]] - 8 G. H. Cha, X. Zhu, P. Petkovic, C. W. Chung, "An efficient indexing method for nearest neighbor searches in high-dimensional image databases,"
*IEEE Transactions on Multimedia*, vol. 4, no. 1, pp. 76-87, 2002.custom:[[[-]]] - 9 A. Andoni, P. Indyk, "Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,"
*Communications of the ACM*, vol. 51, no. 1, pp. 117-122, 2008.doi:[[[10.1145/1327452.1327494]]] - 10 A. Andoni, P. Indyk, "Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,"
*in Proceedings of 2006 47th Annual IEEE Symposium on Foundations of Computer ScienceBerkeley, CA*, pp. 459-468, 2006.doi:[[[10.1145/1327452.1327494]]] - 11 I. Jolliffe,
*in Encyclopedia of Statistics in Behavioral Science*, UK: John Wiley & Sons, Chichester, 2005.custom:[[[-]]] - 12 J. Lever, M. Krzywinski, N. Altman, "Points of significance: principal component analysis,"
*Nature Methods*, vol. 14, no. 7, pp. 641-643, 2017.custom:[[[-]]] - 13 G. Srang,
*Introduction to Linear Algebra, 5th ed*, MA: Wellesley-Cambridge Press, Wellesley, 2016.custom:[[[-]]] - 14 G. Strang, K. Borre,
*Linear Algebra, Geodesy, and GPS*, MA: Wellesley-Cambridge Press, Wellesley, 1997.custom:[[[-]]] - 15 N. Pfister, P. Buhlmann, B Scholkopf, J. Peters, "Kernel‐based tests for joint independence,"
*Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, vol. 80, no. 1, pp. 5-31, 2018.custom:[[[-]]] - 16 B. Scholkopf, A. J. Smola,
*Learning with Kernels: Support V ector Machines, Regularization, Optimization, and Beyond*, MA: MIT Press, Cambridge, 2018.custom:[[[-]]] - 17 C. J. Simon-Gabriel, B. Scholkopf, "Kernel distribution embeddings: universal kernels, characteristic kernels and kernel metrics on distributions,"
*The Journal of Machine Learning Research*, vol. 19, no. 1, pp. 1-29, 2018.custom:[[[-]]] - 18 P. B. Scholkopf, C. Burgest, V. V apnik, "Extracting support data for a given task," in
*Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining (KDD)*, Montreal, Canada, 1995;pp. 252-257. custom:[[[-]]] - 19 M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, et al.,
*Computer, vol*, 28, no. 9, pp. 23-32, 1995.custom:[[[-]]] - 20 C. Faloutsos, R. Barber, M. Flickner, J. Hafner, W. Niblack, D. Petkovic, W. Equitz, "Efficient and effective querying by image content,"
*Journal of Intelligent Information Systems*, vol. 3, no. 3-4, pp. 231-262, 1994.doi:[[[10.1007/BF00962238]]] - 21 J. Payne, L. Hepplewhite, T. J. Stonham, "Texture, human perception, and information retrieval measures," in
*Proceedings of ACM SIGIR MF/IR Workshop*, Athens, Greece, 2000;custom:[[[-]]] - 22
*MPEG-7 (Online). Available:*, https://mpeg.chiariglione.org/standards/mpeg-7 - 23 L. Wu, C. Faloutsos, K. Sycara, T. R. Payne,
*in Proceedings of 26th International Conference on V ery Large Data Bases, Cairo, Egypt, 2000, pp*, 297-306, 297-306. custom:[[[-]]]