การแทนข้อมูลของ FP-Tree (FP-Tree Representation) คืออะไร

FP-tree เป็นการแทนข้อมูลที่แน่นหนา (Compact Representation) ของข้อมูลป้อนเข้า มันถูกสร้างขึ้นโดยการอ่านชุดข้อมูลทีละธุรกรรม (Transaction) และวัดแต่ละธุรกรรมบนเส้นทาง (Path) ใน FP-tree ธุรกรรมหลายๆ อาจมีรายการ (Items) ร่วมกันหลายอย่าง เส้นทางของพวกเขาจึงอาจทับซ้อนกัน (Overlap)

ยิ่งเส้นทางทับซ้อนกันมากเท่าไหร่ ยิ่งการบีบอัด (Compression) สามารถนำไปใช้ได้มากเท่านั้นโดยใช้สถาปัตยกรรม FP-tree หากขนาดของ FP-tree เพียงพอที่จะใส่ในหน่วยความจำหลัก (Main Memory) นี่จะช่วยให้เราสามารถแยก itemsets ที่พบบ่อย (Frequent Itemsets) ได้โดยตรงจากสถาปัตยกรรมในหน่วยความจำ แทนที่จะต้องสร้างการผ่านซ้ำ (Repeated Passes) ผ่านข้อมูลที่จัดเก็บบนดิสก์

แต่ละโหนดในต้นไม้รวมถึงฉลากของรายการพร้อมกับตัวนับ (Counter) ที่แสดงจำนวนธุรกรรมที่แมปบนเส้นทางที่กำหนด เริ่มต้น FP-tree มีเพียงโหนดราก (Root Node) ที่แทนด้วยสัญลักษณ์ null

FP-tree ถูกสร้างต่อไปในวิธีต่อไปนี้:

ชุดข้อมูลถูกค้นหาหนึ่งครั้งเพื่อตัดสินใจจำนวนการสนับสนุน (Support Count) ของแต่ละรายการ รายการที่พบน้อย (Infrequent Items) ถูกลบออก ในขณะที่รายการที่พบบ่อย (Frequent Items) ถูกจัดเรียงในจำนวนการสนับสนุนที่ลดลง (Decreasing Support Counts)

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

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

โหนดแต่ละตัวตามเส้นทางนี้ก็มีจำนวนความถี่เท่ากับหนึ่งเช่นกัน แม้ธุรกรรมสองอันแรกจะมีรายการร่วมกันคือ b แต่เส้นทางของพวกเขาเป็น disjoint (ไม่ต่อเนื่อง) เพราะธุรกรรมไม่มีคำนำหน้าที่พบบ่อยร่วมกัน (Common Prefix)

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

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