소스코드가있는글21 dense subgraph 찾기 구현 (MCODE) 지난 번 글에서 언급했던 알고리즘을 C++로 직접 구현해 보자. 실제로 사용한 예는 다음과 같다. 원래의 network 은 다음과 같다. 우리는 다음과 같은 network 에서 dense 한 sub-graph 즉, edge가 많이 연결된 sub-graph를 뽑아 내어야 한다. source network 의 sif 파일은 다음과 같다. 위에서 dense한 subgraph 를 지금 설명할 코드로 뽑아 내면 다음과 같다. node 를 score로 정렬한 이후 seed로 사용되는데, 높은 점수를 갖는 노드부터 sub-graph (난 계속 cluster 라는 이름을 사용했다. 이 글 이후에도 sub-graph 나 cluster를 사용한다)를 찾기 때문에 cluster 번호가 커질수록 cluster의 density.. 2010. 12. 3. Fisher's linear discriminant 구현 지난 번에 알아 본 Fisher's Linear Discriminant 의 원리를 이제 C++로 구현해 보자. 또한 지난 번 글에서 matlab 으로 테스트 해 보았던 m 코드의 일부를 약간 설명한다. Matlab 에서의 matrix 를 다루는 방식이 FLD 원리 편에서 본 matrix 와 조금은 다르기 때문에 약간의 설명이 필요하다. 또한 matrix inverse 를 구하는 것을 직접 구현하기에는 무리가 따르므로 다른 사람이 구현해 놓은 것을 사용한다. 우리가 직접적으로 계산해야 하는 것은 다음의 수식이다. w는 벡터이고, 우리는 이 벡터의 '방향'만이 필요하므로 위에서 r 은 1로 둔다. Sw 와 m1, m2 는 다음과 같다. 우선 m1 과 m2 부터 구해 보자. 실제로 우리가 다룰 data 는 위.. 2010. 12. 3. 주어진 집합의 모든 부분집합을 구하기 문제는, 말 그대로 간단하다. 주어진 배열의 모든 부분집합을 구해내는 것. 짱구 한 10분 굴려 나온 코드의 아이디어를 스케치 해보자. 우리가 일반적으로 주어진 배열에 대하여 k-개의 원소로 된 부분집합을 다 구하고자 할 때는 다음과 같은 절차를 따르게 된다. 위에서 붉은 색이 선택한 요소라 하자. 위 그림은 2개의 원소로 된 부분집합을 모두 구하는 절차를 표현한 것이다. 우선 가장 왼쪽의 요소 2개를 선택할 것이다. 그 후, 가장 오른쪽 요소를 한 칸 오른쪽으로 옮기겠지. 이런 식으로 계속 오른쪽으로 한 칸씩 옮기면서 2개로 된 부분집합을 만들어 나가는 것이다. 그러다 더이상 움직일 수 없다면 이제 바로 앞의 요소를 한 칸 오른쪽으로 옮기는 것이다. 물론 이 단계에서 가장 오른쪽에 있던 요소는 다시 앞.. 2010. 8. 2. 두 단어의 '유사도'를 측정하기 (resemblance) 구글이나 네이버에서 검색을 할 때, 영어 단어를 '정확히' 입력하지 않았을 경우, '비슷한' 단어로 검색할 것을 추천하는 것을 본 경험이 있을 것이다. 그와 같이, 두 단어가 정확히 같은 것인가를 판단하는 것이 아니라, 대충 비슷한 것인가를 판단할 수 있는 방법을 살펴 보자. 즉, '비슷한 정도'를 수치화 할 수 있는 방법을 살펴 보자. 기본적인 아이디어는 단어를 잘게 자른 조각(그것을 shingle 이라 하자)들을 모은 후, 그 조각들이 많이 비슷하면 비슷할수록 두 단어가 비슷하다는 것이다. 예를 들어 보자. adenophorae radix 와 adenophora 를 비교하는 모습을 살펴 보자. 논의의 편의를 위하여 shingle 의 길이를 2 개로 제한하자. adenophorae radix --> a.. 2010. 7. 6. 이전 1 2 3 4 5 6 다음
