similarity measure

Chapter 3 Similarity Measures Data Mining Technology

Chapter 3 Similarity Measures Written by Kevin E. Heinrich Presented by Zhao Xinyou [email_address] 2007.6.7 Some materials (Examples) are taken from Website.

Searching Process Input Text Process Index Query Sorting Show Text Result Input Text Index Query Sorting Show Text Result Input Key Words Results Search ,[object Object],[object Object],[object Object],[object Object]

Similarity Measures ,[object Object],[object Object],[object Object],[object Object],PP27-28

Classic Similarity Measures ,[object Object],[object Object],[object Object],PP28

Conversion ,[object Object],[object Object],[1, 10] [0, 1] s’ = (s – 1 ) / 9 Generally, we may use : s’ = ( s – min_s ) / ( max_s – min_s ) Linear Non-linear PP28

Vector-Space Model-VSM ,[object Object],PP28-29

Example ,[object Object],[object Object],[object Object],PP28-29 If similarity(q,d i ) > similarity(q, d j ) We may get the result d i is more relevant than d j

Simple Measure Technology Documents Set PP29 Retrieved A Relevant B Retrieved and Relevant A ∩B Precision = Returned Relevant Documents / Total Returned Documents Recall = Returned Relevant Documents / Total Relevant Documents P(A,B) = |A ∩B| / |A| R(A,B) = |A ∩B| / |B|

Example--Simple Measure Technology PP29 Documents Set A,C,E,G, H, I, J Relevant B,D,F Retrieved & Relevant W,Y Retrieved |B| = {relevant} ={A,B,C,D,E,F,G,H,I,J} = 10 |A| = {retrieved} = {B, D, F,W,Y} = 5 |A∩B| = {relevant} ∩ {retrieved} ={B,D,F} = 3 P = precision = 3/5 = 60% R = recall = 3/10 = 30%

Precision-Recall Graph-Curves ,[object Object],[object Object],PP29-30 One Query Two Queries Difficult to determine which of these two hypothetical results is better

Similarity measures based on VSM ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],PP30

Dice Coefficient-Cont’ ,[object Object],[object Object],PP30 ,[object Object]

Dice Coefficient-Cont’ ,[object Object],PP30 α>0.5 : precision is more important α<0.5 : recall is more important Usually α=0.5

Overlap Coefficient PP30-31 Documents Set A queries B Documents

Jaccard Coefficient-Cont’ PP31 Documents Set A queries B Documents

Example- Jaccard Coefficient ,[object Object],[object Object],[object Object],[object Object],[object Object],PP31

Cosine Coefficient-Cont’ PP31-32 (d 21 ,d 22 ,…d 2n ) (d 11 ,d 12 ,…d 1n ) (q 1 ,q 2 ,…q n )

Example-Cosine Coefficient ,[object Object],[object Object],[object Object],C ( D1 , Q ) = = 10/ √ (38*4) = 0.81 C ( D2 , Q ) = 2 / √ (59*4) = 0.13 PP31-32 (3,7,1) (2,3,5) (0,0,2)

Asymmetric PP31 dj di W ki -->w kj

Other Measures ,[object Object],[object Object],[object Object],[object Object],[object Object],PP32

Comparison Simple matching Dice’s Coefficient Cosine Coefficient Overlap Coefficient Jaccard’s Coefficient |A|+|B|-|A ∩ B| ≥(|A|+|B|)/2 |A| ≥ |A ∩ B| |B| ≥ |A∩B| (|A|+|B|)/2 ≥ √ (|A|*|B|) √ (|A|*|B|) ≥ min (|A|, |B|) O≥C≥D≥J PP34

Example- Documents-Term-Query -Cont’ ,[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],[object Object],T1: search(ing) T2: Engine(s) T3: Models T4: database T5: query T6: language T7: documents T8: measur(es,ing) T9: conceptual T10: dependence T11: domain T12: structure T13: similarity T14: semantic T15: ontologies T16: information T17: retrieval Query: Semantic similarity measures used by search engines and other information searching mechanisms PP33

Example- Term-Document Matrix -Cont’ Matrix[q][A] PP34 1 1 1 1 1 2 Q 1 1 1 1 1 D7 1 1 1 D6 1 1 1 1 D5 1 1 1 D4 1 1 1 1 D3 1 1 1 D2 1 1 1 D1 T17 T16 T15 T14 13 T12 T11 T10 T9 T8 T7 T6 T5 T4 T3 T2 T1

Final Results PP34 O≥C≥D≥J

Current Applications ,[object Object],[object Object],[object Object],PP35-38

similarity measure

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (20)

Similar to similarity measure

Similar to similarity measure (20)

More from ZHAO Sam

More from ZHAO Sam (8)

Recently uploaded

Recently uploaded (20)

similarity measure