LINGO Algorithm

SVD나 NMF같은 Dimension reduction skill은 어디에 쓰나 했더니 이런곳에 사용을 하는군요

-------------------------------------------------------------------------------------------------

일반적으로 OPEN 클러스터링 알고리즘은 컨텐츠를 그룹핑 한후에 이를 기반으로 Label을 추출한다. 경우에 따러서 읽기 어려운 Label이 추출되기도 하는데 LINGO는 이런문제를 해결하기 위해 사람이 이해할수 있는 Label을 먼저 추출하고 이를 기반으로 클러스터링을 수행한다.

입력문서에서 고빈도 구를 추출하고, SVD를 사용해서 Term-Document matrix의 차원을 축소한 후에,  검색결과에서 숨겨진 토픽을 추출한다. 마지막으로 추출된 토픽으로 그룹을 매치하고 각 문서를 그룹에 할당한다.

 

 

t = 5 Term이고                     d = 7 documents

 

T1 = Information                  D1 = Large Scale Singular Value Computations

T2 = Singular                      D2 = Software for the Sparse Singular Value Decomposition

T3 = Value                         D3 = Introduction to Modern Information Retrieval

T4 = Computations              D4 = Linear Algebra for Intelligent Information Retrieval

T5 = Retrieval                     D5 = Matrix Computations

                                        D6 = Singular Value Analysis of Cryptograms

                                        D7 = Automatic Information Organization

 이것을 TF/IDF를 사용해서 Matrix를 만들면

A =

	d1	d2	d3	d4	d5	d6	d7	DF(document frequency)	IDF
information	0	0	1	1	0	0	1	3	0.37
singular	1	1	0	0	0	1	0	3	0.37
value	1	1	0	0	0	1	0	3	0.37
computations	1	0	0	0	1	0	0	2	0.54
retrieval	0	0	1	1	0	0	0	2	0.54

 

여기에 Column length normalization을 실행하면 아래와 같은 결과를 얻을수 있다.( column length normalization은 아마도 Input document에서 stop word를 제거한 후의 term의 개수를 곱한것을 의미하는 것 같다 )

A =

information	0.00	0.00	0.56	0.56	0.00	0.00	1.00
singular	0.49	0.71	0.00	0.00	0.00	0.71	0.00
value	0.49	0.71	0.00	0.00	0.00	0.71	0.00
computations	0.72	0.00	0.00	0.00	1.00	0.00	0.00
retrieval	0.00	0.00	0.83	0.83	0.00	0.00	0.00

 

 

Matrix A를 SVD를 사용해서분해하면

A = USV(^t)

 

U =

0.00	0.75	0.00	-0.66	0.00
0.65	0.00	-0.28	0.00	-0.71
0.65	0.00	-0.28	0.00	0.71
0.39	0.00	0.92	0.00	0.00
0.00	0.66	0.00	0.75	0.00

 

P = 

	singular Value	Information Retrieval	information	singular	value	computations	retrieval
information	0.00	1.00	1.00	0.00	0.00	0.00	0.00
singular	1.00	0.00	0.00	1.00	0.00	0.00	0.00
value	1.00	0.00	0.00	0.00	1.00	0.00	0.00
computations	0.00	0.00	0.00	0.00	0.00	1.00	0.00
retrieval	0.00	1.00	0.00	0.00	0.00	0.00	1.00

P =

0.00	0.56	1.00	0.00	0.00	0.00	0.00
0.71	0.00	0.00	1.00	0.00	0.00	0.00
0.71	0.00	0.00	0.00	1.00	0.00	0.00
0.00	0.00	0.00	0.00	0.00	1.00	0.00
0.00	0.83	0.00	0.00	0.00	0.00	1.00

 

M = U^t * P ( Matrix U에서 유의미한 차원까지만 선택한다 )

=

0.82	0.00	0.00	0.65	0.65	0.39	0.00
0.00	0.97	0.75	0.00	0.00	0.00	0.66

 

C = Q^t * A =

0.69	1.00	0.00	0.00	0.00	1.00	0.00
0.00	0.00	1.00	1.00	0.00	0.00	0.56

 

 

 

----------------------------------------------------------------------------------------------

Information Retrieval[ 1.0 ]

[1.00] Introduction to Modern Information Retrieval

[1.00] Linear Algebra for Intelligent Information Retrieval

[0.56] Automatic Information Organization

 

----------------------------------------------------------------------------------------------

Singular Value[0.95]

[1.00] Software for the Sparse Singular Value Decomposition

[1.00] Singular Value Analysis of Cryptograms

[0.69] Large Scale Singular Value Computations

----------------------------------------------------------------------------------------------

Other Topics

Matrix Computations

 

----------------------------------------------------------------------------------------------

http://www.cs.put.poznan.pl/dweiss/site/publications/download/iipwm-osinski-weiss-stefanowski-2004-lingo.pdf

http://project.carrot2.org/publications/osinski-2003-lingo.pdf

 

COMMENT :

Label을 추출하는 가장 손쉬운 방법으로 STC(Suffix Tree Clustering)다. STC는 실행 속도가 빠르고 실행 결과가 직관적이지만 간혹 의미 없는 구를 추출하는 경우가 있어 약점으로 지적되어 왔다. 이를 보완한 방법론중에 SHOC( Semantic Hierarchical  online Clustering)라는 것이 있는데 이 방법은 Frequent Phrase를 추출할때  Suffix Tree대신 Suffix Array를 사용하고, 추출된 구를 SVD로 Base cluster를 구축하고 이를 기반으로 Hierarchical하게 클러스터를 생성한다.( SHOC에 대한 논문을 읽어보지 않아서 정확한 방법은 잘 모르겠다 )

LINGO는 SHOC에서 힌트를 얻어 의미 있는 Label을 구별하기 위해 SVD(또는 NMF, LNMF등)로 차원 축소후 Label과 차원 축소된 문서와의 관계를 계산하는 방법을 사용한다.