การนับการสนับสนุน (Support Counting) เป็นกระบวนการตัดสินใจความถี่ของการปรากฏ (Frequency of Occurrence) สำหรับแต่ละ candidate itemset ที่รอดชีวิตจากขั้นตอนการตัดแต่ง candidate (Candidate Pruning Step) ของฟังก์ชัน apriori-gen
วิธีหนึ่งสำหรับทำสิ่งนี้คือการเปรียบเทียบแต่ละธุรกรรมกับแต่ละ candidate itemset และรีเฟรชจำนวนการสนับสนุนของ candidate ที่รวมอยู่ในธุรกรรม วิธีนี้มีค่าใช้จ่ายทางการคำนวณสูง โดยเฉพาะเมื่อจำนวนธุรกรรมและ candidate itemsets สูง
แนวทางที่สองคือการนับรายการ (Enumerate) itemsets ที่รวมอยู่ในแต่ละธุรกรรม และใช้พวกเขาเพื่อรีเฟรชจำนวนการสนับสนุนของ candidate itemsets เฉพาะของพวกเขา พิจารณาธุรกรรม t ที่รวมถึงห้ารายการ {1, 2, 3, 5, และ 6} มี (5 3) = 10 itemsets ขนาด 3 ที่รวมอยู่ในธุรกรรมนี้
Itemsets ต่างๆ อาจสอดคล้องกับ candidate 3-itemsets ที่อยู่ภายใต้การวิเคราะห์ ในกรณีนั้น จำนวนการสนับสนุนของพวกเขาจะเพิ่มขึ้น มีเซตย่อยต่างๆ ของ t ที่ไม่สอดคล้องกับ candidate ใดๆ ที่สามารถเพิกเฉยได้
แนวทางเป็นระบบ (Systematic Approach) สำหรับการนับ 3-itemsets ที่รวมอยู่ใน t โดยพิจารณาว่าแต่ละ itemset รักษารายการของมันในลำดับ lexicographic ที่เพิ่มขึ้น (Increasing Lexicographic Order) itemset สามารถนับได้โดยการกำหนดรายการเล็กที่สุดก่อน ตามด้วยรายการที่ใหญ่กว่า
ตัวอย่างเช่น กำหนด t: {1, 2, 3, 5, และ 6} 3-itemsets ทั้งหมดที่รวมอยู่ใน t ควรเริ่มต้นด้วยรายการ 1, 2, หรือ 3 ไม่สามารถนำไปใช้เพื่อสร้าง 3-itemset ที่เริ่มต้นด้วยรายการ 5 หรือ 6 เพราะมีสองรายการใน t ที่ฉลากของพวกเขาใหญ่กว่าหรือเท่ากับ 5
โครงสร้างคำนำหน้า (Prefix Structure) แสดงว่า itemsets ที่รวมอยู่ในธุรกรรมสามารถนับได้อย่างสม่ำเสมอ คือ โดยการกำหนดรายการของพวกเขาทีละรายการ จากรายการซ้ายสุดไปยังรายการขวาสุด
สามารถกำหนดได้ว่าแต่ละ 3-itemsets ที่นับได้สอดคล้องกับ candidate itemset ที่มีอยู่หรือไม่ หากมันเชื่อมต่อกับหนึ่งใน candidates ดังนั้น จำนวนการสนับสนุนของ candidate ที่สอดคล้องจะเพิ่มขึ้น
ในอัลกอริทึม Apriori candidate itemsets ถูกแบ่งเป็นหลายถัง (Buckets) และจัดเก็บใน hash tree ระหว่างการนับการสนับสนุน itemsets ที่รวมอยู่ในแต่ละธุรกรรมก็ถูกแฮช (Hashed) เข้าไปในถังที่เหมาะสมของพวกเขา แทนที่จะเปรียบเทียบแต่ละ itemset ในธุรกรรมกับแต่ละ candidate itemset มันเชื่อมต่อเฉพาะกับ candidate itemsets ที่เป็นของถังเดียวกัน
โหนดภายในแต่ละตัวของต้นไม้ต้องการฟังก์ชันแฮชต่อไปนี้ h(p): p mod 3 เพื่อตัดสินใจว่าสาขาไหนของโหนดปัจจุบันต้องทำตามต่อไป ตัวอย่างเช่น รายการ 1, 4, และ 7 ถูกแฮชไปยังสาขาเดียวกัน (คือสาขาซ้ายสุด) เพราะพวกเขามีเศษเหมือนกันหลังจากหารตัวเลขด้วย 3 Candidate itemsets ทั้งหมดถูกจัดเก็บที่โหนดใบ (Leaf Nodes) ของ hash tree
ทำความเข้าใจ Support Counting ใน Apriori: 2 Approaches (Transaction vs Candidate vs Enumeration), Prefix Structure สำหรับ Systematic Enumeration, Hash Tree ด้วย h(p)=p mod 3, Bucket-based Matching เพื่อประสิทธิภาพ
