Data Mining_ Concepts and Techniques - Jiawei Han [314]
An interesting observation here is that the search for maximal δ-pClusters in MaPle is somewhat similar to mining frequent closed itemsets. Consequently, MaPle borrows the depth-first search framework and ideas from the pruning techniques of pattern-growth methods for frequent pattern mining. This is an example where frequent pattern mining and cluster analysis may share similar techniques and ideas.
An advantage of MaPle and the other algorithms that enumerate all biclusters is that they guarantee the completeness of the results and do not miss any overlapping biclusters. However, a challenge for such enumeration algorithms is that they may become very time consuming if a matrix becomes very large, such as a customer-purchase matrix of hundreds of thousands of customers and millions of products.
11.2.4. Dimensionality Reduction Methods and Spectral Clustering
Subspace clustering methods try to find clusters in subspaces of the original data space. In some situations, it is more effective to construct a new space instead of using subspaces of the original data. This is the motivation behind dimensionality reduction methods for clustering high-dimensional data.
Clustering in a derived space
Consider the three clusters of points in Figure 11.9. It is not possible to cluster these points in any subspace of the original space, X × Y, because all three clusters would end up being projected onto overlapping areas in the x and y axes. What if, instead, we construct a new dimension, (shown as a dashed line in the figure)? By projecting the points onto this new dimension, the three clusters become apparent.
Figure 11.9 Clustering in a derived space may be more effective.
Although Example 11.14 involves only two dimensions, the idea of constructing a new space (so that any clustering structure that is hidden in the data becomes well manifested) can be extended to high-dimensional data. Preferably, the newly constructed space should have low dimensionality.
There are many dimensionality reduction methods. A straightforward approach is to apply feature selection and extraction methods to the data set such as those discussed in Chapter 3. However, such methods may not be able to detect the clustering structure. Therefore, methods that combine feature extraction and clustering are preferred. In this section, we introduce spectral clustering, a group of methods that are effective in high-dimensional data applications.
Figure 11.10 shows the general framework for spectral clustering approaches. The Ng-Jordan-Weiss algorithm is a spectral clustering method. Let's have a look at each step of the framework. In doing so, we also note special conditions that apply to the Ng-Jordan-Weiss algorithm as an example.
Figure 11.10 The framework of spectral clustering approaches. Source: Adapted from Slide 8 at http://videolectures.net/micued08_azran_mcl/.
Given a set of objects, , the distance between each pair of objects, , and the desired number k of clusters, a spectral clustering approach works as follows.
Using the distance measure, calculate an affinity matrix, W, such that
where σ is a scaling parameter that controls how fast the affinity Wij decreases as increases. In the Ng-Jordan-Weiss algorithm, Wii is set to 0.
Using the affinity matrix W, derive a matrix . The way in which this is done can vary. The Ng-Jordan-Weiss algorithm defines a matrix, D, as a diagonal matrix such that Dii is the sum of the i th row of W, that is,
(11.24)