มีเทคนิคต่างๆ ที่จำเป็นในการจัดการกับข้อจำกัดเฉพาะ หลักการทั่วไปในการจัดการกับข้อจำกัดที่แข็งและอ่อนซึ่งมีดังต่อไปนี้ -
การจัดการกับข้อจำกัดที่เข้มงวด − วิธีการทั่วไปในการจัดการกับข้อจำกัดที่ยากคือการพิจารณาข้อจำกัดในขั้นตอนการมอบหมายคลัสเตอร์อย่างเคร่งครัด จากชุดข้อมูลและกลุ่มของข้อจำกัดในตัวอย่าง (เช่น ข้อจำกัดที่ต้องลิงก์หรือไม่สามารถลิงก์ได้) เราจะพัฒนาวิธี k-mean เพื่อตอบสนองข้อจำกัดดังกล่าวได้อย่างไร อัลกอริทึม COP-kmeans ทำงานดังนี้ -
สร้างอินสแตนซ์ขั้นสูงสำหรับข้อจำกัดที่ต้องลิงก์ − มันสามารถคำนวณการปิดสกรรมกริยาของข้อจำกัดที่ต้องเชื่อมโยง ดังนั้น ข้อจำกัดที่ต้องเชื่อมโยงทั้งหมดถือเป็นความสัมพันธ์ที่เท่าเทียมกัน การปิดมีชุดย่อยของออบเจ็กต์หนึ่งชุดหรือหลายชุดซึ่งควรกำหนดออบเจ็กต์บางรายการในชุดย่อยให้กับคลัสเตอร์เดียว
มันสามารถกำหนดชุดย่อยดังกล่าว มันสามารถแทนที่บางวัตถุในชุดย่อยด้วยค่าเฉลี่ย อินสแตนซ์ขั้นสูงยังสร้างน้ำหนัก ซึ่งเป็นจำนวนวัตถุที่กำหนด หลังจากขั้นตอนนี้ ข้อจำกัดที่ต้องลิงก์จะได้รับการตอบสนองอย่างต่อเนื่อง
ดำเนินการจัดกลุ่ม k-mean ที่แก้ไข − ใน k-mean วัตถุจะถูกสร้างขึ้นที่จุดศูนย์กลางที่ใกล้ที่สุด มันสามารถเคารพข้อจำกัดที่ไม่สามารถเชื่อมโยงได้ และมันเปลี่ยนกระบวนการมอบหมายศูนย์ใน k-mean เป็นการมอบหมายศูนย์ที่ใกล้เคียงที่สุดที่เป็นไปได้
เมื่อวัตถุถูกกำหนดให้กับศูนย์ตามลำดับ ในทุกขั้นตอน จะสามารถมั่นใจได้ว่าการมอบหมายจนถึงตอนนี้จะไม่รบกวนข้อจำกัดที่ไม่สามารถเชื่อมโยงได้ วัตถุถูกกำหนดให้กับศูนย์กลางที่ใกล้ที่สุดเพื่อให้งานเป็นไปตามข้อจำกัดบางอย่างที่ไม่สามารถเชื่อมโยงได้
เนื่องจาก COP-k-mean กำหนดว่าไม่มีการละเมิดข้อจำกัดในแต่ละขั้นตอน จึงไม่จำเป็นต้องย้อนรอย เป็นอัลกอริธึมที่โลภสำหรับการสร้างคลัสเตอร์ที่ตรงตามข้อจำกัดทั้งหมด ได้รับการสนับสนุนว่าไม่มีข้อขัดแย้งระหว่างข้อจำกัด
การจัดการกับข้อจำกัดที่อ่อนนุ่ม − การทำคลัสเตอร์ที่มีข้อจำกัดที่อ่อนนุ่มเป็นปัญหาการปรับให้เหมาะสม เมื่อการจัดกลุ่มขัดขวางข้อจำกัดแบบนุ่มนวล จำเป็นต้องมีการปรับคลัสเตอร์ ดังนั้น จุดมุ่งหมายในการเพิ่มประสิทธิภาพของการจัดกลุ่มจึงมีสองส่วน เช่น การเพิ่มประสิทธิภาพด้านการจัดกลุ่มและการลดโทษการละเมิดข้อจำกัด บริการตามวัตถุประสงค์คือชุดของคะแนนคุณภาพการจัดกลุ่มและคะแนนบทลงโทษ
จากชุดข้อมูลและชุดของข้อจำกัดที่อ่อนนุ่มบนตัวอย่าง กลยุทธ์อัลกอริธึม CVQE (Constrained Vector Quantization Error) หมายถึงการจัดกลุ่มในขณะที่บังคับใช้บทลงโทษการละเมิดข้อจำกัด ฟังก์ชันวัตถุประสงค์ที่ใช้ใน CVQE คือระยะทางทั้งหมดที่ใช้ใน k-mean ซึ่งแก้ไขโดยบทลงโทษการละเมิดข้อจำกัด ซึ่งคำนวณได้ดังนี้ -
บทลงโทษสำหรับการละเมิดที่ต้องเชื่อมโยง − หากมีข้อจำกัดที่ต้องลิงก์กับอ็อบเจ็กต์ x และ y แต่สร้างเป็นสองศูนย์หลายจุด c1 และค2 ดังนั้นจึงละเมิดข้อจำกัด เป็นผลให้ dist (c1 ,c2 ) ระยะห่างระหว่าง c1 และค2 , ถูกแทรกลงในฟังก์ชันวัตถุประสงค์เป็นบทลงโทษ
บทลงโทษสำหรับการละเมิดที่ไม่สามารถเชื่อมโยงได้ − หากมีข้อจำกัดที่ไม่สามารถเชื่อมโยงบนอ็อบเจ็กต์ x และ y แต่ถูกสร้างขึ้นไปยังจุดศูนย์กลางร่วม c ดังนั้น ข้อจำกัดดังกล่าวจึงถูกละเมิด ระยะทาง dist (c,c ’ ) ระหว่าง c และ c ’ ถูกแทรกลงในฟังก์ชันวัตถุประสงค์เป็นบทลงโทษ
