Loading...
Please wait, while we are loading the content...
Similar Documents
EasyChair Preprint No 1550 Fast Iterative Normalized Cut
| Content Provider | Semantic Scholar |
|---|---|
| Author | Xiao, Zhicong Chen, Xiaojun Zhang, Zitong Nie, Feiping |
| Abstract | Normalized cut is a popular spectral clustering method and has been widely used in many applications. In this paper, we propose a novel Fast Iterative Normalized Cut (FINC) algorithm to solve the classic normalized cut problem in a fast way. In the new method, we rewrite the classical normalized cut problem as a new problem and propose an iterative method with proved convergency to effectively solve the new model without eigendecomposition. Theoretical analysis reveals that solving the new method is equivalent to solving the classic normalized cut. Extensive experimental results show the superior performance of the new method. Introduction Spectral clustering is a hot topic and many spectral clustering algorithms have been proposed during the past decades. Given a dataset, spectral clustering usually constructs a weighted undirected graph from the pair-wise similarity matrix known as the affinity matrix. The commonly-used spectral clustering is normalized cut, that is formalized as a mincut problem to partition the vertices in a graph into several disjoint sets such that the total weight of the set of cut edges is minimized (Ng et al. 2002). Since it is difficult to directly solve the discrete cluster indicator matrix, the normalized cut is usually solved in a two-stage process: 1) relax the discrete cluster indicator matrix into continuous one and solve the relaxed problem with eigendecomposition, and 2) obtain the final discrete cluster indicator matrix with k-means or spectral rotation. However, there is no guarantee on the convergence since the two stages aim to solve different objective functions. Recently, Chen et al. proposed an iterative method, named as Direct Normalized Cut, to directly solve the k-way normalized cut model without relaxation (Chen et al. 2018). However, their method is slow since it employs an inner iterative method to solve the cluster indicator matrix object by object, i.e., assign the cluster membership for one object by fixing the cluster memberships of all other objects. In this paper, we propose a novel Fast Iterative Normalized Cut (FINC) algorithm to solve the classic normalized cut problem. In the new method, we rewrite the classical normalized cut problem as a new problem and propose an iterative method with proved convergency to effectively solve the new ∗Xiaojun Chen is the corresponding author. model without eigendecomposition. Theoretical analysis reveals that solving the new method is equivalent to solving the classic normalized cut. Moreover, the new method is able to simultaneously obtain the cluster memberships of all objects so we can use parallel technique to accelerate it. Experimental results on 5 real-life datasets show the superior performance of the new method. Proposed Method Given the undirected weighted graph G = (V, E) in which the vertices V represent n samples X = {x1, · · · ,xn} and the edges E is associated with the affinity matrix A. Suppose the vertices V in G is partitioned into c components and let Y ∈ Ψn×c be the cluster indicator matrix, in which yil = 1 indicates that xi is assigned to the l-th cluster. In this paper, we propose to solve a new problem as follow max Y∈Ψn×c, s∈Rc×1 c ∑ l=1 2sl √ yT l Ayl − s 2 l y T l DAyl (1) where s ∈ Rc×1 contains c balance parameters in order to balance the volume of these clusters. Problem (1) can be solved with an alternative optimization approach as follows. Update Y with s Fixed When s is fixed, it is difficult to directly solve problem (1) so we rewrite it as a new problem |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://easychair.org/publications/preprint_open/dKN7 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
