Euler Clustering

1 Introduction

Clustering plays an important role in organizing, understanding and learning data. As the information science and Internet techniques develop, a large amount of data, especially image data, are created every day. Consequently, it challenges existing clustering models in both the computational aspect due to increasing size of data and the robustness aspect due to more diversities of data. It is particularly a big obstacle for applying kernel k-means as well as other related kernel based clustering methods [Sch¨olkopf et al., 1998; Ng et al., 2001; Dhillon et al., 2004] to analyze large scale data.

Most if not all, the obstacle of using kernel-based clustering methods for large scale data is mainly caused by the use of kernel trick. Kernel based clustering implicitly transforms data from lower dimensional space to higher or even infinite dimensional feature space (i.e., Reproducing Kernel Hilbert Space (RKHS)), and then linear clustering models are applied in that feature space. The mapping is implicitly induced and supposed to deal with nonlinear clustering problem.

However, relying on commonly used kernel functions, such as Gaussian kernel [Chitta et al., 2011], spatial pyramid matching kernel [Lazebnik et al., 2006] and etc., kernel based clustering methods could not be applied to large scale data. It is because, those frequently used kernel functions implicitly but not explicitly induce a mapping by using kernel trick[Sch¨olkopf, 2000], and this makes the space and computational complexity of kernel based clustering increase dramatically due to computing and keeping the full kernel matrix during learning. Hence, existing kernel based methods are not appropriate for large scale clustering problems due to the limitation of memory, e.g. it needs about 7,500GB memory to keep the kernel matrix for the dataset with 1 million data points. Although the kernel matrix can be subdivided and loaded in the memory block by block [Zhang and Rudnicky, 2002], the optimization will cost the time that is quadratic to the size of the dataset, so that it does not work efficiently for large scale problems. To address the high computational complexity problem in the optimization, an approximate kernel k-means approach is proposed in [Chitta et al., 2011].

In this work, we solve the large scale computation problem in kernel based clustering methods by incorporating Euler kernel [Liwicki et al., 2012]. Particularly, we develop an Euler clustering, which is scalable kernel k-means. The Euler kernel is relying on a nonlinear and robust cosine metric, and more important it intrinsically induces an empirical map which maps data onto a complex space of the same dimension. In addition, the cosine metric is a robust metric and is able to tolerate outliers during clustering. Euler clustering takes the advantages of Euler kernel to measure the similarity between data in a robust way without using kernel trick and increasing the dimensionality of data, and thus solves the large scale problem in kernel k-means.

Euler clustering differs existing clustering methods in the following aspects:

• Euler clustering gets rid of kernel trick and can directly calculate the corresponding distance between a data point and any cluster center efficiently, and thus no

need to calculate and store the kernel matrix.

• The dimension of feature space corresponding to the mapping induced by Euler kernel is the same as data's dimensionality itself. This is because although Euler kernel is based on nonlinear cosine distance, it is however equivalent to deriving an explicit mapping, which maps data onto a complex space of the same dimension. Note that, since the mapping induced by Euler kernel has the same dimension as input data, the computational complexity of Euler kernel is comparable to k-means. Although there exists empirical kernel mapping methods [Sch¨olkopf et al., 1998; Ng et al., 2001; Dhillon et al., 2004; Chitta et al., 2011], they either lose some discriminant information or lead to high dimensionality for each data after the mapping. Hence, Euler clustering is suitable for large scale clustering problems without deriving any approximate models.
• Less sensitive to noise and outliers. In Euler clustering, the distance between data points in the RKHS space is a cosine based measure. Due to the periodicity and the range of the cosine function, the affects of the noise features on the distance are lessened. Hence, outliers will pull the corresponding mean vectors used as the cluster representative prototypes to themselves much more lightly in the RKHS space.

Although Euler clustering is just a special case of kernel k-means, the contribution of this work lies in that by using Euler kernel, Euler clustering can address the large scale and robust clustering simultaneously in a simple but elegant and effective way. In addition, Euler kernel is very different from existing widely known Mercer kernels in that it is defined in the complex domain rather than the real domain. However, it can be used for distance based modeling and our work is able to tell the usefulness of complex methods for clustering analysis.

The reminder of this paper is organized as follows. Section 2 briefly introduces the kernel k-means algorithm and the Euler kernel. In section 3, we introduce Euler clustering and detail the fast optimization process. The used datasets and the experimental results are reported in section 4. Then we conclude this paper in section 5.

2 Preliminary

In order to make our paper self-contained, we first introduce kernel k-means and the Euler kernel which is defined in the complex domain.

2.1 Kernel k-means

Kernel k-means first maps data points from the data space into a RKHS space using an implicit mapping induced by kernel function through kernel trick, and then clusters data to find cluster assignments such that the similar data points are in the same cluster and the dissimilar data points are in different clusters.

More specifically, let X = {x1, . . . , xn} be the given dataset consisting of n data points in Rd , and let ψ(·) denote the mapping induced by kernel function, i.e. ψ(xj) is the image of xj in this defined RKHS space. To group the dataset X

into C clusters, kernel k-means is modeled to minimize the distortion error [Bishop, 2006]

Here mc is the representative prototype, which is given by the mean vector of the images of the cluster Gc as

and U is the cluster membership indicator matrix, Ujc = 1 if xj belongs to Gc, and Ujc = 0 otherwise.

After obtaining the optimal representative prototypes mc, the cluster labels for data points are assigned by finding the closest cluster prototypes as follows

where vj is the assignment for data point xj.

However, due to the implicit representation of images in the RKHS space, the cluster prototypes cannot be represented explicitly, so that the distance between image ψ(xj) and the c-th cluster prototype mc must be calculated by using the kernel trick as follows

where K is the corresponding kernel matrix defined by ψ(·), and nc is the number of data points belonging to the c-th cluster. Obviously, it has to store the full kernel matrix, which may be too large to be loaded in the memory, and it has to spend O(Cn) time in assigning label to each data point at each iteration according to Eq. (4). Hence in total O(Cn2 ) time is used to get labels assigned for data points at each iteration. Therefore, kernel k-means, by using traditional kernel, is not suitable for solving the clustering problem for large amount of data points.

2.2 Euler Kernel

Let xj be one of data points in the given dataset X. Denote the image set as Φ = {φ(x1), . . . , φ(xn)}, then the kernel matrix K is defined by φ(·) as K = ΦH Φ [Paulsen, 2009]. That is, the (j, q)-entry of the kernel matrix is given as follows

Different from existing Mercer kernels, K is defined in the complex space. And, we have KH = K because Kqj = Kjq, where · represents the complex conjugate operator.

It is found that Euler kernel actually induces a mapping φ(xj) [Liwicki et al., 2012] that maps data point xj from d-dimensional real space Rd onto d-dimensional complex RKHS space C d , i.e. φ : Rd → C d , as follows

where i is the imaginary unit.

Therefore, the distance function d(·, ·) which calculates the square Euclidean distance between images φ(xj) and φ(xq) in the RKHS space is given by

where θj denotes απxj. Hence, the distance function d(·, ·) is a real value, so that the distances can be used to measure the dissimilarities between data points, although the kernel function φ and the kernel matrix K are defined in the complex space.

Since cosine function is a periodic function and its value lies in the range [-1, 1], the distance defined as Eq. (7) is less sensitive to noisy features than ℓ2-norm (i.e. Euclidean form) defined in the data space by limiting the affects of noisy features on the distance in the range [-1, 1]. When the value α is small, the distance function Eq. (7) will become l2-norm. As the value α increases, Eq. (7) will reduce the large distances caused by the noise features [Liwicki et al., 2012].

By Eq. (6), Euler kernel can induce an explicit map from input data space to RKHS space without increasing the data dimension. Although Euler kernel function and the corresponding kernel matrix are defined in the complex domain, the distance between data points is ultimately formulated in the real domain, so that it can be used as the dissimilarity measure between data points.

3 Euler Clustering

In this section, we will propose a novel kernel based k-means approach, called Euler clustering. We will employ the Euler kernel function to define the RKHS space and organize the data into C clusters based on a k-means style algorithm in this defined RKHS space. Although it is a kernel based k-means approach, it is almost as fast as k-means algorithm and less sensitive to noise and outliers.

Since, Euler kernel can induce an explicit mapping φ(·) from data space to feature space, the images in the RKHS space can be explicitly represented through Eq. (6) in the complex space. Hence, the cluster representative prototype mc can be explicitly computed in the complex space by the following lemma.

Lemma 1. Denote the size of the cluster Gc by nc, then the optimal mc can be represented explicitly as

where a and b are given by a = 1 nc ∑xj∈Gc cos(απxj) and b = 1 nc ∑xj∈Gc sin(απxj ).

The lemma is straightforward. Note that by conducting kmeans algorithm in the RKHS space, the optimal mc is given as the mean vector of the cluster Gc, i.e.

Due to the explicit formulation of the mapping in Eq. (6) for Euler kernel function, we have

This suggests that different from existing kernel k-means using Gaussian, spatial pyramid matching kernels and etc., the cluster centers mc can be represented explicitly in Euler clustering. Based on this fact, we can derive the below criterion of Euler clustering.

Theorem 1. Euler clustering is to minimize the distortion error

where mc is given by Eq. (10), and the squared Euclidean distance d(xj,mc) (defined in Eq. (7)) from the data point xj to the cluster prototype mc is given by

Proof. Denote απxj by θj and represent mc explicitly as Eq. (10). The squared Euclidean distance d(xj,mc) can be expanded as follows

So that the distance from xj to mc in the RKHS space can be calculated more efficiently.

Euler clustering is in line with k-means. Euler clustering performs the following steps iteratively for optimizing the criterion: 1) updating the optimal cluster prototypes mc explicitly using Eq. (10) by fixing the cluster labels of data points, and 2) grouping data points into closest clusters according to Eq. (12) by fixing mc. Algorithm 1 details the procedure. Euler clustering will monotonically decrease the objective function after updating the cluster representative prototypes and re-assigning labels for data points. Like k-means, it can be concluded that the objective function of Euler clustering is bounded as well. Therefore, the Euler clustering algorithm will converge to a local minimum in a finite number of iterations.

What more important is that the computational complexity of Euler clustering is comparable to k-means, although it is

Algorithm 1 Euler Clustering

• 1: Input: Dataset X = {x1, . . . , xn}, the number of clusters C, the value α, and the maximum number of iterations tmax.
• 2: Output: The cluster sets Gc, c = 1, . . . , C.
• 3: Initialization: Initialize the cluster labels of data points.

Transform the data points from data space onto feature space using Eq. (6).

• 4: repeat
• 5: t = t + 1;
• 6: Fix the cluster labels of the data points, and update the cluster representative prototypes mc using Eq. (10).
• 7: Fix the cluster representative prototypes mc, and update the cluster labels of the data points using Eq. (12).
• 8: until convergence || t > tmax.

a nonlinear clustering method. More specifically, Euler clustering only takes O(nd) and O(ndC ) to update the cluster representative prototypes and the cluster labels of data points in each iteration. the Euler clustering algorithm converges in O(T ndC ), where T is the number of iterations. Hence, Euler clustering can code with the nonlinear clustering and perform as light as a linear method. The following theorem summarize the computational analysis of Euler Clustering.

Theorem 2. The proposed Euler clustering algorithm can converge to a local optimum in O(TndC ), where T is the number of iterations.

4 Experiments

In this section, we evaluate the proposed Euler clustering method on five public datasets: Event [Li and Fei-Fei, 2007], 13 Natural Scene Categories [Fei-Fei and Perona, 2005], Caltech 101 [Fei-Fei et al., 2006], Imagenet [Deng et al., 2009], and Caltech 256 [Griffin et al., 2007], to show its performance compared to k-means algorithm [MacQueen, 1967], kernel k-means algorithm [Sch¨olkopf et al., 1998], normalized cut algorithm [Shi and Malik, 2000], and approximate kernel k-means algorithm [Chitta et al., 2011]. The Gaussian kernel is a very effective kernel and commonly used in many fields, and the spatial pyramid matching kernel is often applied in computer vision. Both two kernels are applied in kernel k-means, normalized cut, and approximate kernel kmeans. We denote them as G-K-Kmeans (P-K-Kmeans), GN-Cut (P-N-Cut), and G-AppK-Kmeans (P-AppK-Kmeans) when using Gaussian kernel (spatial pyramid matching kernel), respectively.

4.1 Experimental Settings

For all the five datasets, the spatial pyramid image representation was created for each image. We first extracted 128dimensional SIFT descriptors [Lowe, 1999] for each image. Then we employed the bag-of-features [Fei-Fei and Perona, 2005] to get 512 prototypes for the SIFT features and apply the spatial pyramid modeling [Lazebnik et al., 2006] to obtain three-level based pyramid histogram representation, which is a sparse 10,752-dimensional vector for representing each image.

We measure the clustering performance in terms of the normalized mutual information (NMI) [Dhillon et al., 2004]. The NMI lies in [0, 1]. The larger the NMI is, the better the clustering matches the true class distribution. Meanwhile, the empirical time the compared approaches take to achieve the convergence is measured to show the efficiency of our method.

For all the experiments shown in the following, the value α of our approach is set to be 700. For the Gaussian kernel, the kernel width is set as √l ∑ni=1 ∑nj=1 ‖xi-xj ‖2 n(n-1) , where l is selected from the sequences [0.001, 0.005, 0.01, . . . , 100, 200, . . . 1000]. For the approximate kernel k-means algorithms, the sample size is set to be 1,000, such that its clustering performance on all the five datasets approximate the corresponding kernel k-means algorithm.

All the methods are implemented in Matlab and run on an Intel Xeon 2.67GHz processor. To make the performance of the compared methods comparable, all the results reported are averaged over 10 runs with 10 different initializations of the cluster labels of data points. All compared methods are conducted under the same setting. The maximum number of iterations is set to be 100 for all compared methods.

4.2 Datasets

Table 1 summarizes the properties of the five datasets, and the details of these datasets are shown as follows.

• Event: The event dataset contains 8 sports event categories collected from Internet with the sizes of categories varying from 137 to 250.
• 13 Natural Scenes: There are 3,859 images covering 13 categories of natural scenes in the 13 Natural Scenes dataset. The average size of each image is about 250 × 300 pixels.
• Caltech 101: This dataset consists of 8,677 pictures of objects belonging to 101 categories. There are about 40 to 800 images per category, and most categories have about 50 images. The images in this dataset are left-right aligned.
• SImagenet: The full Imagenet dataset contains 1,261,402 images that are organized into 1,000 leaf synsets in a synset tree, in which each leaf synset represents a class of images. We selected 19,911 images from 12 synsets: manhole cover, daily, website, odometer,

monarch butterfly, rapeseed, cliff dwelling, mountain, geyser, shoji, door, villa, to construct a small dataset SImagenet [Chitta et al., 2011].

• Caltech 256: The collection of this dataset contains 30,607 images of objects belonging to 256 categories and 1 clutter. We discarded the images in the clutter, and chose the other images to construct this dataset consisting of 29,780 images covering 256 categories. Compared to Caltech 101, there are more images per category, and the images are not left-aligned in this dataset, thus it is harder to identify.

4.3 Experimental Results

As aforementioned, we compare all methods in terms of the NMI and the computational cost on the five datasets in the Table 2 and Table 3. Table 2 tabulates the average NMI over 10 runs for the five public datasets. On all datasets, Euler clustering achieves the best clustering performance among all the compared approaches. It improves the clustering significantly.

Compared to non-approximate kernel methods, such as kmeans, Euler clustering enhances the clustering performance with almost 1∼2 times higher average NMI on Event, Scene 13 and SImagenet, and 50% higher average NMI on Caltech 101 and Caltech 256. Compared to the Gaussian kernel based kernel k-means and normalized cut, Euler clustering obtains great improvement as well. In particular on Scene 13 dataset, Euler clustering obtains 0.27 higher average NMI against G-K-Kmeans, and 0.31 higher average NMI against G-N-Cut; on SImagenet dataset, 0.255 higher average NMI and 0.23 higher average NMI are achieved as compared to G-K-Kmeans and G-N-Cut respectively. Even compared to the spatial pyramid matching kernel based ones that are popularly used in literature for image categorization, Euler clustering improves the clustering with almost 10%∼15% higher NMI values as well.

Compared to approximate kernel clustering methods such as G-AppK-Kmeans and P-AppK-Kmeans, Euler clustering also gains significant improvement on the NMI performance. The figures in Table 2 and Table 3 show the approximate methods, especially G-AppK-Kmeans, is always much faster than Euler clustering. However the price is that its performance is still much lower than Euler clustering, although it may suggest a combination of the approximation methodology and Euler clustering would be a promising extension in future.

Among all datasets, Euler clustering performs much better on Scene 13, Caltech 101 and SImagenet. Although dataset Event contains less images and less categories, the clustering performances of all approaches are lower than the ones on Scene 13, SImagenet, and Caltech 101, because the images from Event contain more semantic information. All approaches do not work very well on Caltech 256 as shown in Table 2, since it is large and contains diverse categories with large intra- and inter- class variations. Nevertheless, Euler clustering still obtains comparable performances on the two datasets.

Regarding the stability of Euler clustering, Table 2 also shows that Euler clustering not only obtains the best clustering performance in terms of NMI but also obtains the most robust clustering performance in terms of the standard deviation of NMI values against initializations. It obtains the smallest standard deviation of NMI values on SImagenet and Caltech 256. Although the absolute standard deviation values on Scene 13 and Caltech 101 it obtains are not the smallest, the relative standard deviation values with respective to the NMI values are the smallest. On Event, the relative standard deviation value it obtains is not the smallest, but it is not larger than the ones obtained by G-K-Kmeans and P-AppK-Kmeans too much.

Finally, the time for each method to take to achieve the convergence is shown in Table 3. Table 3 shows that Euler clustering is an efficient and more robust approach, although it is not the fastest on the five datasets. Compared to k-means, Euler clustering takes comparable time, as Euler clustering needs additional processing to compute the mapping. However, it converges with less iterations on the datasets Caltech 101 and Caltech 256. The reason why Gaussian kernel based clustering, namely G-K-Kmeans runs faster than Euler clustering and even k-means on Event and Scene 13 as shown in Table 1 is because the sizes of Event and Scene 13 are much smaller than the dimensionality of data, so the Gaussian kernel matrix can be calculated efficiently. However, as long as the size of dataset increases, G-K-Kmeans takes more and more time than Euler clustering on SImagenet and Caltech 256. This is because by the representation theorem, the computational complexity of G-K-Kmeans is a quadratic function of the number of samples and G-K-Kmeans therefore becomes more costly for large scale dataset. P-K-Kmeans always takes a lot of time, because modeling spatial pyramid takes time. Although P-K-Kmeans always gets better performance than G-K-Kmeans, it is however still clearly performs inferior to Euler clustering in the aspect of both computational cost and NMI performance (10%-15% lower NMI values than Euler clustering).

4.4 Parameters

In this section, we will show that our proposal is robust to the parameter value. For investigation, we plot the average NMI values it achieves on all the five datasets by varying α in the range [0.1, 1000] in Figure 1.

Figure 1 shows that when α lies in the range [0.1, 2], Euler clustering performs similarly to the k-means algorithm with the NMI values being close to the ones achieved by k-means, which are shown in Table 2, because the cosine based distance ensembles the l2 norm distance when α is small. As α increases, the clustering becomes better matching to the true class distribution. When α is in the range [100, 1000], Euler clustering performs much better than k-means as shown in Figure 1. Figure 1 also shows that Euler clustering performs stably when α in the range [100, 1000].

5 Conclusion

In this paper, we introduce Euler clustering in order to solve the existing largely unsolved problems for kernel clustering, namely the large scale computation problem and robust clustering. This is achieved by incorporating Euler kernel in line with kernel k-means. Euler kernel differs from existing kernels and is a complex function. It provides a cosine distance based measure between data and meanwhile induces an empirical mapping of the same dimension as input data. Our experiments have validated our approach against related approaches.

Acknowledgments

This research was supported by the National Natural Science of Foundation of China (No. 61102111, No. 61173084), the NSFC-GuangDong (U1135001), the 12th Five-year Plan China S&TSupporting Programme (No. 2012BAK16B06), Foundation of China and Royal Society of Edinburgh (NSFCRSE) joint project (No. 6121130123), Specialized Research Fund for the Doctoral Program of Higher Education (No. 20110171120051), Guangdong Natural Science Foundation (No. S2012010009926), the Fundamental Research Funds for the Central Universities (No. 12lgpy28, 2012350003161455) and the Guangdong Provincial Government of China through the Computational Science Innovative Research Team program.