Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

เทคนิคการขุดรูปแบบเชิงลบมีอะไรบ้าง?


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

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

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

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

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

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

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

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

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