A Hybrid Approach for XML Similarity

จาก XML ทั้งสามเอกสาร แสดงให้เห็นว่า XML ทั้งสามมีความคล้ายคลึงกัน
การที่จะทำการค้นหาว่าเอกสารไหนมีความคล้ายคลึงกันมากกว่ามีหลายวิธี
หนึ่งในวิธีนั้นคือ Hybrid Approach

Hybrid Approach เป็นวิธีการหาคำที่มีความหมายคล้ายกัน โดยรวมวิธี Edge Counting, Information Content และ Feature Based เข้าด้วยกัน วิธีนี้ นำเสนอโดย J.Tekli และคณะ โดยมีขั้นตอนดังนี้

1. ตรวจสอบโครงสร้างของสอง tree (XML มองได้ว่าเป็น tree) ที่คล้ายกัน วิธีนี้ใช้ความคิดของวิธี Edit Distance โดยสนใจการเพิ่ม การลบ และการปรับปรุงข้อมูลของ node ใน tree เพื่อหาค่าความแตกต่างของสอง trees เช่น กำหนดให้มีสอง tree A และ B และหาค่าที่น้อยสุดที่จะเปลี่ยน A ให้คล้ายกับ B มากที่สุด (ค่ายิ่งน้อยเท่าไหร สอง tree ก็เหมือนกันมากเท่านั้น (ในลักษณะโครงสร้าง tree)) โดยมีสูตรคำนวนดังนี้



ตารางข้างล่างแสดงตัวอย่างการคำนวนหาค่า Edit Distance ที่น้อยที่สุดของ XML tree A และ tree B



2. การวัดค่าคำที่มีความหมายคล้ายกัน (Semantic Similarity Measure) วิธีนี้ใช้หลักของ IR เข้ามาช่วย โดยใช้วิธีของ Lin ซึ่งมีสูตรคำนวนดังนี้



w1 และ w2 คือคำที่ต้องการ
c1 และ c2 คือแนวคิดในฐานความรู้ของโครงสร้างตามลำดับชั้น ของคำ w1 และ w2 ตามลำดับ
c0 คือคำที่เหนือกว่า (ancestor) ของคำ c1 และ c2
p(c) แสดงถึงความน่าจะเป็นของคำที่ตรงกับแนวคิดของ c โดย p(c) สามารถคำนวนได้ดังนี้

p(c)= freq(c)/ N

freq(c) คือ จำนวนของคำ c ที่ปรากฎในเอกสาร
N คือจำนวนของคำทั้งหมด
ซึ่งสูตรนี้คือสูตรเดียวกับ tf ของ TF*IDF

ผลลัพธ์จะได้ค่าออกมาระหว่าง 0 กับ 1 ค่าที่ใกล้ 1 มากกว่า แสดงว่ามีความคล้ายกันมากกว่า ดังตาราง



3. การกำหนดค่าความคล้ายของคำ (Label Semantic Similarity Cost) ขั้นตอนนี้สนใจคำนวนการเพิ่ม, ลบ, และปรับปรุงคำ จากตัวอย่าง เปรียบเทียบความคล้ายของ XML element ในเอกสาร A-B และ เอกสาร A-C เช่น Academy-College จะมีค่าความคล้ายมากกว่า Academy-Factoryเช่นเดียวกับ Professor-Lecturer จะมีค่าสูงกว่า Professor-Supervisor ดังนั้นค่า Sim(A,B) น่าจะมีค่ามากกว่า Sim(A,C) โดยมีสูตรคำนวนต่างๆดังนี้



ค่าของ initial และ คำที่จะเปลี่ยน (x.l และ y.l ตามลำดับ) ยิ่งมาก ค่าของ update operation ยิ่งน้อย
เช่น SimSem(x.l,y.l) = 1 ค่า CostUpd(x,y) = 0 หมายความว่าไม่มีการเปลี่ยนแปลง



สำหรับการเพิ่มและการลบ จะสนใจค่าของคำที่เหนือกว่า (ancestor) ด้วย
ค่าของ การเพิ่ม/การลบคำที่ใกล้เคียงกับคำที่เหนือกว่ายิ่งมาก ค่า insertion/deletion operation cost จะยิ่งน้อย

4. ค่าความลึกของ Node (Node Depth Cost)
ถ้ามีการแก้ไขใน root node ของ XML จะมีผลมากกว่าการแก้ไข node อื่นๆ เช่น จาก a.xml ถ้าแก้ไข Acadamy เป็น Hospital จะทำให้ความหมายของ XML นั้นเปลี่ยนไปมาก ดังนั้น จึงมีการนำค่าความลึกของ node มาคำนวนในการเปรียบเทียบด้วย ถ้า node อยู่ใกล้ root มากเท่าไหร่ จะมีค่ามากเท่านั้น ดังสูตรคำนวนดังนี้



0p คือ การเพิ่ม การลบ หรือการแก้ไข
x.d คือความลึกของ node ที่จะทำการแก้ไข
ค่าสูงสุดจะมีค่า = 1 ถ้ามีการแก้ไขที่ root และค่าจะลดลงเรื่อยๆ ถ้าแก้ไขใน node ที่ต่ำลงมา

5. Semantic Cost Model (SCM) การคำนวนหาคำที่มีความหมายคล้ายกันระหว่างเปรียบเทียบเอกสาร XML ใช้สูตรดังนี้



0p คือการเพิ่ม การลบ หรือการแก้ไข

ผลลัพธ์ที่ได้จากการเปรียบเทียบ XML A, B และ C ดังตารางข้างล่าง



ตารางเปรียบเทียบระหว่าง A และ B


ตารางเปรียบเทียบระหว่าง A และ C

ผลลัพธ์ได้ดังนี้
Sim_SCM(A,B) = 1 / 1 + Dist_SCM(A,B) = 1/1 + 0.3586 = 0.7361
Sim_SCM(A,C) = 1 / 1 + Dist_SCM(A,C) = 1/1 + 1.2628 = 0.4418
จากสมการข้างต้น สรุปได้ว่า เอกสาร A และ B ใกล้เคียงกันมากกว่า เอกสาร A และ C ในลักษณะของโครงสร้างเอกสารที่คล้ายกัน

ที่มา : J.Tekli, R. Chbeir, K. Yetongnon, “A Hybrid Approach for XML Similarity”, The 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, pp. 783-795.

Semantic Similarity Retrieval Model (SSRM)

การหาความสำคัญของเอกสารจะดูที่น้ำหนักของคำที่สนใจ การหาน้ำหนักของคำจะใช้ทฤษฎี tf*idf และการหาค่าความคล้ายของสองเอกสารจะใช้ทฤษฎีของ Vector Space Model (VSM) คือ Cosine Similarity ที่จะได้ผลดีกว่าวิธี Inner Product
อย่างไรก็ตามในวิธีที่กล่าวมาข้างต้น จะสามารถค้นหาความคล้ายของเอกสารได้ก็ต่อเมื่อเอกสารนั้นใช้คำคำเดียวกัน
ในหลายๆเอกสารที่มีความคล้ายกัน แต่ใช้คำคนล่ะคำกัน VSM จะไม่สามารถหาความคล้ายกันของเอกสารได้ เช่น คำว่า car กับ automobile

Semantic Similarity Retrieval Model (SSRM) คือทฤษฎีที่จะหาความคล้ายกันของเอกสารที่ใช้คำคนล่ะคำกันโดยมีขั้นตอนดังนี้

1. Term Re-Weighting การหาน้ำหนักของคำใหม่ : น้ำหนักของคำ qi ของแต่ละการค้นหา i จะถูกปรับโดยดูความสัมพันธ์กับคำที่มีความหมายคล้ายกับคำ j ในเวคเตอร์เดียวกัน



โดยที่ t คือ threshold ที่ผู้ใช้กำหนดขึ้น (ในที่นี้ t = 0.8) สูตรนี้ใช้เฉพาะคำที่มีคำที่คล้ายกันกับคำที่ค้นหา เช่น railway, train, metro ส่วนคำที่ไม่คล้ายกัน ไม่มีการเปลี่ยนแปลง เช่น train, house

2. Term Expansion การขยายคำศัพท์ : ข้อแรก เลือกคำ synonym หลังจากนั้นเลือกคำใน hyponyms และ hypernyms ที่มีความคล้ายกับคำที่สนใจ รูปภาพแสดงถึง hypernyms และ hyponyms ของคำ



โดยที่แต่ล่ะคำจะค้นหาจาก WordNet tree ของคำคำนั้น คำที่มี threshold มากกว่า 0.9 จะถูกนำมาเพิ่มในการค้นหา คำที่นำมาเพิ่มอาจจะอยู่สูงกว่า หรือต่ำกว่ามากกว่า 1 ขั้นของคำคำนั้นก็ได้



โดยที่ n คือจำนวนของ hyponym ของแต่ละคำ j และสำหรับ hypernyms n มีค่า = 1
คำที่อยู่ในคำค้นหาอยู่แล้วอาจจะกลายเป็นคำใหม่สำหรับคำอื่น และคำหนึ่งคำ อาจจะถูกเพิ่มมากกว่าหนึ่งครั้งได้

3. Document Similarity การหาความคล้ายของเอกสาร : การหาความคล้ายของเอกสารใช้สูตรดังนี้



โดยที่ i และ j คือคำที่สนใจและคำในเอกสารตามลำดับ คำที่สนใจจะถูกคำนวนน้ำหนักใหม่ และถูกขยายคำ โดยที่คำในเอกสารจะไม่ต้องทำอะไรนอกจากหาน้ำหนักโดยใช้สูตร tf*idf เท่านั้น ผลการค้นหาจะมีค่าระหว่าง 0 กับ 1

ที่มา : G. Varelas, E. Voutsakis, P. Raftopoulou, E. Petrakis, E. Milios, “Semantic similarity methods in wordNet and their application to information retrieval on the web”, Proceedings of the 7th annual ACM international workshop on Web information and data management (WIDM’05), November 5, 2005 Bermen, Germany.

WordNet และ Ontology

WordNet คือฐานข้อมูลที่รวบรวมคำศัพท์ภาษาอังกฤษไว้ แต่ไม่ได้ใช้งานในรูปแบบ Dictionary อย่างเดียว คือไม่ได้สนใจแค่ว่าคำคำนี้แปลว่าอะไร แต่ WordNet จะเน้นไปที่ความสัมพันธ์ระหว่างคำศัพท์ โดยสามารถถือว่า WordNet เป็น Ontology อันหนึ่งที่รวบรวมคำศัพท์ไว้มากกว่า 100,000 คำ

WordNet ประกอบไปด้วยคำนาม (Nouns), คำกริยา (Verbs), คำคุณศัพท์ (Adjectives), และคำวิเศษณ์ (Adverbs) โดยคำที่มีความสัมพันธ์เกี่ยวข้องกันจะนำมาเกี่ยวโยงกันด้วย synonym sets (synsets) โดยข้อมูลใน synsets จะเกี่ยวโยงกันด้วย senses คำหนึ่งคำที่มีความหมายมากกว่าหนึ่งความหมาย จะมี senses มากกว่าหนึ่ง senses นอกจากนี้ WordNet ยังมีความสัมพันธ์ระหว่างคำนอกเหนือจาก synonym อีก 2 รูปแบบ คือ ความสัมพันธ์แบบ Is-A หรือเรียกว่า Hyponym และ Hypernym และความสัมพันธ์แบบ Part-Of หรือเรียกว่า Meronym และ Holonym

ตัวอย่างความสัมพันธ์แบบ Is-A
สุนัข เป็น Hypernym ของ ดัลเมเชี่ยน
ดัลเมเชี่ยน เป็น Hyponym ของสุนัข
ข้อสังเกตหรือวิธีทำความเข้าใจแบบง่ายๆ Hypernym มีรากศัพท์คือ Hyper แปลว่าเหนือ
เพราะฉะนั้น คำ ก. Hypernym ของคำ. ข แสดงว่าคำ ก. อยู่เหนือกว่าคำ ข. หรือคำ ก. มีความหมายกว้างๆ แต่คำ ข. มีความหมายแบบเฉพาะ

ตัวอย่างความสัมพันธ์แบบ Part-Of
ตึก เป็น holonym ของหน้าต่าง
หน้าต่างเป็น meronym ของตึก
ข้อสังเกตหรือวิธีทำความเข้าใจแบบง่ายๆ meronym คล้ายกับคำว่า member แปลว่าสมาชิก
เพราะฉะนั้น คำ ก. เป็น meronym ของ คำ ข. แสดงว่า คำ ก. เป็นสมาชิกหรือเป็นส่วนประกอบของคำ ข.

คำที่มีความหมายคล้ายกัน หรือ Semantic Similarity จะสนใจในส่วนของ synset และนอกจากนั้น ยังต้องเอา Hypernym และ Hyponym มาทำการวิจัยควบคู่ไปด้วย นอกจากนั้น การค้นหาคำที่มีความหมายคล้ายกันจะสนใจเฉพาะ Noun และ Verb เท่านั้น

การค้นหาคำที่มีความหมายคล้ายกัน สามารถแบ่งได้เป็น 4 วิธีใหญ่ๆได้แก่
1. Edge Counting Methods วัดคำศัพท์ 2 คำ โดยใช้ความยาวของ path ที่เชื่อมต่อแต่ละคำ และตำแหน่งของคำในกลุ่ม
2. Information Content Methods วัดความแตกต่างของเนื้อหาของสองคำ โดยใช้ความเป็นไปได้ที่จะเกิดขึ้นในเอกสาร
3. Feature Based Methods วัดความคล้ายกันของคำสองคำ โดยดูที่ properties ของคำ
4. Hybrid Methods รวมเอาวิธีทั้งหมดเข้าด้วยกัน

วิธีการหาความคล้ายของคำโดยส่วนมากจะค้นหาจาก Ontology ซึ่งสามารถแบ่งได้ 2 ประเภทคือ
1. Single Ontology คือ คำสองคำที่ต้องการหามาจาก Ontology เดียวกัน ใช้วิธี Edge Counting Methods และ Information Content Methods
2. Cross Ontology คือ คำสองคำที่ต้องการหามาจาก Ontology มากกว่าหนึ่ง Ontology ใช้วิธี Feature Based Methods และ Hybrid Methods

ที่มา : G. Varelas, E. Voutsakis, P. Raftopoulou, E. Petrakis, E. Milios, “Semantic similarity methods in wordNet and their application to information retrieval on the web”, Proceedings of the 7th annual ACM international workshop on Web information and data management (WIDM’05), November 5, 2005 Bermen, Germany.