ความหมายของ PROCLUS
PROCLUS ย่อมาจาก Projected Clustering (การจัดกลุ่มเชิงฉาย) เป็นเทคนิค subspace clustering แบบลดมิติ (dimension-reduction) ตามปกติ นั่นคือ แทนที่จะเริ่มจากพื้นที่มิติเดี่ยว (single-dimensional spaces) มันเริ่มต้นด้วยการหาประมาณการเริ่มต้น (initial approximation) ของคลัสเตอร์ในพื้นที่แอตทริบิวต์มิติสูง (high-dimensional attribute space)
แต่ละมิติถูกสร้างน้ำหนัก (weight) สำหรับแต่ละคลัสเตอร์ และน้ำหนักที่รีเฟรช (refreshed weights) ถูกใช้ในรอบถัดไป (next iteration) เพื่อสร้างคลัสเตอร์ใหม่ (recreate the clusters) นี่นำไปสู่การสำรวจพื้นที่หนาแน่น (dense regions) ในทุก subspace ของมิติที่สะดวก (convenient dimensionality) และป้องกันการสร้างคลัสเตอร์ที่ทับซ้อน (overlapped clusters) จำนวนมากในมิติที่ฉาย (projected dimensions) ของมิติต่ำกว่า
อัลกอริทึม PROCLUS
PROCLUS ค้นพบชุด medoids ที่ดีที่สุดโดย phase การปีนเขา (hill-climbing phase) คล้ายกับที่ใช้ใน CLARANS แต่ปรับเปลี่ยน (generalized) เพื่อจัดการกับ projected clustering มันใช้ distance measure (ขนาดวัดระยะทาง) ที่เรียกว่า Manhattan segmental distance ซึ่งคือ Manhattan distance บนชุดมิติที่เหมาะสม (appropriate dimensions)
อัลกอริทึม PROCLUS ประกอบด้วยสามกระบวนการ (phases) ได้แก่: initialization (การเริ่มต้น), iteration (การวนซ้ำ), และ cluster refinement (การปรับปรุงคลัสเตอร์)
1. Initialization Phase (ขั้นตอนเริ่มต้น)
ในขั้นตอน initialization ต้องการ greedy algorithm เพื่อเลือกชุด medoids เริ่มต้นที่อยู่ห่างจากกันพอสมควร (far apart from each other) เพื่อให้แน่ใจว่าแต่ละคลัสเตอร์ถูกแทนโดยวัตถุอย่างน้อยหนึ่งตัวในเซตที่เลือก มันเลือก random sample (ตัวอย่างสุ่ม) ของจุดข้อมูลสัมพันธ์กับจำนวนคลัสเตอร์ที่ต้องการสร้าง และจากนั้นใช้ greedy algorithm เพื่อรับเซตย่อยสุดท้ายที่เล็กลงสำหรับขั้นตอนถัดไป
2. Iteration Phase (ขั้นตอนวนซ้ำ)
ขั้นตอน iteration เลือก random set ของ k medoids จากเซตที่ลดแล้ว (reduced set) (ของ medoids) และแทนที่ "bad" medoids ด้วย medoids ใหม่ที่เลือกแบบสุ่ม หากการจัดกลุ่มดีขึ้น (clustering is increased)
สำหรับแต่ละ medoid ชุดของมิติถูกเลือกที่ระยะทางเฉลี่ยของพวกเขาเล็กเทียบกับ mathematical expectation (คาดการณ์ทางคณิตศาสตร์) จำนวนมิติทั้งหมดที่เกี่ยวข้องกับ medoids ควรเป็น k × l โดยที่ l เป็นพารามิเตอร์อินพุทที่เลือก average dimensionality (มิติเฉลี่ย) ของ cluster subareas
3. Refinement Phase (ขั้นตอนปรับปรุง)
ขั้นตอน refinement คำนวณมิติใหม่สำหรับแต่ละ medoid ขึ้นอยู่กับคลัสเตอร์ที่ค้นพบ มอบหมายจุดใหม่ให้ medoids และลบ outliers (ค่าผิดปกติ) PROCLUS แสดงให้เห็นว่าวิธีนี้มีประสิทธิภาพและขยายได้ (scalable) ในการค้นพบคลัสเตอร์มิติสูง
ไม่เหมือน CLIQUE ซึ่งสร้าง output หลาย overlapped clusters PROCLUS หา nonoverlapped partitions (พาร์ติชันที่ไม่ทับซ้อน) ของจุด คลัสเตอร์ที่ค้นพบสามารถให้ความเข้าใจที่ดีกว่าข้อมูลมิติสูง และสนับสนุนการวิเคราะห์ subsequence (ต่อเนื่อง) อื่นๆ
CLIQUE จำเป็นต้องค้นพบ subspaces ของ largest dimensionality (มิติใหญ่ที่สุด) ที่ high-density clusters มีอยู่ใน subspaces เหล่านั้น มันไม่ไวต่อลำดับของ input objects (order of input objects) และไม่แทน (pretend) canonical data distribution บางอย่าง มัน scales linearly (ขยายแบบเชิงเส้น) กับขนาดของ input และมี scalability ที่ดีที่สุดเมื่อจำนวนมิติในข้อมูลเพิ่มขึ้น
