ROCK คืออะไร?

ความหมายของ ROCK

ROCK ย่อมาจาก Robust Clustering using links (การจัดกลุ่มที่ทนทานโดยใช้ลิงก์) เป็นอัลกอริทึมการจัดกลุ่มแบบลำดับชั้น (hierarchical clustering algorithm) ที่วิเคราะห์แนวคิดของ links (จำนวนเพื่อนบ้านร่วมระหว่างสองวัตถุ) สำหรับข้อมูลที่มีแอตทริบิวต์เชิงหมวดหมู่ (categorical attributes) มันแสดงให้เห็นว่าข้อมูลระยะทาง (distance data) แบบนั้นไม่สามารถนำไปสู่คลัสเตอร์คุณภาพสูงได้เมื่อจัดกลุ่มข้อมูลเชิงหมวดหมู่

นอกจากนี้ อัลกอริทึมการจัดกลุ่มส่วนใหญ่สร้างเฉพาะความคล้ายคลึง (similarity) ระหว่างจุดเมื่อจัดกลุ่ม คือ ที่แต่ละขั้นตอน จุดที่รวมเข้าด้วยกันเป็นคลัสเตอร์เดียว วิธี "เฉพาะที่" (localized) นี้ทำให้เกิดข้อผิดพลาด (prone to bugs) ได้ง่าย ตัวอย่างเช่น สองคลัสเตอร์ที่แตกต่างกันอาจมีจุดบางจุดหรือ outliers ที่อยู่ใกล้กัน ดังนั้น การพึ่งพาความคล้ายคลึงระหว่างจุดเพื่อตัดสินใจการจัดกลุ่มอาจทำให้สองคลัสเตอร์ถูกรวมกัน

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

นิยามเพื่อนบ้านและลิงก์

มีสองจุด p_i และ p_j เป็นเพื่อนบ้าน (neighbors) หาก sim(p_i, p_j) ≥ θ โดยที่ sim เป็นฟังก์ชันความคล้ายคลึง (similarity function) และ θ เป็นเกณฑ์ที่ผู้ใช้ระบุ (user-specified threshold) สามารถเลือก sim เป็น distance metric หรือแม้แต่มาตรฐานที่ไม่ใช่ metric ที่ปรับให้ค่าตกอยู่ระหว่าง 0 และ 1 โดยค่าที่สูงกว่าแสดงว่าจุดเหล่านั้นคล้ายกันมากขึ้น

จำนวนการเชื่อมต่อ (links) ระหว่าง p_i และ p_j แทนเป็นจำนวนเพื่อนบ้านร่วม (common neighbors) ระหว่าง p_i และ p_j หากจำนวนลิงก์ระหว่างสองจุดสูง แสดงว่าพวกเขาน่าจะเป็นของคลัสเตอร์เดียวกัน ด้วยการพิจารณาจุดข้อมูลเพื่อนบ้านในความสัมพันธ์ระหว่างกลุ่มจุดเดี่ยว ROCK มีพลังมากกว่าวิธีการจัดกลุ่มมาตรฐานที่มุ่งเน้นเฉพาะความคล้ายคลึงของจุด

ตัวอย่างข้อมูล Market Basket

ตัวอย่างของข้อมูลที่มีแอตทริบิวต์เชิงหมวดหมู่คือข้อมูลตะกร้าสินค้า (market basket data) ข้อมูลเช่นนี้ประกอบด้วยฐานข้อมูลธุรกรรม โดยแต่ละธุรกรรมเป็นกลุ่มของไอเทม ธุรกรรมถูกมองเป็นข้อมูลกับแอตทริบิวต์บูลีน (Boolean attributes) แต่ละตัวสอดคล้องกับไอเทมเดี่ยว เช่น ขนมปัง (bread) หรือ ชีส (cheese)

ในข้อมูลสำหรับธุรกรรม แอตทริบิวต์ที่สอดคล้องกับไอเทมจะเป็นจริง (true) หากธุรกรรมรวมไอเทมนั้น มิฉะนั้นจะเป็นเท็จ (false) มีชุดข้อมูลหลายชุดที่มีแอตทริบิวต์เชิงหมวดหมู่สามารถจัดการได้ในลักษณะเดียวกัน คำศัพท์ของ ROCK เกี่ยวกับเพื่อนบ้านและลิงก์เหมือนกันระหว่างสอง "จุด" หรือธุรกรรม T_i และ T_j แทนด้วย Jaccard coefficient ดังนี้:

$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$$

ROCK สร้างกราฟเบาบาง (sparse graph) จากเมทริกซ์ความคล้ายคลึงของข้อมูลที่กำหนดโดยใช้เกณฑ์ความคล้ายคลึง และแนวทางเพื่อนบ้านร่วม มันดำเนินการ agglomerative hierarchical clustering บนกราฟเบาบาง ขนาดวัด goodness measure สามารถคำนวณการจัดกลุ่มได้ การสุ่มตัวอย่าง (Random sampling) สามารถใช้สำหรับการขยายขนาด (scaling up) ไปยังชุดข้อมูลขนาดใหญ่

เวลาสูงสุดในกรณีแย่ที่สุด (worst-case time complexity) ของ ROCK คือ O(n² + nm_mm_a + n²log_n) โดยที่ m_m และ m_a คือ จำนวนเพื่อนบ้านสูงสุดและเฉลี่ย ตามลำดับ และ n คือจำนวนวัตถุ