XML Path Matching

Path ระหว่าง root ไปถึง node ของ XML มีความสำคัญ เช่น
1. /conferences/conference/paper/authorname
2. /conferences/conference/submission/author/name
3. /universities/university/department/name
จากตัวอย่าง แสดงให้เห็นว่า เอกสาร 1 และ 2 น่าจะมีความเหมือนกัน โดยที่เอกสาร 3 ไม่น่ามีความเกี่ยวข้องกัน หรือเกี่ยวข้องกันน้อยมาก

XML Path ใช้ใน data integration, data querying, and data cleaning ซึ่งเป็นหัวข้อสำคัญ

Path Similarity ควรเพียงพอสำหรับในการอธิบายความหมายเช่น
- hire/date กับ birth/date ซึ่งคนละความหมายกัน
- คำที่มีความหมายเหมือนกัน หรือพิมพ์ผิด

การเปรียบเทียบโครงสร้างของ XML มีหลายการค้นคว้า โดยแบ่งออกเป็น similarity based on the tree edit distance และ combining the similarity values measured among their child elements. ทั้งสองวิธีเปรียบเทียบ element ไม่ใช่ path
COMA เป็น framework ที่ทำ schema matchers ซึ่งเรียกว่า NamePath (Path Similarity function) NamePath แปลง element ทุกตัวไปในรูป string และนำ string ไปเทียบหาความเหมือน

PathSim คือ similarity algorithm โดยแปลง XML part เป็น list ของ element names และใช้ edit distance มาเปรียบเทียบ list โดยมองว่า แต่ละ path คือ string แต่ไม่ได้เปรียบเทียบที่ละตัวตามลำดับอักษร แต่มองว่าแต่ละ path แสดงถึง list ของ element
PathSim คำนวนความคล้ายกันของสอง path โดยใช้ edit distance ระหว่าง list ของ element
PathSim ใช้ Matrix ในการคำนวนหาค่าความคล้ายกันของ 2 path โดยมีขั้นตอนดังนี้
1. สร้าง Matrix ที่มีแถว I + 1 และมีคอลัมภ์ j + 1
2. เติมค่าในแถวแรกและคอลัมภ์แรกด้วย
a. แถวแรก M[0,q] = q สำหรับ 0 <= q <= j
b. คอลัมภ์แรก M[p,0] = p สำหรับ 1 <= p <= i
3. เติมค่าที่เหลือโดยเลือกค่าที่น้อยที่สุดจาก
a. ค่าของ cell ข้างบน + 1
b. ค่าของ cell ทางซ้าย + 1
c. ค่าของ cell ทางซ้ายบน + ค่าความไม่เหมือนกันของ A[p] กับ B[q]
(M[p-1,q-1] + (1 – Sim(A[p],B[q]))
ตัวอย่าง
จาก 2 path A=”Author/Names” และ B=”Author/Name/First” สร้าง Matrix 2*3 และเติมค่าในแถวและคอลัมภ์แรกดังรูปที่ 1 หลังจากนั้นเติมค่าในช่องที่เหลือ




ค่า M[2,1] (Names,Author) คำนวนโดยใช้
ทางเลือกที่ 1 คือ Cell ข้างบน + 1 ได้ค่า 1
ทางเลือกที่ 2 คือ Cell ซ้าย + 1 ได้ 3
ทางเลือกที่ 3 คือ Cell บนซ้าย + ความไม่เหมือนกัน ได้ 1 + (1+1) = 3
เพราะฉะนั้นเลือกทางเลือกที่ 1 ซึ่งหมายความได้ว่า มีการเพิ่มค่า element ใน path A หรือเอาค่า element ออกจาก path B

ค่า M[2,2] ทางเลือกที่ 1 และ 2 ได้ค่า 2 ทั้งคู่
ทางเลือกที่ 3 เอาค่า 0 + ค่าความไม่เหมือน (1 – ค่าความเหมือน) ในที่นี่คือ 1 – 0.8 ได้ 0.2
เพราะฉะนั้น M[2,2] = 0.2
ค่าความเหมือนของ Name และ Names คือ 0.8 เพราะฉะนั้นค่าความไม่เหมือน คือ 0.2

ค่า M[2,3] คำนวนโดยใช้ทางเลือกที่ 2 หมายความได้ว่า มีการเพิ่ม element ใน path B หรือเอา element ออกจาก path A

การคำนวนค่าความเหมือนของ สอง path ใช้สูตร

PathSim(A,B) = 1 – M[I,j]/Max(I,j)

จากตัวอย่างค่า edit distance สูงสุดคือ 1.2 ใน cell M[2,3] ดังนั้นค่าความเหมือนคือ
PathSim (A,B) = 1 – 1.2/3 = 0.6

Ref : A.R. Vinson, C.A. Heuser, A.S. da Silva, E.S. De Moura, “An Approach to XML Path Matching”, 9th Annual ACM International Workshop on Web Information and Data Management, Lisbon, Portugal, 2007, pp. 17-24.

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.

การเดินทางไปถึงอเมริกาครั้งแรกนับจากเรียนจบ

ประเทศอเมริกา เป็นประเทศที่มีพื้นที่ขนาดใหญ่มาก ประกอบไปด้วยรัฐต่างๆถึง 50 รัฐ
48 รัฐที่มีพื้นที่ติดกัน และมีอีก 2 รัฐที่ไม่มีพื้นที่ติดกับรัฐอื่นๆเลยคือ ฮาวาย และ อลาสก้า

ผมได้มีโอกาสไปใช้ชีวิตที่อเมริกามาประมาณ 2 ปีครึ่ง ช่วงนั้นไปเรียนต่อปริญญาโท และได้ท่องเที่ยวไปหลายสถานที่มากๆ
และหลังจากเรียนจบ กลับมาเมืองไทย ก็ได้มีโอกาสกลับไปอเมริกาอีก 2 ครั้งคือปี 2008 และปี 2009
โดยปี 2008 ไปทางด้านชายฝั่งตะวันตก โดยได้ไปเพียงแค่ 5 เมืองสำคัญเท่านั้นเองคือ
- Sacramento
- San Francisco
- Las Vegas
- San Diego
- Los Angeles

ส่วนปี 2009 ได้ไปช่วงกลางประเทศ เดินทางทั้งหมด 12 รัฐ เอาไว้จะเล่าคราวหน้าละกัน

ปี 2008 การเดินทางเริ่มต้นโดยบินไปกับสายการบิน All Nippon Airways
ทีเลือกสายการบินนี้มีหลายเหตุผล
1. สามารถเก็บไมล์กับการบินไทยได้
2. เวลาบินสะดวกสบายกว่าบินการบินไทย
3. เป็นสายการบินของญี่ปุ่น เครื่องบินน่าจะดีกว่าสายการบินของอเมริกาคือ United Airlines

การเดินทางเริ่มต้นออกจากประเทศไทยเวลาเช้าตรู่ ประมาณ 8.15 น. แต่ต้องไปถึงสนามบินก่อน 6.15 น.
การบินครั้งนี้ต้องไปเปลี่ยนเึครื่องที่ ญี่ปุ่น และบินตรงไป San Francisco เลย
ช่วงแรกใช้เวลาบินประมาณ 6 ชั่วโมง จะถึงญี่ปุ่น และมีเวลาเปลี่ยนเครื่องประมาณ 1 ชั่วโมงเพื่อต่อเครื่องไป San Francisco
ช่วงที่สองจากญี่ปุ่นไปอเมริกาใช้เวลาประมาณ 9 ชั่วโมง

การเดินทางถือว่าสะดวกสบายอย่างที่คิด เครื่องที่ใช้บินใหม่มาก แอร์โฮสเตสบริการดีตามฉบับสาวญี่ปุ่น
อาหารอร่อยใช้ได้ ความบันเทิงบนเครื่องมีจอส่วนตัวทุกที่นั่ง สามารถเลือกหนังที่อยากดูได้ตามอัธยาศัย
เมื่อเดินทางไปถึงญี่ปุ่น ความซวยเรื่องมาเยือน เพราะไปถึงช้าประมาณ 15 นาที
และต้องไปเสียเวลามากๆในการตรวจสัมภาระก่อนเข้าอาคารผู้โดยสาร เพื่อไปเปลี่ยนเครื่อง
ตรงนี้ผมไม่เข้าใจจริงๆ เพราะผู้โดยสารพึ่งลงมาจากเครื่องบินลำนึง และจะไปต่ออีกลำ ทำไมต้องตรวจละเอียดแถมวุ่นวายมากๆ
กว่าจะผ่านขั้นตอนทุกอย่าง เล่นเอาต้องวิ่งไปขึ้นเครื่องอีกลำทันที แทบไม่มีเวลาพักเลย ก็ยังดีที่ยังขึ้นเครื่องทัน
หลังจากนั้นก็เดินทางอีก 9 ชั่วโมงกว่าๆก็ถึงประเทศอเมริกา

ตอนเข้าประเทศ เจ้าหน้าที่ตรวจคนเข้าเมืองไม่ได้สอบถามอะไรมาก
ถามว่ามาทำไม มากี่วัน รู้จักใครบ้างไหม ก็ปล่อยให้เข้าประเทศไป
ตรงข้อรู้จักใครบ้างไหม ผมบอกเจ้าหน้าที่ว่าเป็นนักเรียนเก่า เพื่อจะได้สะดวกในการเข้า
เค้าเลยถามว่ามีเพื่อนอยู่บ้างไหม ผมบอกไปว่า เพื่อนเรียนจบ กลับประเทศไทยกันหมดแล้ว ไม่เหลือใครเลย
พอผ่านตรวจคนเข้าเมือง รับกระเป๋า และผ่านศุลกากรเรียบร้อย ก็เป็นอันหมดห่วง ไม่โดนกักตัวแน่นอน

หลังจากนั้นก็ไปรับรถเช่าที่ได้จองไว้ และขับรถไปเมือง Sacramento ก่อนเลย
การขับรถช่วงแรกจะงงนิดหน่อย เพราะรถที่นี่พวงมาลัยซ้าย
แต่โชคดีที่ผมเคยอาศัยอยู่ที่นี่มาก่อน เลยไม่มีปัญหามาก ใช้เวลาปรับตัวไม่เกินครึ่งชั่วโมงก็ขับได้โดยไม่มีปัญหา

รายละเอียดการเที่ยวเมืองต่างๆ เดี๋ยวจะมาเล่าครั้งหน้า
ส่วนรูปภาพ ผมได้อัพไว้ที่ Hi5 http://kob-11.hi5.com ลองไปแวะชมกันได้ครับ