التجميع المقيد: متى تتعارض قيود الوصل والفصل؟

الخلاصة السريعة

راجع القيود قبل التجميع: قد يفرض مسار من الوصل جمع عنصرين يمنع قيد فصل اجتماعهما، وقد يكون عدد المجموعات المطلوب غير كافٍ رغم غياب هذا التعارض.

• must-link يفرض المجموعة نفسها وcannot-link يمنعها؛ الوصل ينقل العضوية عبر سلسلة، ولا تنقل سلسلة الفصل الحكم نفسه. ^[1]
• وصل أ بب ووصل ب بج يفرضان وصل أ بج؛ إضافة فصل أ وج تجعل هذه القيود مستحيلة معًا في تقسيم صلب.
• فصل أ وب وفصل ب وج لا يمنع جمع أ وج؛ يمكن وضعهما معًا وب وحده في تقسيم من مجموعتين.
• إذا فصلنا الأزواج الثلاثة أ وب وج، نحتاج ثلاث مجموعات مختلفة على الأقل؛ طلب مجموعتين يستحيل لهذا المثال مهما كانت المسافات.

أي علاقة نكتب على الزوج؟

تستخدم الورقة الأصلية قيودًا زوجية للوصل والفصل، وتوضح أن الوصل متعدٍّ وأن بعض قيود الفصل تنتقل عبر علاقة وصل. ^[1]

سنفترض عناصر أ وب وج وتقسيمًا صلبًا؛ لكل عنصر مجموعة واحدة. لا نفترض مواقع أو مراكز، لأن السؤال الأول عن إمكان احترام القيود قبل تفضيل أقرب مجموعة.

اكتب نوع العلاقة مع الزوج، لا علامة عامة تعني «مرتبط». فصلة الوصل تعني اجتماع العضوية، بينما صلة الفصل تعني اختلافها. تحويل العلاقتين إلى الحافة نفسها في سجل واحد يمحو الشرط الذي نريد فحصه.

تعارض ينتج من سلسلة وصل

نضع قيد وصل بين أ وب، وآخر بين ب وج. ما دام ب في المجموعة نفسها مع كليهما، تكون العناصر الثلاثة في مجموعة واحدة. هذا استنتاج من العضوية، لا من قرب القيم.

نضيف قيد فصل بين أ وج. صار مطلوبًا أن يجتمعا وألا يجتمعا في الوقت نفسه؛ لا يستطيع أي تقسيم صلب احترام جميع القيود. زيادة عدد المجموعات لا تصلح هذا التعارض.

يمكن كشفه بتجميع العناصر المرتبطة بسلاسل وصل أولًا، ثم البحث عن فصل داخل المجموعة المنطقية الناتجة. في سجل مثالنا، احتفظ بالقيدين الأصليين وقيد الفصل حتى يمكن مراجعة مصدر التعارض بدل حذف علاقة بلا تفسير.

لماذا لا تنتقل علاقة الفصل بالطريقة نفسها؟

نبدأ حالة جديدة فيها فصل أ وب وفصل ب وج فقط، دون قيود وصل. تقسيم {أ،ج} و{ب} يحقق الشرطين: أ ليس مع ب، وج ليس مع ب.

لذلك لا نستنتج فصل أ وج من السلسلة. الاختلاف عن عنصر مشترك لا يفرض اختلاف الطرفين بعضهما عن بعض. ولو أضفنا وصل أ وج في هذه الحالة، لبقي التقسيم نفسه متوافقًا مع القيود.

لا تخلط هذا المثال بالحالة السابقة؛ سجل العلاقات تغير. نقل استنتاج من حالة تحمل وصلًا إلى حالة تحمل فصلًا فقط يجعل النتيجة تبدو قاعدة عامة، بينما يتوقف الحكم على نوع كل علاقة.

قيود متسقة وعدد مجموعات غير كافٍ

نضيف الآن الفصل الثالث أ وج إلى قيدي الفصل السابقين. يجب أن تختلف عضوية كل زوج من العناصر الثلاثة؛ لا تكفي مجموعتان لأن عنصرين سيشتركان حتمًا في إحداهما.

ثلاث مجموعات مفردة تحقق الشروط، وطلب مجموعتين لا يحققها. هذا قيد على العدد، مختلف عن تعارض الوصل والفصل الذي لم يصلحه أي عدد. المسافات لا تغير هذه الحجة المنطقية.

هذه أمثلة تحقق يدوي لا نتيجة تشغيل COP-Kmeans. قبل تفسير فشل برنامج بعينه، افحص سجل القيود وعدد المجموعات وطريقة التنفيذ. أمثلتنا تثبت استحالة الحالات المحددة فقط، ولا تجعل كل رسالة فشل دليلًا على استحالة المسألة كلها.