อะไรคือตัวแทนของ FP-Tree?

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

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

แต่ละโหนดในแผนผังจะมีป้ายกำกับของรายการพร้อมกับตัวนับที่แสดงธุรกรรมหลายรายการที่แมปบนเส้นทางที่กำหนด เดิมที FP-tree รวมเฉพาะโหนดรูทที่กำหนดโดยสัญลักษณ์ nulf

FP-tree ยังคงดำเนินต่อไปในวิธีการดังต่อไปนี้ −

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

อัลกอริทึมจะสร้างการส่งผ่านข้อมูลครั้งที่สองเพื่อสร้างแผนผัง FP หลังจากตรวจสอบธุรกรรมแรก {a, b} โหนดที่มีป้ายกำกับว่า a และ b จะถูกสร้างขึ้น เส้นทางถูกสร้างขึ้นจาก null→a→b เพื่อเข้ารหัสธุรกรรม แต่ละโหนดตามเส้นทางมีการนับความถี่ 1

หลังจากตรวจสอบธุรกรรมที่สอง {b, c, d} แล้ว ชุดโหนดใหม่จะถูกสร้างขึ้นสำหรับรายการ b, c และ d เส้นทางจะถูกสร้างขึ้นเพื่อกำหนดธุรกรรมโดยการเชื่อมโยงโหนด null→b→c→d

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

ธุรกรรมที่สาม {a, c, d, e} แบ่งปันรายการนำหน้าที่ใช้บ่อย (ซึ่งก็คือ a) กับธุรกรรมแรก ดังนั้น เส้นทางสำหรับธุรกรรมที่สาม null→a→ c →d→e ทับซ้อนกับเส้นทางสำหรับธุรกรรมแรก nuII→a→b เนื่องจากเส้นทางที่ทับซ้อนกัน การนับความถี่สำหรับโหนด o เพิ่มขึ้นเป็นสอง ในขณะที่การนับความถี่สำหรับโหนดที่เพิ่งสร้าง c, d และ e จะเหมือนกันหนึ่ง

เฟสนี้จะดำเนินต่อไปจนกว่าแต่ละธุรกรรมจะได้รับการแมปบนเส้นทางใดเส้นทางหนึ่งที่ระบุในแผนผัง FP ขนาดของ FP-tree นั้นเล็กกว่าขนาดของข้อมูลที่ไม่ถูกบีบอัด เนื่องจากธุรกรรมหลายรายการในข้อมูลตะกร้าของตลาดมีรายการร่วมกันมากกว่า