Dealing with Higher Dimensionality and Outliers in Content-Based Image Retrieval

Introduction

High dimensional multiple array data and exponential information growth nowadays are being widely observed in the areas of multimedia retrieval, modern computer vision research (Ju, Sun, Gao, Hu, & Yin, 2015), social networking, text processing, gene expression dataset analysis etc., with respect to both dimensionality and sample size. The dimensionality is being increased double in every 20 month or so (Jensen & Shen, 2008). This high-dimensionality not only increases computational overhead and memory requirements in algorithms, but also adversely affects their performance in real applications. These high-dimensional data however, are not often distributed uniformly in their ambient space; instead they lie in or close to a low-dimensional space or manifold (Torki, Elgammal, & Lee, 2010), (Zhang, Huang, & Wang, 2010). Obtaining the low dimensional features set from high-dimensional data has been a challenging problem in machine learning research. Knowledge acquisition, refining is only valuable when it can be used efficiently and effectively. The accumulated data may contain the noise because of the technological imperfection while capturing these data and the source of the data may produce noisy data. In medical domain any kind of the inadequacy in the imaging device may produce noisy medical images and may be the reason of wrong diagnosis. In social media data is unstructured in nature. The excellent formal or informal contents, spam, grammatical mistakes in those contents, wrong spelling and punctuation marks all these issues are prevalent in social media. The useful knowledge extraction from the data as mentioned is very difficult. The dimensionality reduction in this context is very effective to get rid of the noisy and redundant features. It refers both the feature extractions and feature selections. In feature extraction the original features space is translated into new feature space with smaller dimension and the semantic meaning is lost. In feature selection, a subset of the original features set is extracted by eliminating features with little or no predictive information by minimizing redundancy and maximizing relevance to the target such as the class labels in classification.

Theoretically, the problem of higher dimensional data can be given using a K-Nearest Neighbors (KNN) classifier (Hastie, Tibshirani, & Friedman, 2008). Suppose the inputs are uniformly distributed in the unit hypercube [0, 1]^p and task is to make a decision for a test point x’s belonging class by “growing” a hypercube around x until it contains a desired fraction r of the training data points. The expected edge length of this cube is given by e_p(r) = r^1/p as e(r)^d= r. The p = 10 gives e₁₀(0.01) = 0.01^1/10≈ 0.63 and e₁₀(0.1) = 0.1^1/10≈ 0.80 indicate that to consider 1% or 10% of the data to form a local average, it requires to cover 63% or 80% of the range along each dimension around x. In this context the neighborhoods are no longer “local” in spite of the name “nearest neighbor”. Reducing r will not help because then only fewer observations will be taken for average which results in higher variance. The following Figure 1 is illustrating this curse of dimensionality.

Figure 1.

The illustration of curse of dimensionality. The right figure shows that, for any dimensions p, the side-length of the sub-cube required to consider a fraction r of the volume of the data. For p=10, to capture 10% of the data it requires to capture 80% of the range of each dimension.

However, in the last couple of decades, a lot of progress has been observed in developing tools or formulating algorithms for dimensionality reduction and features selection (Celik, Logsdon, & Aase, 2014), (Jenatton, Obozinski, & Bach, 2010), (Kong, Wang, Teoh, Wang, & Venkateswarlu, 2005), (Lu, Plataniotis, & Venetsanopoulos, 2008) .