ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

08. spectal clustering

?
?
Jeonghun Yoon
Jeonghun Yoon

Spectral clustering? ?? ?? ??? ?????. Eignevalue? Eigenvector? ?????? ??? ?????? ? ? ?? ?????.

1 of 37
Downloaded 91 times
Jeonghun Yoon
(??) ??? ??? ??? "objects"?? ?????? ????. objects? ??? or ?? or ?? ?? ? ? ??. ???? ??? ??? ??? ??(clusters)? ???. (??? ??) ??? objects???? ???(similarity)? ????. ?? ??? ??? objects? ??? ???? ??? ??, ?? ??? ??? objects? ??? ???? ??? ??.
??? ??? ??? k-means ????? ???? 2?? clusters? ??? ??.
k-means? ???? ?? clusters??. "On Spectral Clustering: Analysis and an algorithm" by AY Ng ?? ?? convex set? ?? ?? k-means? ??? ? ??.
????, convex set? ?? ???? ??? clusters? ??? ? ? ???? ??? ?? ??? ???? original data points? ??? points? ?? ? ? (embedding, demsional reduction) ? ??? points set?? ????? ????? ??? ???? "On Spectral Clustering: Analysis and an algorithm" by AY Ng original ??? ?? ??? ??? ??(??? ??? ??)
(How?) ??? objects??? ???(similarity)? ?????, ??? ??(similarity matrix)? ???. ?? ???? ???? ????, objects? points? mapping ??? points ??? ???? ?? ? ? ??. ??? ??(similarity) ??? ????, ?? ???(similarity graph)? ????. ?? ???? ????? ??, ???? ?? ??(adjacency matrix)? ????? ??(laplacian matrix)? ????? ??? ???? ??. ??? ????? ??? ???? ??? points set? ????. objects? clusters? ??? ?? Graph? ??! ??? ??? ??? ??.
(??? ? ???? & ????) ¢Ù ??? data objects(points) ?1, ¡­ , ? ? ¢Ú ?? objects ??? ???(similarity) ? ??, ?? = ??? ? = ?1, ¡­ , ? ? ? ?1 ???? ??? ??? ???? ?1??? ??, ? ?? ???? ??? ??? ???? ? ???? ??. ?1, ¡­ , ? ? ? ?1 ?2 ?3 ?4 ?1? ?2? ?? ?? ??? ??, ?1? ?3? ?? ?? ?? ??? ??, ?1? ?4? ?? ??? ?? ??.
??? ???? ?? clusters? ??? ??? ??? ? ??. ??? ¡ü ?? ? ?? 2 ¡ý ??? ¡ý ?? ? ?? 2 ¡ü ? ?? ??? ??? ???. ??? ? ? ??? ?? ? ?? ? ??? ? ? ??? ?? ? ?? ?
? ?? ??, ?? ?? ?? ?? ?(eigenvalue)? ???? ?? ??(eigenvector)??. ? = ?1, ¡­ , ? ? ? ? = ?1 ?2 ? ? ? ?? ?? ?? ?? ?1 = ?1 ?2 ? ? ? ?1? ?1? ???? ??? point??, ?2? ?2? ???? ??? point??. ??? ? ? ??? ?? ? ?? ? = min ? 1 2 ? ? ?? ??? points (??? ???? ??)
By , this change of representation enhances the cluster-properties in the data, so that clusters can be trivially detected in the new representation.
? Input : Data points ? ?, ? ?, ...,? ? ¡Ê ? ? , Similarity matrix ? ¡Ê ? ?¡Á? , clusters? ? ? ¡ð Similarity matrix? ???? similarity graph? ??(build) ¡ð adjacency matrix ?, diagonal matrix ?? ???? graph laplacian? ?? ¢Ù ? = ? ? ? : unnormalized graph laplacian ¡ð matrix L? ??? ?? ??(eigenvector) ?1, ¡­ , ? ? ¡Ê ? ? ? ?? ? ?? ?? Spectral Clustering Algorithm
¡ð ??? ?? ??? ?(column)? ???? matrix ?? ?? (? ¡Ê ? ?¡Á?) ¡ð ?? ?(row)? ??? data points? ??(interpret) ? ?, ? ?,..., ? ? ¡Ê ? ? ¡ð ??? ??? data points ?1, ?2, ..., ? ?? ?-means ????? ???? ??? clusters? ?? Spectral Clustering Algorithm ?11 ?12 ?21 ?22 ? ?1(??1) ?1? ?2(??1) ?2? ? ? ? ? ?1 ? ?2 ? ? ?(??1) ? ?? ? = ?1, ?2, ¡­ , ? ? = ?11 ?12 ?21 ?22 ? ?1(??1) ?1? ?2(??1) ?2? ? ? ? ? ?1 ? ?2 ? ? ?(??1) ? ?? new data point ? ? new data point ? ? new data point ? ? Dimensional Reduction : ? ¡Á ? ¡ú ? ¡Á ?
1 3 4 2 5 6 8 7 ???? ?? ??(??? ?? ?). 3?? clusters? ??? ???.
08. spectal clustering
?1 ?2 ?3 ?2 ?1 ?3 2? (0 , -0.7071 , 0) ??? points 8?? ?? (0 , 0 , -0.5) (0 , 0 , -0.5) (0 , 0 , -0.5) (0 , 0 , -0.5) (-0.7071 , 0 , 0) (-0.7071 , 0 , 0) (0 , -0.7071 , 0) (0 , -0.7071 , 0) 2? (-0.7071 , 0 , 0) 4? (0 , 0 , -0.5000) ??? ??(Embedding ? ??)
- ?? eigenvalue ??? ???? ??? eigenvector? ???? ??? ???? - ? ???? - ?? ??? ??? ? ???? Questions Go to appendix 1
? if, connected graph??? first laplacian eigenvector? constant vector. (?) ? if, disconnected(?-connected components), graph laplacian? block diagonal matrix??, ?? ? laplacian eigenvector? ??? ??. ?????, Go to appendix 2
Spectral Clustering? ??? (connected component? 1? ??)
? ???, components? ?? ???(loosely) ?? ?? ???(connected), ? graph laplacian? ??? block diagonal matrix? ?? ?, ? ?? laplacian eigenvector? ???. ¡ð Balanced min-cut? ???? ? ?? laplacian eigenvector? ????. ¡ð ? cluster? ???, ??? eigenvector? ????, ? eigenvector?? ?? ?? ?? ??.(perturbed) ¡ù ??? ??? Davis-Kahan Theorem? ??. Go to appendix 3
Spectral Clustering? ??? (connected component? 1?)
Spectral Clustering?? ?-means ????? ?????, ??? non-convex ??? ?? data ???? clusters? ??? ? ??.
? Eigengap ¡ð ?? ???? ?? ???? ??. ¡ð choose the number ? such that all eigenvalues ?1,¡­,? ? are very small, but ? ?+1 is relatively large.
? Unnormalized Graph Laplacian ? = ? ? ? ? Normalized Graph Laplacian ? ??? = ?? ? ? ??? ? ? = ? ? ?? ? ? ??? ? ? ? ?? = ??? ? = ? ? ??? ? ???????? ????
? graph? normal??, ???? vertices? ??(approximately) ?? degree? ? ? ??, ?, ? ??, ? ???? ?? ??? clustering ??? ????. ? graph? degrees? ?? broadly distributed ? ??, (?? ??? ??) ¡ð normalized rather than unnormalized ¡ð ? ?? rather than ? ???
? We want to partition such that ¡ð points in different clusters are dissimilar to each other ¢Ù minimize the between-cluster similarity ¢Ú minimize ???(?, ? ? ) ¡ð points in the same cluster are similar to each other ¢Ù maximize the within-cluster similarity ¢Ú maximize ?(?, ?) and ?(? ? , ? ? )
? between-cluster similarity ¡ð ????, ???????? satisfy. ? within-cluster similarity ¡ð ? ?, ? = ? ?, ? ? ? ?, ? ? = ??? ? ? ???(?, ? ? ) ¡ð If ???(?, ? ? ) is small and ???(?) is large, then within-cluster is maximized. ¡ð We can achieve this by minimizing ????. ? Normalized spectral clustering using implements both clustering objective mentioned above, while unnormalized spectral clustering only implements the first objective.
? Spectral clustering?? ??? relaxation? ????. (discrete problem) ? Most importantly, there is no guarantee whatsoever on the quality of the solution of the relaxed problem compared to the exact solution. ? The reason why the spectral relaxation is so appealing is not that it leads to particularly good solutions. ? Its popularity is mainly due to the fact that it results in a standard linear algebra problem which is simple to solve.
? http://snap.stanford.edu/class/cs224w-readings/ng01spectralcluster.pdf ? http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf ? http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Lu xburg07_tutorial_4488%5b0%5d.pdf ? http://ranger.uta.edu/~chqding/papers/KmeansPCA1.pdf ? http://ranger.uta.edu/~chqding/Spectral/spectralA.pdf
cluster? ??? ?? ??? ? ? ??? ?? ? ?? ? ??? ? ? ??? ?? ? ?? ? ??? ? ? ? ? ? ?? ???????? ???? by def of ? graph cut Spectral cluster is a way to solve relaxed versions of cut problems.
? ???????? ?1, ?2, ¡­ , ? ? ??? ?? ¡ð Given a partition of ? into ? sets, we define ? indicator vectors ?? = (?1,?, ¡­ , ? ?,?) by ¢Ù ??,? = 1 |? ?| if ?? ¡Ê ?? ¢Ú ??,? = 0 otherwise for all (? = 1, ¡­ , ?; ? = 1, ¡­ , ?) ???????? ?1, ¡­ , ? ? ? ? ?=1 ? ??? ??, ?? ? |??| = ? ?=1 ? ?? ? ??? = ? ?=1 ? ? ? ?? ?? = ??(? ? ??) ??? ?¡Ê? ?¡Á? ??(? ? ??) s.t. ? ? ? = ? by Rayleigh-Ritz thm, sol of this problem : ? eigenvectors of unnormalized laplacian ?
? ???? ?1, ?2, ¡­ , ? ? ??? ?? ¡ð Given a partition of ? into ? sets, we define ? indicator vectors ?? = (?1,?, ¡­ , ? ?,?) by ¢Ù ??,? = 1 ???(? ?) if ?? ¡Ê ?? ¢Ú ??,? = 0 otherwise for all (? = 1, ¡­ , ?; ? = 1, ¡­ , ?) ??? ? ?,¡­,? ? ??(? ? ??) s.t. ? ? ?? = ? by Rayleigh-Ritz thm, sol of this problem : ? eigenvectors of normalized laplacian ? ??? ??? ?¡Ê? ?¡Á? ??(? ? ?? ? ? ??? ? ? ?) s.t. ? ? ? = ? ??? ??? ??????. ? = ? 1 2 ? Back by Rayleigh-Ritz thm, sol of this problem : ? eigenvectors of normalized laplacian ? ??
Ideal ??? ?????. ??? connected components? ??? ????. ?? ?? components? connectio? ?? ????. (connected component : component?? ?? ??? path? ??? ??) block diagonal matrix??. ? = ?1 ?2 ? ? ?
¡ù Prove ¡ð ??, connected component? 1??? ??? ??. ??? ?? ? 0? ???? ?? ??? ??? ??. ??? 0 = ¦²?,? ??,? ?? ? ?? 2 ? ? ???. ??,? > 0 ???, ??? ??? ?? ?, ?? ??? ?? ?? ??? ? ???. ???, ?? vertices ?? ??? path? ?? ? ???. ??? ? = ?? where ? ¡Ê ?? ??.
¡ù Prove ¡ð connected component? 1?? ??? ??? ??. ?? ? 0? ???? ?? ?? ? ?? ?? ??? ? ??. ?????? block diagonal ??? ??? ???, connected component? ???? ??? ??? ??? ?? ?? ?? ??? ??? ??,? = 0??? ??, ??? 0? ???. ???, block diagonal ??? ?? ?? ??? ??? ???? ??? ??? 0? eigenvector? component? ??? ???? ? ?. ?? ? eigenvector? ?? eigenvalue 0? ???? eigenvectors??. ? = ?1 ?2 ? ? ? ?1 ?1 0 0 0 0 0 0 0 ?2 ?2 0 0 0 0 0 0 0 0 ? ? ? ?
¡ð ? is a block diagonal matrix, the spectrum of ? is given by the union of the spectra of ??, and the corresponding eigenvectors of ? are the eigenvectors of ??,filled with 0 at the positions of the other blocks. Back
? Perturbation theory ¡ð How eigenvalues and eigenvectors of a matrix ? change if we add a small perturbation ?. ¡ð Most perturbation theorems state that a certain distance between eigenvalues or eigenvectors of ? and perturbed matrix ? ? = ? + ? is bounded by a constant times a norm of ?. ¡ð Strongly connected componen? ideal case?? ????. loosely connected componen? nearly ideal case?? ??. nearly ideal case?? ??? ??? distinct cluster? ??? ??. ??? between-cluster? similarity? ??? 0? ???. ¢Ùideal case? perturbed laplacian matrix(nearly ideal case)? ?????. ¢ÚPerturbation theory? ???, perturbed laplacian? eigenvectors? ideal case ? indicator vectors(eigenvectors of laplacian)? ??? ?? ??. ¢Û??? ideal case? eigenvectors? ???? ??? ??? nearly ideal case? eigenvectors? ???? ??? ??? ??? error term? ????? ?? ? ???? ? ? ??.
¡ð ??? ??? ???? ? properties 2?? ??. ¢Ù eigenvectors? eigenvalues? ??? ??? ??? ??. ¨C ?? ??? ??. ?? ?? ??? ??. ¢Ú eigenvector? components? 0???? "safely bounded away" ??? ??. ¨C ?, ? ?? = ??1 ?? ? property? ? ????. ¨C ? ??? = ?? 1 2 ??? 1 2? eigenvector? ? 1 2 ? ? ? ??. ???, vertices? degree? ??? ?? ???, degre? ?? ?? vertices? ????, eignevectors?? ???? entries? ?? 0? ?? ??? ??. ??? ?? ???? ??? row- normalization step? ????. ¨C ? ???? very low degrees? ??? vertices? ??? ?, ???? ???? ??. Back

More Related Content

08. spectal clustering

  • 2. (??) ??? ??? ??? "objects"?? ?????? ????. objects? ??? or ?? or ?? ?? ? ? ??. ???? ??? ??? ??? ??(clusters)? ???. (??? ??) ??? objects???? ???(similarity)? ????. ?? ??? ??? objects? ??? ???? ??? ??, ?? ??? ??? objects? ??? ???? ??? ??.
  • 3. ??? ??? ??? k-means ????? ???? 2?? clusters? ??? ??.
  • 4. k-means? ???? ?? clusters??. "On Spectral Clustering: Analysis and an algorithm" by AY Ng ?? ?? convex set? ?? ?? k-means? ??? ? ??.
  • 5. ????, convex set? ?? ???? ??? clusters? ??? ? ? ???? ??? ?? ??? ???? original data points? ??? points? ?? ? ? (embedding, demsional reduction) ? ??? points set?? ????? ????? ??? ???? "On Spectral Clustering: Analysis and an algorithm" by AY Ng original ??? ?? ??? ??? ??(??? ??? ??)
  • 6. (How?) ??? objects??? ???(similarity)? ?????, ??? ??(similarity matrix)? ???. ?? ???? ???? ????, objects? points? mapping ??? points ??? ???? ?? ? ? ??. ??? ??(similarity) ??? ????, ?? ???(similarity graph)? ????. ?? ???? ????? ??, ???? ?? ??(adjacency matrix)? ????? ??(laplacian matrix)? ????? ??? ???? ??. ??? ????? ??? ???? ??? points set? ????. objects? clusters? ??? ?? Graph? ??! ??? ??? ??? ??.
  • 7. (??? ? ???? & ????) ¢Ù ??? data objects(points) ?1, ¡­ , ? ? ¢Ú ?? objects ??? ???(similarity) ? ??, ?? = ??? ? = ?1, ¡­ , ? ? ? ?1 ???? ??? ??? ???? ?1??? ??, ? ?? ???? ??? ??? ???? ? ???? ??. ?1, ¡­ , ? ? ? ?1 ?2 ?3 ?4 ?1? ?2? ?? ?? ??? ??, ?1? ?3? ?? ?? ?? ??? ??, ?1? ?4? ?? ??? ?? ??.
  • 8. ??? ???? ?? clusters? ??? ??? ??? ? ??. ??? ¡ü ?? ? ?? 2 ¡ý ??? ¡ý ?? ? ?? 2 ¡ü ? ?? ??? ??? ???. ??? ? ? ??? ?? ? ?? ? ??? ? ? ??? ?? ? ?? ?
  • 9. ? ?? ??, ?? ?? ?? ?? ?(eigenvalue)? ???? ?? ??(eigenvector)??. ? = ?1, ¡­ , ? ? ? ? = ?1 ?2 ? ? ? ?? ?? ?? ?? ?1 = ?1 ?2 ? ? ? ?1? ?1? ???? ??? point??, ?2? ?2? ???? ??? point??. ??? ? ? ??? ?? ? ?? ? = min ? 1 2 ? ? ?? ??? points (??? ???? ??)
  • 10. By , this change of representation enhances the cluster-properties in the data, so that clusters can be trivially detected in the new representation.
  • 11. ? Input : Data points ? ?, ? ?, ...,? ? ¡Ê ? ? , Similarity matrix ? ¡Ê ? ?¡Á? , clusters? ? ? ¡ð Similarity matrix? ???? similarity graph? ??(build) ¡ð adjacency matrix ?, diagonal matrix ?? ???? graph laplacian? ?? ¢Ù ? = ? ? ? : unnormalized graph laplacian ¡ð matrix L? ??? ?? ??(eigenvector) ?1, ¡­ , ? ? ¡Ê ? ? ? ?? ? ?? ?? Spectral Clustering Algorithm
  • 12. ¡ð ??? ?? ??? ?(column)? ???? matrix ?? ?? (? ¡Ê ? ?¡Á?) ¡ð ?? ?(row)? ??? data points? ??(interpret) ? ?, ? ?,..., ? ? ¡Ê ? ? ¡ð ??? ??? data points ?1, ?2, ..., ? ?? ?-means ????? ???? ??? clusters? ?? Spectral Clustering Algorithm ?11 ?12 ?21 ?22 ? ?1(??1) ?1? ?2(??1) ?2? ? ? ? ? ?1 ? ?2 ? ? ?(??1) ? ?? ? = ?1, ?2, ¡­ , ? ? = ?11 ?12 ?21 ?22 ? ?1(??1) ?1? ?2(??1) ?2? ? ? ? ? ?1 ? ?2 ? ? ?(??1) ? ?? new data point ? ? new data point ? ? new data point ? ? Dimensional Reduction : ? ¡Á ? ¡ú ? ¡Á ?
  • 13. 1 3 4 2 5 6 8 7 ???? ?? ??(??? ?? ?). 3?? clusters? ??? ???.
  • 15. ?1 ?2 ?3 ?2 ?1 ?3 2? (0 , -0.7071 , 0) ??? points 8?? ?? (0 , 0 , -0.5) (0 , 0 , -0.5) (0 , 0 , -0.5) (0 , 0 , -0.5) (-0.7071 , 0 , 0) (-0.7071 , 0 , 0) (0 , -0.7071 , 0) (0 , -0.7071 , 0) 2? (-0.7071 , 0 , 0) 4? (0 , 0 , -0.5000) ??? ??(Embedding ? ??)
  • 16. - ?? eigenvalue ??? ???? ??? eigenvector? ???? ??? ???? - ? ???? - ?? ??? ??? ? ???? Questions Go to appendix 1
  • 17. ? if, connected graph??? first laplacian eigenvector? constant vector. (?) ? if, disconnected(?-connected components), graph laplacian? block diagonal matrix??, ?? ? laplacian eigenvector? ??? ??. ?????, Go to appendix 2
  • 18. Spectral Clustering? ??? (connected component? 1? ??)
  • 19. ? ???, components? ?? ???(loosely) ?? ?? ???(connected), ? graph laplacian? ??? block diagonal matrix? ?? ?, ? ?? laplacian eigenvector? ???. ¡ð Balanced min-cut? ???? ? ?? laplacian eigenvector? ????. ¡ð ? cluster? ???, ??? eigenvector? ????, ? eigenvector?? ?? ?? ?? ??.(perturbed) ¡ù ??? ??? Davis-Kahan Theorem? ??. Go to appendix 3
  • 20. Spectral Clustering? ??? (connected component? 1?)
  • 21. Spectral Clustering?? ?-means ????? ?????, ??? non-convex ??? ?? data ???? clusters? ??? ? ??.
  • 22. ? Eigengap ¡ð ?? ???? ?? ???? ??. ¡ð choose the number ? such that all eigenvalues ?1,¡­,? ? are very small, but ? ?+1 is relatively large.
  • 23. ? Unnormalized Graph Laplacian ? = ? ? ? ? Normalized Graph Laplacian ? ??? = ?? ? ? ??? ? ? = ? ? ?? ? ? ??? ? ? ? ?? = ??? ? = ? ? ??? ? ???????? ????
  • 24. ? graph? normal??, ???? vertices? ??(approximately) ?? degree? ? ? ??, ?, ? ??, ? ???? ?? ??? clustering ??? ????. ? graph? degrees? ?? broadly distributed ? ??, (?? ??? ??) ¡ð normalized rather than unnormalized ¡ð ? ?? rather than ? ???
  • 25. ? We want to partition such that ¡ð points in different clusters are dissimilar to each other ¢Ù minimize the between-cluster similarity ¢Ú minimize ???(?, ? ? ) ¡ð points in the same cluster are similar to each other ¢Ù maximize the within-cluster similarity ¢Ú maximize ?(?, ?) and ?(? ? , ? ? )
  • 26. ? between-cluster similarity ¡ð ????, ???????? satisfy. ? within-cluster similarity ¡ð ? ?, ? = ? ?, ? ? ? ?, ? ? = ??? ? ? ???(?, ? ? ) ¡ð If ???(?, ? ? ) is small and ???(?) is large, then within-cluster is maximized. ¡ð We can achieve this by minimizing ????. ? Normalized spectral clustering using implements both clustering objective mentioned above, while unnormalized spectral clustering only implements the first objective.
  • 27. ? Spectral clustering?? ??? relaxation? ????. (discrete problem) ? Most importantly, there is no guarantee whatsoever on the quality of the solution of the relaxed problem compared to the exact solution. ? The reason why the spectral relaxation is so appealing is not that it leads to particularly good solutions. ? Its popularity is mainly due to the fact that it results in a standard linear algebra problem which is simple to solve.
  • 28. ? http://snap.stanford.edu/class/cs224w-readings/ng01spectralcluster.pdf ? http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf ? http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Lu xburg07_tutorial_4488%5b0%5d.pdf ? http://ranger.uta.edu/~chqding/papers/KmeansPCA1.pdf ? http://ranger.uta.edu/~chqding/Spectral/spectralA.pdf
  • 29. cluster? ??? ?? ??? ? ? ??? ?? ? ?? ? ??? ? ? ??? ?? ? ?? ? ??? ? ? ? ? ? ?? ???????? ???? by def of ? graph cut Spectral cluster is a way to solve relaxed versions of cut problems.
  • 30. ? ???????? ?1, ?2, ¡­ , ? ? ??? ?? ¡ð Given a partition of ? into ? sets, we define ? indicator vectors ?? = (?1,?, ¡­ , ? ?,?) by ¢Ù ??,? = 1 |? ?| if ?? ¡Ê ?? ¢Ú ??,? = 0 otherwise for all (? = 1, ¡­ , ?; ? = 1, ¡­ , ?) ???????? ?1, ¡­ , ? ? ? ? ?=1 ? ??? ??, ?? ? |??| = ? ?=1 ? ?? ? ??? = ? ?=1 ? ? ? ?? ?? = ??(? ? ??) ??? ?¡Ê? ?¡Á? ??(? ? ??) s.t. ? ? ? = ? by Rayleigh-Ritz thm, sol of this problem : ? eigenvectors of unnormalized laplacian ?
  • 31. ? ???? ?1, ?2, ¡­ , ? ? ??? ?? ¡ð Given a partition of ? into ? sets, we define ? indicator vectors ?? = (?1,?, ¡­ , ? ?,?) by ¢Ù ??,? = 1 ???(? ?) if ?? ¡Ê ?? ¢Ú ??,? = 0 otherwise for all (? = 1, ¡­ , ?; ? = 1, ¡­ , ?) ??? ? ?,¡­,? ? ??(? ? ??) s.t. ? ? ?? = ? by Rayleigh-Ritz thm, sol of this problem : ? eigenvectors of normalized laplacian ? ??? ??? ?¡Ê? ?¡Á? ??(? ? ?? ? ? ??? ? ? ?) s.t. ? ? ? = ? ??? ??? ??????. ? = ? 1 2 ? Back by Rayleigh-Ritz thm, sol of this problem : ? eigenvectors of normalized laplacian ? ??
  • 32. Ideal ??? ?????. ??? connected components? ??? ????. ?? ?? components? connectio? ?? ????. (connected component : component?? ?? ??? path? ??? ??) block diagonal matrix??. ? = ?1 ?2 ? ? ?
  • 33. ¡ù Prove ¡ð ??, connected component? 1??? ??? ??. ??? ?? ? 0? ???? ?? ??? ??? ??. ??? 0 = ¦²?,? ??,? ?? ? ?? 2 ? ? ???. ??,? > 0 ???, ??? ??? ?? ?, ?? ??? ?? ?? ??? ? ???. ???, ?? vertices ?? ??? path? ?? ? ???. ??? ? = ?? where ? ¡Ê ?? ??.
  • 34. ¡ù Prove ¡ð connected component? 1?? ??? ??? ??. ?? ? 0? ???? ?? ?? ? ?? ?? ??? ? ??. ?????? block diagonal ??? ??? ???, connected component? ???? ??? ??? ??? ?? ?? ?? ??? ??? ??,? = 0??? ??, ??? 0? ???. ???, block diagonal ??? ?? ?? ??? ??? ???? ??? ??? 0? eigenvector? component? ??? ???? ? ?. ?? ? eigenvector? ?? eigenvalue 0? ???? eigenvectors??. ? = ?1 ?2 ? ? ? ?1 ?1 0 0 0 0 0 0 0 ?2 ?2 0 0 0 0 0 0 0 0 ? ? ? ?
  • 35. ¡ð ? is a block diagonal matrix, the spectrum of ? is given by the union of the spectra of ??, and the corresponding eigenvectors of ? are the eigenvectors of ??,filled with 0 at the positions of the other blocks. Back
  • 36. ? Perturbation theory ¡ð How eigenvalues and eigenvectors of a matrix ? change if we add a small perturbation ?. ¡ð Most perturbation theorems state that a certain distance between eigenvalues or eigenvectors of ? and perturbed matrix ? ? = ? + ? is bounded by a constant times a norm of ?. ¡ð Strongly connected componen? ideal case?? ????. loosely connected componen? nearly ideal case?? ??. nearly ideal case?? ??? ??? distinct cluster? ??? ??. ??? between-cluster? similarity? ??? 0? ???. ¢Ùideal case? perturbed laplacian matrix(nearly ideal case)? ?????. ¢ÚPerturbation theory? ???, perturbed laplacian? eigenvectors? ideal case ? indicator vectors(eigenvectors of laplacian)? ??? ?? ??. ¢Û??? ideal case? eigenvectors? ???? ??? ??? nearly ideal case? eigenvectors? ???? ??? ??? ??? error term? ????? ?? ? ???? ? ? ??.
  • 37. ¡ð ??? ??? ???? ? properties 2?? ??. ¢Ù eigenvectors? eigenvalues? ??? ??? ??? ??. ¨C ?? ??? ??. ?? ?? ??? ??. ¢Ú eigenvector? components? 0???? "safely bounded away" ??? ??. ¨C ?, ? ?? = ??1 ?? ? property? ? ????. ¨C ? ??? = ?? 1 2 ??? 1 2? eigenvector? ? 1 2 ? ? ? ??. ???, vertices? degree? ??? ?? ???, degre? ?? ?? vertices? ????, eignevectors?? ???? entries? ?? 0? ?? ??? ??. ??? ?? ???? ??? row- normalization step? ????. ¨C ? ???? very low degrees? ??? vertices? ??? ?, ???? ???? ??. Back