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.