ควรใช้วิธีการจัดกลุ่มการแบ่งพาร์ติชันเพราะจะลดระยะห่างระหว่างชุดและศูนย์กลางคลัสเตอร์ หากเลือกวิธี k-mean ได้ ศูนย์คลัสเตอร์จะไม่สามารถใช้งานได้เนื่องจากมีสิ่งกีดขวาง
ตัวอย่างเช่น กระจุกอาจกลายเป็นศูนย์กลางของทะเลสาบ กล่าวอีกนัยหนึ่ง วิธี k-medoids จะเลือกวัตถุภายในคลัสเตอร์เป็นศูนย์กลาง และรับประกันได้ว่าปัญหาจะไม่ปรากฏขึ้น
ทุกครั้งที่มีการเลือก Medoid ใหม่ จะต้องคำนวณระยะทางระหว่างแต่ละวัตถุและศูนย์กลางคลัสเตอร์ที่เลือกใหม่ เนื่องจากวัตถุสองชิ้นอาจมีสิ่งกีดขวาง ระยะห่างระหว่างวัตถุสองชิ้นจึงสามารถหาได้โดยการคำนวณทางเรขาคณิต (เช่น เกี่ยวข้องกับสามเหลี่ยม)
ค่าใช้จ่ายในการคำนวณอาจสูงได้หากมีวัตถุและสิ่งกีดขวางจำนวนมาก ปัญหาการจัดกลุ่มที่มีสิ่งกีดขวางสามารถกำหนดได้โดยใช้คำอธิบายแบบกราฟิก อันดับแรก จุด p ปรากฏจากจุดอื่น q ในพื้นที่ R หากเส้นตรงที่อยู่ติดกัน p และ q ไม่ตัดกับสิ่งกีดขวาง
กราฟการมองเห็นคือกราฟ V G =(V, E) รวมถึงจุดยอดแต่ละจุดของสิ่งกีดขวางมีโหนดที่เท่ากันใน V และสองโหนด v1 และ v2 ใน V จะรวมกันโดยขอบใน E ถ้าหากจุดยอดเทียบเท่าที่พวกเขากำหนดนั้นมองเห็นกันได้เท่านั้น
ให้ VG’ =(V’, E’) เป็นกราฟการมองเห็นที่สร้างจาก VG โดยการแทรกจุดเพิ่มเติมสองจุด คือ p และ q ใน V’ E' รวมขอบที่เพิ่มจุดสองจุดใน V0 หากมองเห็นจุดสองจุดร่วมกัน
สามารถใช้เพื่อลดต้นทุนในการคำนวณระยะทางระหว่างออบเจ็กต์หรือจุดสองชุดใดก็ได้ สามารถใช้วิธีการประมวลผลล่วงหน้าและการปรับให้เหมาะสมได้หลายวิธี มีจุดกลุ่มแนวทางหนึ่งจุดที่อยู่ใกล้กันในไมโครคลัสเตอร์ สามารถทำได้โดยการหาพื้นที่ R เป็นรูปสามเหลี่ยมก่อน จากนั้นจึงรวมจุดที่อยู่ใกล้เคียงในรูปสามเหลี่ยมที่คล้ายกันเข้าเป็นกลุ่มย่อย โดยใช้แนวทางที่คล้ายกับ BIRCH หรือ DBSCAN
ด้วยการประมวลผลไมโครคลัสเตอร์แทนจุดเดียว การคำนวณทั้งหมดจะลดลง หลังจากนั้น การคำนวณล่วงหน้าสามารถนำมาใช้เพื่อสร้างดัชนีการรวมสองประเภทขึ้นอยู่กับการคำนวณของเส้นทางที่สั้นที่สุด -
-
ดัชนี VV สำหรับจุดยอดอุปสรรคบางคู่
-
ดัชนี MV สำหรับไมโครคลัสเตอร์และจุดยอดอุปสรรคบางคู่ ช่วยให้ดัชนีช่วยเพิ่มประสิทธิภาพโดยรวมได้มากขึ้น
ด้วยการคำนวณล่วงหน้าและการเพิ่มประสิทธิภาพดังกล่าว ระยะห่างระหว่างจุดสองจุดใดๆ (ที่วิธีการละเอียดของไมโครคลัสเตอร์) สามารถคำนวณได้อย่างมีประสิทธิภาพ ดังนั้น กระบวนการจัดกลุ่มสามารถทำได้ในลักษณะที่คล้ายกับอัลกอริทึม k-medoids ที่มีประสิทธิภาพโดยทั่วไป ซึ่งรวมถึง CLARANS และบรรลุคุณภาพการจัดกลุ่มที่ดีที่สุดสำหรับชุดข้อมูลขนาดใหญ่
