ความท้าทายของการจัดกลุ่มแบบ Partitioning กับอุปสรรค
วิธีการจัดกลุ่มแบบแบ่งพาร์ติชัน (partitioning clustering method) น่าประสงค์เพราะมันลดระยะทางระหว่างเซตและ cluster centers ของพวกเขา หากเลือก k-means method cluster center อาจไม่พร้อมใช้งาน (cannot be available) กำหนดโดยการมีอยู่ของ obstacles (อุปสรรค)
ตัวอย่างเช่น คลัสเตอร์อาจกลายเป็นอยู่กลางทะเลสาบ (in the center of a lake) ในคำอื่น วิธี k-medoids เลือกวัตถุภายในคลัสเตอร์เป็น center และดังนั้นรับประกันว่าปัญหาจะไม่เกิดขึ้น
ทุกครั้งที่ medoid ใหม่ถูกเลือก ระยะทางระหว่างแต่ละวัตถุและ cluster center ใหม่ที่เลือก ต้องคำนวณใหม่ (recalculated) เนื่องจากอาจมี obstacles ระหว่างสองวัตถุ ระยะทางระหว่างสองวัตถุสามารถนำมาได้จาก geometric computations (การคำนวณทางเรขาคณิต) (เช่น เกี่ยวข้องกับ triangulation - การสามเหลี่ยม)
ต้นทุนการคำนวณ (computational cost) อาจสูงขึ้น หากมีจำนวนวัตถุและ obstacles มาก ปัญหาการจัดกลุ่มกับอุปสรรค สามารถนิยามได้โดยใช้ graphical representation (การแทนที่ทางกราฟิก)
Visibility Graph (กราฟการมองเห็น)
ขั้นแรก จุด p ถูกมองเห็น (visible) จากจุด q อีกจุดหนึ่งในพื้นที่ R หากเส้นตรงที่เชื่อม p และ q ไม่ intersect (ไม่อยู่ภายใน/ไม่ตัด) obstacles ใดๆ
Visibility graph คือ กราฟ VG = (V, E) รวมถึงแต่ละ vertex (จุดยอด) ของ obstacles มีโหนดเทียบเท่าใน V และสองโหนด v1 และ v2 ใน V ถูกเชื่อมต่อโดย edge (ขอบ) ใน E ก็ต่อเมื่อ vertices เทียบเท่าที่พวกเขานิยาม มองเห็นกัน (visible to each other)
ให้ VG' = (V', E') เป็น visibility graph ที่สร้างจาก VG โดยเพิ่มจุดเพิ่มเติมสองจุด p และ q ใน V' E' รวม edge เชื่อมสองจุดใน V0 หากสองจุดมองเห็นร่วมกัน (jointly visible)
การเพิ่มประสิทธิภาพการคำนวณระยะทาง
เพื่อลดต้นทุนการคำนวณระยะทางระหว่างคู่วัตถุหรือจุดใดๆ หลายการทำ preprocessing (การประมวลผลล่วงหน้า) และ optimization approaches (แนวทางเพิ่มประสิทธิภาพ) สามารถใช้ได้ มีหนึ่งแนวทาง คือ จัดกลุ่มจุดที่อยู่ใกล้กันเป็น microclusters สามารถทำได้โดยการ triangulate (แบ่งสามเหลี่ยม) พื้นที่ R เป็นสามเหลี่ยม ก่อน แล้วจึงรวมจุดที่อยู่ใกล้กันในสามเหลี่ยมเดียวกันเป็น microclusters โดยใช้วิธีคล้าย BIRCH หรือ DBSCAN
ด้วยการประมวลผล microclusters แทนจุดเดี่ยว การคำนวณโดยรวมลดลง หลังจากนั้น precomputation (การคำนวณล่วงหน้า) สามารถนำไปใช้เพื่อสร้างดัชนีการเชื่อมต่อ (join indices) สองประเภท ขึ้นอยู่กับการคำนวณ shortest paths (เส้นทางสั้นที่สุด):
VV indices สำหรับทุกคู่ของ obstacle vertices
MV indices สำหรับทุกคู่ของ microcluster และ obstacle vertex ดัชนีเหล่านี้ช่วยเพิ่มประสิทธิภาพโดยรวม (overall performance) มากขึ้น
ด้วย precomputation และ optimization ดังกล่าว ระยะทางระหว่างสองจุดใดๆ (ในระดับรายละเอียดของ microcluster) สามารถคำนวณได้อย่างมีประสิทธิภาพ ดังนั้น กระบวนการจัดกลุ่มสามารถดำเนินการได้ในลักษณะคล้ายกับ typical efficient k-medoids algorithm เช่น CLARANS และทำให้ได้ clustering quality ที่ดีสำหรับชุดข้อมูลขนาดใหญ่
