Spectral clustering is not easy to understand. Although I present this topics, I dare not to say I am familiar with it.
Usually it is easier to understand an algorithm from its physcial meaning. In this paper, feature points clustering is first modeled as a Graph G=(V,E). And the action of clustering is interpreted as grouping the nodes into different groups. A simple method to evaluate the quality of grouping is to calculate the sum of edges that are linked between different groups (Cut(A,B)). Smaller Cut(A,B) is prefered since it means the similarity between the groups is small. However, minimize cut usually causes clustering that has little number of members. To solve this problem, the author proposed a method to evaluate the cut quality, and it is Normlized Cut (NCut(A,B)).
The idea of NCut is that it penalizes a clustering that has few edges connected to the nodes out of its group. However, it makes the problem becomes NP-hard. The author found that the NCut value can be represented by some matrix form consisting of the Laplacian matrix L and the vector f determined by the clustering result. That is, you can minimze NCut by minimize the matrix form. However, it is unreasonable since once we get f, we get the NCut value. In other words, minimizing the matrix form is equivalent to using brute force. In order to solve the matrix form, the author relieves some constraint of f. And then the problem can be solved as an eigenvector problem because of the approximation.
The paper mainly focus on how to cluster the data into two groups and does not put much emphasize on howto cluster the data into several groups simutaneously.
The authors also compared the normalized cut algorithm with other algorithms. There is no suprise that their method performs superior than other methods under some different settings.
Reference:
Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation," Trans. PAMI 2000.
Usually it is easier to understand an algorithm from its physcial meaning. In this paper, feature points clustering is first modeled as a Graph G=(V,E). And the action of clustering is interpreted as grouping the nodes into different groups. A simple method to evaluate the quality of grouping is to calculate the sum of edges that are linked between different groups (Cut(A,B)). Smaller Cut(A,B) is prefered since it means the similarity between the groups is small. However, minimize cut usually causes clustering that has little number of members. To solve this problem, the author proposed a method to evaluate the cut quality, and it is Normlized Cut (NCut(A,B)).
The idea of NCut is that it penalizes a clustering that has few edges connected to the nodes out of its group. However, it makes the problem becomes NP-hard. The author found that the NCut value can be represented by some matrix form consisting of the Laplacian matrix L and the vector f determined by the clustering result. That is, you can minimze NCut by minimize the matrix form. However, it is unreasonable since once we get f, we get the NCut value. In other words, minimizing the matrix form is equivalent to using brute force. In order to solve the matrix form, the author relieves some constraint of f. And then the problem can be solved as an eigenvector problem because of the approximation.
The paper mainly focus on how to cluster the data into two groups and does not put much emphasize on howto cluster the data into several groups simutaneously.
The authors also compared the normalized cut algorithm with other algorithms. There is no suprise that their method performs superior than other methods under some different settings.
Reference:
Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation," Trans. PAMI 2000.
沒有留言:
張貼留言