Transcription of Kernel k-means, Spectral Clustering and Normalized Cuts
{{id}} {{{paragraph}}}
Example: air traffic controller
Kernel k-means, Spectral Clustering and Normalized Cuts
Kernel k-means, Spectral Clustering and Normalized CutsInderjit S. DhillonDept. of Computer SciencesUniversity of Texas at AustinAustin, TX GuanDept. of Computer SciencesUniversity of Texas at AustinAustin, TX KulisDept. of Computer SciencesUniversity of Texas at AustinAustin, TX and Spectral Clustering have both been usedto identify clusters that are non-linearly separable in inputspace. Despite significant research, these methods have re-mained only loosely related. In this paper, we give an ex-plicit theoretical connection between them. We show thegenerality of the weighted kernelk-means objective func-tion, and derive the Spectral Clustering objective of normal-ized cut as a special case.
the normalized cut criterion is equivalent to the following trace maximization problem: maximize 1 k trace(ZT AZ),where Z = X(XT DX)−1/2, and X is an n × k indicator matrix for the partitions. Note that ZT DZ = Ik. Letting Z˜ = D1/2Z and relaxing the constraint that X is an indicator matrix results in the following problem: maxi-
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: