태그를 이용한 웹 페이지간의 유사도 측정 방법 (Measuring Web Page Similarity using Tags)

목적 소셜 북마킹(social bookmarking) 웹 페이지에 주제, 내용을 나타내는 태그 부착 태그를 이용한 두 웹페이지 간의 의미적 유사 도 측정하는 방식 WSET(Web Page Similariy Based on Entire Tags)을 제안 의미적 유사도(semantic similarity) : 웹 페이지들이 얼마나 비슷한 주제 또는 내용을 다루고 있는지를 측정하는 척도

목적 태그를 이용한 두 웹페이지 간의 의미적 유사 도 측정하는 방식 WSET(Web Page Similariy Based on Entire Tags)을 제안 의미적 유사도(semantic similarity) : 웹 페이지들이 얼마나 비슷한 주제 또는 내용을 다루고 있는지를 측정하는 척도

이전의 유사도 측정 방법들 텍스트 데이터를 통한 측정 유사 페이지 검색 방법(HITS 알고리즘) 단어 출현 빈도 벡터(term frequency) 생성 후, 벡터간의 코사인 유사도(cosine similarity) 계산 단점 : 텍스트 외 형식의 데이터 측정 불가 유사 페이지 검색 방법(HITS 알고리즘) 주어진 페이지와 하이퍼링크로 연결된 페이지들 을 하나의 그룹으로 만들고 그룹 중 가장 권위있 다고 판단되는 페이지를 주어진 페이지와 유사한 페이지라고 판단 단점 : 하이퍼링크 연결이 적으면 유사한 페이지 를 못 찾음 http://en.wikipedia.org/wiki/Vector_space_model#Example:_tf-idf_weights http://www.miislita.com/term-vector/term-vector-1.html

Term frequency vector In the classic vector space model proposed by Salton, Wong and Yang [1] the term specific weights in the document vectors are products of local and global parameters. The model is known as term frequency- inverse document frequency model. The weight vector for document d is  , where and tft,d is term frequency of term t in document d (a local parameter)  is inverse document frequency (a global parameter). | D | is the total number of documents in the document set;   is the number of documents containing the term t. Using the cosine the similarity between document dj and query q can be calculated as: In a simpler Term Count Model the term specific weights do not include the global parameter. Instead the weights are just the counts of term occurrences: wt,d = tft,d.

이전의 유사도 측정 방법들 HITS알고리즘 (Hiperlink-Induced Topic Search) 텍스트 데이터를 통한 측정

Social-SimRank(SSR)을 이용한 방식 NA : 태그의 개수 2차원 행렬 SA=NAⅹNA 두 웹페이지 P, Q의 각각 태그 [t1,t2,…,tn], [u1,u2,…,um] P와 Q의 유사도 Sp(P,Q)=SA(t1,u1)+SA(t1,u2)+…+SA(tn,um) Sp(P,Q)= n m Sp(P,Q)=∑ ∑ SA(ti,uj) Sp(P,Q)=i=1 j=1

Social-SimRank(SSR)을 이용한 방식 단점 : 여러 의미로 쓰이는 단어에 대해 문제가 생김 덧셈을 통하여 관계가 없어도 높게 나옴 예 : java – 프로그래밍 언어, 인도네시아의 섬

SMM(Separable Mixture Model) 동시 발생 데이터(co-occurrence data)를 위한 통계적 모델 동시 발생 데이터 : 동시에 발생하는 두 가지 다른 종류의 데이터 ex) 웹 페이지, 태그 각각 추상 클래스가 발생할 확률과 데이터 각 각이 K개의 추상 클래스 각각에 대해 나타날 조건부 확률을 알려줌

SMM을 웹 페이지와 태그에 적용 Class 1 Class 2 p(Cα) 0.75 0.25 p(‘programming’| Cα) 0.5 p(‘java’| Cα) p(‘tour’| Cα) p(A|Cα) 0.33 p(B|Cα) p(C|Cα) p(D|Cα) 1.0

WSET Web page Similarity based on Entire Tags p(t_{ 1 }\wedge u_{ 1 })=p(t_{ 1 }|u_{ 1 })\cdot p(u_{ 1 })\\ =\sum _{ \alpha =1 }^{ C }{ p(t_{ 1 }|C_{ \alpha }) } p(C_{ \alpha }|u_{ 1 })\cdot p(u_1)\\ =\sum _{ \alpha =1 }^{ C }{ p(t_{ 1 }|C_{ \alpha }) } \frac { p(u_{ 1 }|C_{ \alpha })p(C_{ \alpha }) }{ p(u_{ 1 }) } \cdot p(u_{ 1 })\\ =\sum _{ \alpha =1 }^{ C }{ p(t_{ 1 }|C_{ \alpha }) } p(u_{ 1 }|C_{ \alpha })\cdot p(C_{ \alpha })

WSET p(t_1 \wedge u_1)=p(u_1 \wedge t_1)= \sum^C_\alpha p(C_\alpha) p(t_1|C_\alpha )p(u_1 |C_\alpha) p(t_{ 1 }\wedge t_{ 2 }\wedge u_{ 1 })=p(t_{ 1 }\wedge t_{ 2 })\cdot p(u_{ 1 }|t_{ 1 }\wedge t_{ 2 })\\ =p(t_{ 1 })\cdot p(t_{ 2 }|t_{ 1 })\cdot p(u_{ 1 }|t_{ 1 }\wedge t_{ 2 })\\ =p(t_{ 1 })\cdot p(t_{ 2 }|t_{ 1 })\cdot \frac { p(t_{ 1 }\wedge t_{ 2 })p(u_{ 1 }) }{ p(t_{ 1 }\wedge t_{ 2 }) } \\ =\sum _{ \alpha =1 }^{ C } p(t_{ 1 }|C_{ \alpha })p(t_{ 2 }|C_{ \alpha })p(C_{ \alpha })\cdot \frac { p(t_{ 1 }\wedge t_{ 2 }|C_{ \alpha })p(C_{ \alpha }|u_{ 1 })p(u_{ 1 }) }{ p(t_{ 1 }\wedge t_{ 2 }|C_{ \alpha })p(C_{ \alpha }) } \\ =\sum _{ \alpha =1 }^{ C } p(t_{ 1 }|C_{ \alpha })p(t_{ 2 }|C_{ \alpha })p(C_{ \alpha })\cdot \frac{p(C_\alpha|u_1) p(u_1)}{p(C_\alpha)} \\=\sum _{ \alpha =1 }^{ C } p(t_{ 1 }|C_{ \alpha })p(t_{ 2 }|C_{ \alpha })p(C_{ \alpha })\cdot \frac{p(u_1|C_\alpha) p(C_\alpha)}{p(u_1)}\cdot \frac{p(u_1)}{p(C_\alpha)} \\=\sum^C_{\alpha=1} p(t_1 |C_\alpha)p(t_2|C_\alpha)p(u_1|C_\alpha)p(C_\alpha)

WSET p(t_{ 1 }\wedge t_{ 2 }\wedge ...\wedge t_{ n }\wedge u_{ 1 }\wedge u_{ 2 }\wedge ...\wedge u_{ m })\\ =\sum _{ \alpha =1 }^{ C }{ \prod _{ i=1 }^{ n }{ p(t_{ i }|C_{ \alpha }) } \cdot \prod _{ j=1}^{m }{ p(u_j | C_\alpha ) \cdot p(C_\alpha) } } S_{ \sigma }(P,Q)=\sqrt [ n+m ]{ p(t_{ 1 }\wedge t_{ 2 }\wedge ...\wedge t_{ n }\wedge u_{ 1 }\wedge u_{ 2 }\wedge ...\wedge u_{ m }) }

WSET Web page Similarity based on Entire Tags SMM을 이용해 클래스들로 분류, 각 태그들이 각 클래스에서 나타날 확률을 이용해 유사도 측정 p(t_{ 1 }\wedge u_{ 1 })=p(t_{ 1 }|u_{ 1 })\cdot p(u_{ 1 })\\ =\sum _{ \alpha =1 }^{ C }{ p(t_{ 1 }|C_{ \alpha }) } p(C_{ \alpha }|u_{ 1 })\cdot p(u_1)\\ =\sum _{ \alpha =1 }^{ C }{ p(t_{ 1 }|C_{ \alpha }) } \frac { p(u_{ 1 }|C_{ \alpha })p(C_{ \alpha }) }{ p(u_{ 1 }) } \cdot p(u_{ 1 })\\ =\sum _{ \alpha =1 }^{ C }{ p(t_{ 1 }|C_{ \alpha }) } p(u_{ 1 }|C_{ \alpha })\cdot p(C_{ \alpha })

WSET 실험결과-샘플 SSR WSET [Java, Programming, Software] [Java, Travel, Island] 0.0521 [Eclipse, Java, Programming] [Java, Island, Tour] 0.0942 1.1E-26

WSET 실험결과-실제 delicious.com 10,000개의 웹 페이지 총 6천 여 태그 50개 클래스 최소 200번 이상 태그 붙여진 웹 페이지 총 6천 여 태그 이 중 오타 등 이유로 상위 60%(약 3,600)만 사용 50개 클래스

WSET 실험결과-유사한 웹 페이지

WSET 실험결과-유사한 웹 페이지 Web Pages Tag Information 1 http://www.graphdrome.com/ [design, illustration, portfolio, …] 2 http://inspiredology.com/graphic-design/typography [typography, design, inspiration, font, …] 3 http://feltron.com/ [design, portfolio, inspiration, typography, …] 4 http://www.maxomatic.net/ [illustration, design, portfolio, graphic, …] 5 http://www.adrianjohnson.org.uk/ [illustration, design, portfolio, …] page 2 3 4 5 1 0.017 0.018 0.069 0.038 0.016 0.015 0.011 0.042 0.031 0.021 0.027 0.030 0.023 0.028 0.046 SSR Results WSET Results

WSET 실험결과 -완전히 다른 웹 페이지 Web Pages Tag Information 6 http://developer.apple.com/tools/developonrailsleopard.html [rails, ruby, osx, mac, development, …] 7 http://www.overcomingbias.com/2008/02/my-favorite-lia.html [education, teaching, learning, economics, …] 8 http://www.photoattorney.com/ [photography, legal, law, copyright, …] 9 http://www.sungevity.com/#start [solar, energy, home, green, …] 10 http://www.yumsugar.com/1663993 [coffee, recipe, food, dessert, cooking, …] 11 http://www.chami.com/html-kit/services/favicon/ [favicon, webdesign, icon, tools, …] page 7 8 9 10 11 6 7.8E-5 6.1E-5 1.5E-5 1.5E-4 6.7E-5 SSR Results WSET Results

WSET 실험결과 -완전히 다른 웹 페이지

WSET 실험결과 -다양한 의미를 가지는 태그 webdev, howto

고려 사항 웹 페이지-태그 데이터의 적절한 샘플링 최신 데이터를 반영하여 SMM을 주기적 구축 필요 적절한 수의 K개의 추상 클래스 지정

결론 SMM을 이용해 각 태그들이 클래스에 나타날 확률이 아닌 해당 태그 전체가 같은 클래스에 서 나타날 확률을 계산하여 의미적 유사도를 측정하는 방식에 더 좋은 결과를 보임

완전히 다른 태그에 대해 민감 Web Pages Tag Information 1 http://www.graphdrome.com/ [design, illustration, portfolio, …] 2 http://inspiredology.com/graphic-design/typography [typography, design, inspiration, font, …] 3 http://feltron.com/ [design, portfolio, inspiration, typography, …] 4 http://www.maxomatic.net/ [illustration, design, portfolio, graphic, …] 5 http://www.adrianjohnson.org.uk/ [illustration, design, portfolio, …] page 2 3 4 5 1 0.017 0.018 0.069 0.038 0.016 0.015 0.011 0.042 0.031 0.021 0.027 0.030 0.023 0.028 0.046 SSR Results WSET Results

완전히 다른 태그에 대해 민감 http://www.graphdrome.com/ http://www.maxomatic.net/ Tag : illustration,design,portfolio,art,typography,grap hics,inspiration,drawing,illustrator,designer http://www.maxomatic.net/ Tags : illustration,design,portfolio,inspiration,collage, barcelona,art,graphics,graphic,illustrator

여러 의미 가진 태그 제거에 우수 여러 의미를 지닌 태그로 인해 의미적 유사성 이 높게 나오는 것을 방지하는데 우수 다만, 완전히 다른 태그 하나가 끼어들어 있으 면 더 유사한 웹 페이지더라도 의미적 유사도 가 낮게 나올 수 있음