เมล็ดต้นไม้: การหาปริมาณความคล้ายคลึงกันระหว่างข้อมูลที่มีโครงสร้างเป็นต้นไม้

เครือข่าย หรือ กราฟ เป็นข้อมูลที่มีโครงสร้างประเภทหนึ่งในรูปแบบของ โหนด โดยมีความสัมพันธ์อธิบายโดยลิงก์หรือ ขอบ โหนดและขอบในกราฟอาจมีคุณลักษณะหลายอย่างที่อาจเป็นตัวเลขหรือเชิงหมวดหมู่ หรือซับซ้อนกว่านั้น

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

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

การจำแนกประเภทข้อมูลที่มีโครงสร้างโดยไม่ได้รับการดูแล

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

การจำแนกประเภทแบบไม่มีผู้ดูแลสามารถใช้ร่วมกับทฤษฎีกราฟเพื่อระบุกลุ่มของเครือข่ายต้นไม้ที่คล้ายคลึงกัน โครงสร้างข้อมูลแบบทรีถูกใช้เพื่อสร้างแบบจำลองวัตถุจากหลายโดเมน ในการประมวลผลภาษาธรรมชาติ (NLP) ตัวอย่างเช่น ต้นไม้แยกวิเคราะห์ถูกจำลองตามคำสั่ง ต้นไม้ที่มีป้ายกำกับ ในการให้เหตุผลอัตโนมัติ ปัญหามากมายได้รับการแก้ไขโดยการค้นหา โดยที่พื้นที่การค้นหาจะแสดงเป็นต้นไม้ที่มีจุดยอดเชื่อมโยงกับสถานะการค้นหา และขอบแสดงขั้นตอนการอนุมาน นอกจากนี้ ข้อมูลกึ่งโครงสร้าง เช่น เอกสาร HTML และ XML สามารถสร้างแบบจำลองตามลำดับต้นไม้ที่มีป้ายกำกับ

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

คำสาปแห่งมิติ

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

นี่อาจเป็นข้อเสียเปรียบที่สำคัญ เนื่องจากเทคนิคการจำแนกประเภทจำนวนมากไม่สามารถปรับขนาดได้อย่างมีประสิทธิภาพด้วยมิติของอินพุต กล่าวอีกนัยหนึ่ง พลังการจัดหมวดหมู่จะลดลงเมื่อเพิ่มมิติของอินพุต ปัญหานี้เรียกว่าคำสาปแห่งมิติ

หากต้องการทราบสาเหตุของการเสื่อมประสิทธิภาพ ให้พิจารณาช่องว่าง X ของมิติ d สมมติว่า X มีชุดของจุดกระจายอย่างสม่ำเสมอ หากจำนวนมิติของ X เพิ่มขึ้น จำนวนจุดที่จำเป็นในการรักษาความหนาแน่นให้เท่ากันจะต้องเพิ่มขึ้นแบบทวีคูณ กล่าวอีกนัยหนึ่ง ยิ่งมิติข้อมูลของอินพุตมากเท่าใด ข้อมูลนั้นก็จะยิ่งกระจัดกระจายมากขึ้นเท่านั้น โดยทั่วไป ชุดข้อมูลที่เบาบางไม่ได้ให้ข้อมูลเพียงพอสำหรับการสร้างตัวแยกประเภทที่ดี เนื่องจากความสัมพันธ์ระหว่างองค์ประกอบข้อมูลนั้นอ่อนแอเกินกว่าที่อัลกอริทึมจะตรวจจับได้

พื้นที่คุณลักษณะแต่ละส่วนด้านบนมีจุดข้อมูลแปดจุด บนสเปซหนึ่งมิติ การระบุกลุ่มจุดห้าจุดทางด้านซ้ายและสามจุดทางขวาเป็นเรื่องง่าย การขยายจุดเหล่านี้เหนือจำนวนคุณลักษณะที่สูงขึ้น (เช่น มิติข้อมูล) ทำให้ยากต่อการค้นหากลุ่มเหล่านี้ ในการใช้งานจริง พื้นที่คุณลักษณะสามารถมีได้หลายร้อยมิติ

การแสดงเวกเตอร์สำหรับข้อมูลที่มีโครงสร้างเหมาะสมเมื่อข้อมูลเกี่ยวกับโดเมนสามารถใช้อย่างมีประสิทธิภาพเพื่อเลือกชุดคุณลักษณะที่สามารถจัดการได้ เมื่อไม่มีข้อมูลดังกล่าว ขอแนะนำให้ใช้เทคนิคที่สามารถจัดการข้อมูลที่มีโครงสร้างได้โดยตรง โดยไม่ต้องดำเนินการในพื้นที่เวกเตอร์

วิธีการเคอร์เนล

วิธีเคอร์เนลหลีกเลี่ยงความจำเป็นในการแปลงข้อมูลเป็นรูปแบบเวกเตอร์ ข้อมูลเดียวที่พวกเขาต้องการคือการวัดความคล้ายคลึงกันของแต่ละรายการในชุดข้อมูล การวัดนี้เรียกว่า เคอร์เนล และฟังก์ชันสำหรับกำหนดเรียกว่า ฟังก์ชันเคอร์เนล เมธอดของเคอร์เนลจะค้นหาความสัมพันธ์เชิงเส้นในพื้นที่คุณลักษณะ เทียบเท่ากับการใช้จุดข้อมูลสองจุดในพื้นที่คุณลักษณะ และการออกแบบคุณลักษณะอาจยังคงเป็นขั้นตอนที่มีประโยชน์ในการออกแบบฟังก์ชันเคอร์เนล อย่างไรก็ตาม เมธอดของเคอร์เนลจะหลีกเลี่ยงการทำงานโดยตรงบนพื้นที่ของฟีเจอร์ เนื่องจากสามารถแสดงให้เห็นได้ว่าสามารถแทนที่ dot product ด้วยฟังก์ชันเคอร์เนลได้ ตราบใดที่ฟังก์ชันเคอร์เนลเป็นฟังก์ชันกึ่งกำหนดผลบวกที่สมมาตรและสมมาตร ซึ่งสามารถใช้เป็นอินพุตข้อมูลได้ ในพื้นที่เดิม

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

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

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

วิธีการทำเหมืองข้อมูลหลายวิธีสามารถทำเคอร์เนลได้ ในการจำแนกอินสแตนซ์ข้อมูลที่มีโครงสร้างแบบทรีด้วยเมธอดเคอร์เนล เช่น ด้วยเครื่องเวกเตอร์ที่รองรับ ก็เพียงพอที่จะกำหนดฟังก์ชันเคอร์เนลที่ถูกต้อง (แน่นอนบวกสมมาตร) k : T × T → R หรือเรียกอีกอย่างว่า เคอร์เนลของต้นไม้ ในการออกแบบเมล็ดต้นไม้ที่มีประโยชน์ในทางปฏิบัติ หนึ่งจะต้องมีการคำนวณในเวลาพหุนามเหนือขนาดของต้นไม้ และสามารถตรวจจับกราฟไอโซมอร์ฟิคได้ เมล็ดต้นไม้ดังกล่าวเรียกว่าเมล็ดต้นไม้ที่ สมบูรณ์

เมล็ดต้นไม้

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

สตริงเคอร์เนล

อันดับแรก เราจะเริ่มต้นด้วยการแนะนำสั้น ๆ เกี่ยวกับเมล็ดสตริง ซึ่งจะช่วยให้เราสามารถแนะนำวิธีการเคอร์เนลอื่นที่ยึดตามการแปลงต้นไม้เป็นสตริง

มากำหนด num y (s) เป็นจำนวนครั้งของสตริงย่อย y ในสตริง s ด้วย | s | หมายถึงความยาวของสตริง เคอร์เนลสตริงที่เราจะอธิบายในที่นี้ถูกกำหนดเป็น:

สตริง K (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

โดยที่ F คือชุดของสตริงย่อยที่เกิดขึ้นทั้งใน S 1 และ S 2 และพารามิเตอร์ w s ทำหน้าที่เป็นพารามิเตอร์น้ำหนัก (เช่น เพื่อเน้นสตริงย่อยที่สำคัญ) ดังที่เราเห็น เคอร์เนลนี้ให้ค่าที่สูงกว่าแก่คู่ของสตริง เมื่อพวกเขาแบ่งปันสตริงย่อยทั่วไปจำนวนมาก

เคอร์เนลต้นไม้ขึ้นอยู่กับการแปลงต้นไม้เป็นสตริง

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

เราแปลงต้นไม้สองต้นเป็นสองสตริงดังนี้:

ให้ T หมายถึงหนึ่งในต้นไม้เป้าหมาย และติด ป้ายกำกับ (ns ) ป้ายสตริงของโหนด n s ใน T tag( ns ) หมายถึงการแสดงสตริงของทรีย่อยของ T ที่รูทที่ ns ดังนั้นหาก n root เป็นโหนดรูทของ T tag(n root ) คือการแสดงสตริงของทรีทั้งหมด T

ต่อไป ให้ string(T) = tag(n root ) แทนการแสดงสตริงของ T เราจะใช้ขั้นตอนต่อไปนี้ซ้ำๆ จากล่างขึ้นบนเพื่อรับ string(T) :

• หากโหนด ns เป็นลีฟ ให้ tag( ns ) = “[” + label( ns ) + “]” (โดยที่ + นี่คือตัวดำเนินการต่อสตริง)
• หากโหนด ns ไม่ใช่ leaf และมีลูก c n 1 , n 2 , … , nc , sort tag (n 1 ), tag(n 2 ), … , tag(nc ) ตามลำดับคำศัพท์เพื่อรับ แท็ก (n 1* ), tag(n 2* ), … , tag(n c* ) , และให้ tag( ns ) = “[” + label( ns ) + tag(n 1* ) + tag(n 2* ) + … + tag( nc* ) + “]” .

รูปด้านล่างแสดงตัวอย่างการแปลงแบบ tree-to-string ผลลัพธ์คือสตริงที่ขึ้นต้นด้วยตัวคั่นการเปิด เช่น "[" และลงท้ายด้วยคู่ปิด "]" โดยมีตัวคั่นคู่ที่ซ้อนกันซึ่งสอดคล้องกับทรีย่อยที่รูทที่โหนดใดโหนดหนึ่ง

ตอนนี้เราสามารถนำการแปลงข้างต้นไปใช้กับต้นไม้สองต้น T 1 และ T 2 เพื่อรับสองสตริง S 1 และ S 2 จากตรงนั้น เราก็สามารถใช้สตริงเคอร์เนลที่อธิบายข้างต้นได้

เคอร์เนลต้นไม้ระหว่าง T 1 และ T 2 ผ่านสองสตริง S 1 และ S 2 สามารถกำหนดได้ดังนี้:

K tree (T 1 , T 2 ) = K string ( string(T 1 ), string(T 2 ) ) = K string (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

ในการใช้งานส่วนใหญ่ พารามิเตอร์น้ำหนักจะกลายเป็น w | s | , การถ่วงน้ำหนักสตริงย่อยตามความยาว | s | . วิธีการชั่งน้ำหนักทั่วไปสำหรับ w | s | เป็น:

• การถ่วงน้ำหนักคงที่ ( w | s | = 1 )
• k -การถ่วงน้ำหนักสเปกตรัม ( w | s | = 1 ถ้า | s | = k และ w | s | = 0 อย่างอื่น)
• การถ่วงน้ำหนักแบบเอ็กซ์โปเนนเชียล ( w | s | = λ | s | โดยที่ 0 ≤ λ ≤ 1 คืออัตราการสลายตัว)

ในการคำนวณเคอร์เนล ก็เพียงพอที่จะกำหนดสตริงย่อยทั่วไปทั้งหมด F และนับจำนวนครั้งที่เกิดขึ้นใน S 1 และ S 2 ขั้นตอนเพิ่มเติมในการค้นหาสตริงย่อยทั่วไปนี้เป็นปัญหาที่มีการศึกษามาเป็นอย่างดี และสามารถทำได้ใน O( | S 1 | + | S 2 | ) โดยใช้แผนผังส่วนต่อท้ายหรืออาร์เรย์ต่อท้าย หากเราคิดว่าจำนวนตัวอักษรสูงสุด (เช่น บิต ไบต์ หรืออักขระ) ที่จำเป็นในการอธิบายป้ายกำกับของโหนดเป็นค่าคงที่ ความยาวของสตริงที่แปลงแล้วจะเป็น | S 1 | = O( | T 1 | ) และ | S 2 | = O( | T 2 | ) . ดังนั้นความซับซ้อนในการคำนวณของการคำนวณฟังก์ชันเคอร์เนลคือ O( | T 1 | + | T 2 | ) ซึ่งเป็นเส้นตรง

เคอร์เนลต้นไม้ตามเส้นทางย่อย

เคอร์เนลต้นไม้ด้านบนใช้วิธีแนวนอนหรือกว้างก่อนเพื่อแปลงต้นไม้เป็นสตริง แม้ว่าวิธีการนี้จะค่อนข้างง่าย แต่การแปลงนี้หมายความว่าไม่สามารถดำเนินการกับต้นไม้โดยตรงในรูปแบบดั้งเดิมได้

ส่วนนี้จะกำหนดเคอร์เนลของต้นไม้ที่ทำงานบนโครงสร้างแนวตั้งในต้นไม้ ซึ่งช่วยให้เคอร์เนลทำงานบนต้นไม้ได้โดยตรง

ส่วนย่อยของเส้นทางจากรูทไปยังใบไม้ใดใบไม้หนึ่งเรียกว่าเส้นทาง ย่อย และชุด เส้นทาง ย่อยคือชุดของเส้นทางย่อยทั้งหมดที่รวมอยู่ในแผนผัง:

สมมติว่าเราต้องการกำหนดเคอร์เนลต้นไม้ K(T 1 , T 2 ) ระหว่างต้นไม้สองต้น T 1 และ T 2 โดยใช้ชุดพาธย่อย เราสามารถกำหนดเคอร์เนลต้นไม้นี้เป็น:

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | พี |

โดยที่ num p (T) คือจำนวนครั้งที่พาธย่อย p เกิดขึ้นในทรี T , | พี | คือจำนวนโหนดในเส้นทางย่อย p และ P คือชุดของเส้นทางย่อยทั้งหมดใน T 1 และ T 2 w | พี | คือน้ำหนักที่คล้ายกับที่กล่าวไว้ในส่วนที่แล้ว

ในที่นี้ เราขอนำเสนอการใช้งานเคอร์เนลนี้อย่างง่ายโดยใช้การค้นหาเชิงลึกเป็นอันดับแรก แม้ว่าอัลกอริธึมนี้ทำงานในเวลากำลังสอง แต่มีอัลกอริธึมที่มีประสิทธิภาพมากขึ้นโดยใช้ทรีต่อท้ายหรืออาร์เรย์ต่อท้ายหรือส่วนขยายของอัลกอริธึม Quicksort แบบมัลติคีย์ซึ่งสามารถบรรลุเวลาเชิงเส้นตรง ( O( | T 1 | log | T 2 | ) ) โดยเฉลี่ย:

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

ในตัวอย่างนี้ เราใช้พารามิเตอร์การถ่วงน้ำหนัก w | s | w | พี | = 1 . สิ่งนี้ทำให้เส้นทางย่อยทั้งหมดมีน้ำหนักเท่ากัน อย่างไรก็ตาม มีหลายกรณีเมื่อใช้การถ่วงน้ำหนัก k -spectrum หรือค่าน้ำหนักที่กำหนดแบบไดนามิกบางอย่างมีความเหมาะสม

เว็บไซต์การขุด

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

เราจะทำอย่างนั้นได้อย่างไร? เอกสาร HTML มีโครงสร้างที่ซ้อนกันแบบลอจิคัล ซึ่งคล้ายกับต้นไม้มาก เอกสารแต่ละฉบับมีองค์ประกอบหลักหนึ่งรายการ โดยมีองค์ประกอบเพิ่มเติมซ้อนอยู่ภายใน องค์ประกอบที่ซ้อนกันในแท็ก HTML นั้นเทียบเท่ากับโหนดย่อยของแท็กนั้นตามตรรกะ:

มาดูโค้ดบางส่วนที่สามารถแปลงเอกสาร HTML เป็นแผนผังได้:

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

สิ่งนี้จะสร้างโครงสร้างข้อมูลแบบทรีที่อาจมีลักษณะดังนี้:

การใช้งานข้างต้นใช้ประโยชน์จากไลบรารี Python ที่มีประโยชน์สองสามอย่าง: NetworkX สำหรับการทำงานกับโครงสร้างกราฟที่ซับซ้อน และ Beautiful Soup สำหรับการดึงข้อมูลจากเว็บและจัดการเอกสาร

การเรียก html_to_dom_tree(soup.find("body")) จะส่งคืนวัตถุกราฟ NetworkX ที่รูทที่องค์ประกอบ <body> ของหน้าเว็บ

สมมติว่าเราต้องการหากลุ่มต่างๆ ในชุดโฮมเพจของเว็บไซต์ 1,000 หน้า โดยการแปลงหน้าแรกแต่ละหน้าเป็นแผนผังแบบนี้ เราสามารถเปรียบเทียบแต่ละรายการได้ ตัวอย่างเช่น โดยใช้เคอร์เนลของทรีย่อยของพาธที่ให้ไว้ในส่วนก่อนหน้า ด้วยการวัดความคล้ายคลึงกันเหล่านี้ เราอาจพบว่าตัวอย่างเช่น ไซต์อีคอมเมิร์ซ ไซต์ข่าว บล็อก และไซต์เพื่อการศึกษา สามารถระบุความคล้ายคลึงกันได้อย่างง่ายดาย

บทสรุป

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

โครงสร้างแบบต้นไม้พบได้ในพื้นที่คำจริงมากมาย เช่น เอกสาร XML และ HTML สารประกอบทางเคมี การประมวลผลภาษาธรรมชาติ หรือพฤติกรรมผู้ใช้บางประเภท ดังที่แสดงในตัวอย่างการสร้างต้นไม้จาก HTML เทคนิคเหล่านี้ช่วยให้เราทำการวิเคราะห์ที่มีความหมายในโดเมนเหล่านี้