Decentralized Orthogonal Iteration (DOI) + Spectral clustering 

  

On spectral clustering analysis and an algorithm.pdf <= Spectral clustering에 사용된 논문 

A Decentralized Algorithm for Spectral Analysis.pdf   <= Decentralized Orthogonal Iteration에 사용된 논문 


 DOI 는 Distributed algorithm 중에 하나이다. 이 알고리즘을 통해서 전체 Graph G의 Adjacency matrix A의 top k eigenvector들을 구할 수 있다.  이는 Orthogonal Iteration (OI)를 Push-sum (PS) algorithm이라는 consensus 알고리즘을 통해서 distributed 하게 구현한 것이다. 

 이렇게 구한 k 개의 eigenvector들은 전체 Graph의 spectral clustering에 사용될 수 있다. Spectral clustering이란 노드와 엣지로 이뤄진 (원과 연결선) 그래프 구조를 적절히 나누는 알고리즘을 의미한다. 여기선 node와 node 사이의 거리에 반비례하는 weight를 엣지에 부여했지만 이를 페이스북 같은 것에 고려할 때는 두 사용자 간의  친밀도를 나타낼 수 있는 주고 받은 메세지의 수나 태그된 사진의 수 등으로 표현될 수 있을 것이다. 

 

 DOI 와 같은 분산 처리 기법을 사용할 경우 얻을 수 있는 이점은 크게 두 가지이다. 하나는 하나의 성능 좋은 서버가 모든 연산을 할 필요가 없다는 것이다. 즉 페이스북과 같이 사용자가 수천만에 달하는 시스템의 경우 수천만*수천만 의 엄청난 크기의 matrix의 eigenvector를 구해야하는데 이는 실질적으로 불가능하다. 두 번째 이점은 privacy이다. 최근에 프리즘과 같은 CIA의 감시 도청 시스템에 대한 말이 많이 대두되는 시기에 분산 처리를 할 경우 각 노드에 해당하는 사용자의 PC에서 자신의 neighbor (이 경우는 친구)의 정보만을 사용하므로 중앙 서버에서는 따로 개인 정보를 볼 필요가 없다. 


1. Orthogonal Iteration 


매트랩 코드 main_OI.m

더보기

 

2. Push Sum 


매트랩 코드 main_PS.m

더보기

 

3. Decentralized Orthogonal Iteration + Spectral Clustering 


*Spectral Clustering Algorithm 



매트랩 코드 main_DOI.m

더보기

 

추가적으로 필요한 코드들 


1. make_agent_formation.m 

더보기


2. make_adjacency_matrix.m 

더보기


3. qr_GS.m 

더보기


 DOI + Spectral clustering 결과 

위의 그림에서 같은 색과 숫자가 부여된 노드 (네모) 들이 같은 cluster로 분류된 애들이다. 대충 잘 된다. kmeans cluster의 distance measure는 cosine distance를 사용하였다. 이상하게 유클리디안 distance를 사용하면 결과가 잘 나오지 않는다.. 





저작자 표시 비영리 동일 조건 변경 허락
신고
« PREV : 1 : ··· : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : ··· : 578 : NEXT »