เราจะค้นพบโครงสร้างพื้นฐานบ่อยครั้งได้อย่างไร

การค้นพบโครงสร้างย่อยบ่อยครั้งมักประกอบด้วยสองขั้นตอน ในขั้นตอนแรก สามารถสร้างผู้สมัครโครงสร้างพื้นฐานได้บ่อยครั้ง ความถี่ของผู้สมัครทุกคนจะได้รับการทดสอบในขั้นตอนที่สอง การศึกษาส่วนใหญ่เกี่ยวกับการค้นพบโครงสร้างย่อยบ่อยครั้งมุ่งเน้นไปที่การปรับให้เหมาะสมของขั้นตอนแรก เนื่องจากขั้นตอนที่ 2 เกี่ยวข้องกับการทดสอบ subgraph isomorphism ซึ่งความซับซ้อนในการคำนวณสูงเกินไป (เช่น NP-complete)

มีวิธีการต่างๆ สำหรับการขุดโครงสร้างพื้นฐานบ่อย ๆ ซึ่งมีดังนี้ -

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

ความซับซ้อนในการออกแบบหลักของอัลกอริธึมการขุดโครงสร้างพื้นฐานแบบ Apriori คือขั้นตอนการสร้างตัวเลือก การผลิตของผู้สมัครในการขุด itemset บ่อยครั้งนั้นเป็นความจริง ตัวอย่างเช่น สมมติว่าเรามีชุดรายการที่ใช้บ่อยสองชุดคือ size-3:(abc) และ (bcd)

ตัวเลือก itemset ที่พบบ่อยของ size-4 ที่สร้างขึ้นจากพวกเขานั้นง่าย (abcd) เปลี่ยนจากการเข้าร่วม อย่างไรก็ตาม ปัญหาการสร้างตัวเลือกในการขุดโครงสร้างย่อยบ่อยครั้งนั้นยากกว่าการขุดแบบชุดไอเท็มบ่อยครั้ง เนื่องจากมีหลายวิธีในการรวมโครงสร้างย่อยสองโครงสร้าง

แนวทางรูปแบบ-การเติบโต − วิธีการตาม Apriori ต้องใช้กลยุทธ์การค้นหาแบบกว้างก่อน (BFS) เนื่องจากการสร้างผู้สมัครที่ฉลาดในระดับ ในการพิจารณาว่ากราฟ size-(k + 1) มีความถี่หรือไม่ จะต้องตรวจสอบกราฟย่อย size-k ที่เกี่ยวข้องทั้งหมดเพื่อให้ได้ขอบเขตบนของความถี่ ดังนั้น ก่อนการขุดกราฟย่อยขนาด-(k +1) ใดๆ วิธีการแบบ Apriori มักจะต้องทำการขุดกราฟย่อย size-k ให้เสร็จสิ้น

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

Pattern Growth Graph นั้นเรียบง่ายแต่ไม่ได้ผล คอขวดอยู่ที่ความไร้ประสิทธิภาพของการขยายกราฟ กราฟเดียวกันสามารถพบได้หลายครั้ง ตัวอย่างเช่น อาจมีกราฟขอบ (n -1) ที่แตกต่างกัน n กราฟที่สามารถขยายไปยังกราฟ n-edge เดียวกันได้ การค้นพบกราฟเดียวกันซ้ำแล้วซ้ำอีกนั้นไม่มีประสิทธิภาพในการคำนวณ เราเรียกกราฟที่ถูกค้นพบเป็นครั้งที่สองว่ากราฟที่ซ้ำกัน

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