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

Presentation on theme: "태그를 이용한 웹 페이지간의 유사도 측정 방법 (Measuring Web Page Similarity using Tags)"— Presentation transcript:

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

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

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

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

5 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.

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

7 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

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

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

10 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

11 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 })

12 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)

13 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 }) }

14 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 })

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

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

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

18 WSET 실험결과-유사한 웹 페이지 Web Pages Tag Information 1
[design, illustration, portfolio, …] 2 [typography, design, inspiration, font, …] 3 [design, portfolio, inspiration, typography, …] 4 [illustration, design, portfolio, graphic, …] 5 [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

19 WSET 실험결과 -완전히 다른 웹 페이지 Web Pages Tag Information 6
[rails, ruby, osx, mac, development, …] 7 [education, teaching, learning, economics, …] 8 [photography, legal, law, copyright, …] 9 [solar, energy, home, green, …] 10 [coffee, recipe, food, dessert, cooking, …] 11 [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

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

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

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

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

24 완전히 다른 태그에 대해 민감 Web Pages Tag Information 1
[design, illustration, portfolio, …] 2 [typography, design, inspiration, font, …] 3 [design, portfolio, inspiration, typography, …] 4 [illustration, design, portfolio, graphic, …] 5 [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

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

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