التجميع بالارتباط

التجميع هو مشكلة تقسيم نقاط البيانات إلى مجموعات بناءً على التشابه أو الاختلاف. التجميع الارتباطي هو إطار عمل للتجميع يتم فيه تقسيم مجموعة من الكائنات إلى مجموعات بناءً على معلومات التشابه والاختلاف بين كل زوج، دون الحاجة إلى تحديد عدد المجموعات مسبقًا. ^{[ 1 ]}

في مجال تعلم الآلة ، يعتمد التجميع الارتباطي (المعروف أيضًا باسم تحرير المجموعات ) على دراسة الحالات التي تكون فيها علاقات التشابه أو الاختلاف بين الكائنات معروفة. ويُصاغ النموذج القياسي المدخلات على شكل رسم بياني كامل غير مُرجّح.${\displaystyle G=(V,E)}$حيث يتم تسمية كل حافة إما${\displaystyle +}$أو${\displaystyle -}$(أي أن الرسم البياني هو رسم بياني موقّع )، مما يشير إلى ما إذا كانت نقاط النهاية المقابلة متشابهة أم مختلفة.

الهدف هو إيجاد تجميع (أي تقسيم لـ${\displaystyle V}$يهدف هذا الأسلوب إما إلى زيادة عدد الاتفاقات إلى أقصى حد - وهو مجموع الحواف الموجبة التي تقع نقاط نهايتها في نفس المجموعة والحواف السالبة التي تقع نقاط نهايتها في مجموعات مختلفة - أو إلى تقليل عدد حالات عدم الاتفاق - وهو مجموع الحواف الموجبة التي تتباعد نقاط نهايتها والحواف السالبة التي تقع نقاط نهايتها في نفس المجموعة. وعلى عكس أساليب التجميع الأخرى مثل k-means ، لا يتطلب التجميع بالارتباط تحديد عدد المجموعات.${\displaystyle k}$مقدماً.

ليس من الممكن دائمًا إيجاد تجميع خالٍ من أي اختلافات. على سبيل المثال، لنفترض وجود رسم بياني مثلثي يحتوي على ضلعين موجبين وضلع سالب واحد. في هذه الحالة، يُظهر كل تجميع اختلافًا واحدًا على الأقل. تُعرف هذه التكوينات في الأدبيات باسم المثلثات السيئة . ^{[ 2 ]}

من منظور حسابي، يُعدّ تحسين هدف تجميع الارتباطات تحديًا كبيرًا. تُصنّف هذه المسألة (بصيغتها القرارية) ضمن مسائل NP-complete . ^{[ 3 ]} وقد طوّرت العديد من الدراسات اللاحقة خوارزميات تقريبية لتجميع الارتباطات في ظل افتراضات مختلفة، بما في ذلك الرسوم البيانية الكاملة أو العامة، والرسوم البيانية غير الموزونة أو الموزونة، وذلك لتحقيق أهداف التصغير والتعظيم على حد سواء. تُعتبر هذه المسألة من مسائل التحسين التوافقي الأساسية ، وقد طُوّرت العديد من التقنيات الخوارزمية لمعالجتها.

وقد دُرست هذه المشكلة على نطاق واسع في مختلف التخصصات. وقدّم وحيد وحسيني مراجعة شاملة للأدبيات المتعلقة بالبحوث المبكرة حول تجميع الارتباطات. ^{[ 4 ]}

يترك${\displaystyle G=(V,E)}$ليكن رسمًا بيانيًا يحتوي على عقد${\displaystyle V}$والحواف${\displaystyle E}$. تكتل من${\displaystyle G}$هو تقسيم لمجموعة العقد الخاصة به${\displaystyle \Pi =\{\pi _{1},\dots ,\pi _{k}\}}$مع${\displaystyle V=\pi _{1}\cup \dots \cup \pi _{k}}$و${\displaystyle \pi _{i}\cap \pi _{j}=\emptyset }$ل${\displaystyle i\neq j}$بالنسبة لتجميع معين${\displaystyle \Pi }$، يترك${\displaystyle \delta (\Pi )=\{\{u,v\}\in E\mid \{u,v\}\not \subseteq \pi \;\forall \pi \in \Pi \}}$تشير إلى مجموعة جزئية من حواف${\displaystyle G}$والتي تقع نقاط نهايتها في مجموعات فرعية مختلفة من التجميع${\displaystyle \Pi }$والآن، لنبدأ${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$لتكن دالة تُسند وزنًا غير سالب لكل حافة من حواف الرسم البياني، ولتكن${\displaystyle E=E^{+}\cup E^{-}}$أن يكون تقسيم الحواف إلى أجزاء جذابة (${\displaystyle E^{+}}$) ومثير للاشمئزاز (${\displaystyle E^{-}}$) الحواف؛ أي أن الحواف موقعة .

تُعدّ مشكلة التجميع ذات الارتباط الأدنى من عدم الاتفاق هي مشكلة التحسين التالية : $${\displaystyle {\begin{aligned}&{\underset {\Pi} {\operatorname {minimize} }}&&\sum _{e\in E^{+}\cap \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\setminus \delta (\Pi )}w_{e}\;.\end{محاذاة}}}$$ هنا، المجموعة${\displaystyle E^{+}\cap \delta (\Pi )}$يحتوي على الحواف الجذابة التي تقع نقاط نهايتها في مكونات مختلفة فيما يتعلق بالتجميع${\displaystyle \Pi }$والمجموعة${\displaystyle E^{-}\setminus \delta (\Pi )}$يحتوي على الحواف التنافرية التي تقع نقاط نهايتها في نفس المكون بالنسبة للتجميع${\displaystyle \Pi }$تحتوي هاتان المجموعتان معًا على جميع الحواف التي لا تتوافق مع التجميع.${\displaystyle \Pi }$.

على غرار مشكلة التجميع بالارتباط ذي الحد الأدنى من عدم الاتفاق، تُعرَّف مشكلة التجميع بالارتباط ذي الحد الأقصى من الاتفاق على النحو التالي: $${\displaystyle {\begin{aligned}&{\underset {\Pi} {\operatorname {maximize} }}&&\sum _{e\in E^{+}\setminus \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\cap \delta (\Pi )}w_{e}\;.\end{محاذاة}}}$$ هنا، المجموعة${\displaystyle E^{+}\setminus \delta (\Pi )}$يحتوي على الحواف الجذابة التي تقع نقاط نهايتها في نفس المكون بالنسبة للتجميع${\displaystyle \Pi }$والمجموعة${\displaystyle E^{-}\cap \delta (\Pi )}$يحتوي على الحواف التنافرية التي تقع نقاط نهايتها في مكونات مختلفة بالنسبة للتجميع${\displaystyle \Pi }$تحتوي هاتان المجموعتان معًا على جميع الحواف التي تتفق مع التجميع.${\displaystyle \Pi }$.

بدلاً من صياغة مشكلة تجميع الارتباطات بدلالة أوزان الحواف غير السالبة وتقسيم الحواف إلى حواف جاذبة وحواف دافعة، تتم صياغة المشكلة أيضاً بدلالة تكاليف الحواف الموجبة والسالبة دون تقسيم مجموعة الحواف بشكل صريح. بالنسبة للأوزان المعطاة${\displaystyle w\colon E\to \mathbb {R} _{\geq 0}}$وتقسيم معين${\displaystyle E=E^{+}\cup E^{-}}$بتقسيم الحواف إلى حواف جاذبة وحواف دافعة، يمكن تحديد تكاليف الحواف بواسطة $${\displaystyle {\begin{aligned}c_{e}={\begin{cases}\;\;w_{e}&{\text{if }}e\in E^{+}\\-w_{e}&{\text{if }}e\in E^{-}\end{cases}}\end{aligned}}}$$ للجميع${\displaystyle e\in E}$.

يُقال إن الحافة التي تقع نقاط نهايتها في مجموعات مختلفة مقطوعة.${\displaystyle \delta (\Pi )}$يُطلق على عملية قطع جميع الحواف اسم القطع المتعدد ^{[ 5 ]}${\displaystyle G}$.

مشكلة القطع المتعدد بأقل تكلفة هي مشكلة إيجاد تجميع${\displaystyle \Pi }$ل${\displaystyle G}$بحيث يكون مجموع تكاليف الحواف التي تقع نقاط نهايتها في مجموعات مختلفة في حده الأدنى: $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in \delta (\Pi )}c_{e}\;.\end{aligned}}}$$

على غرار مشكلة القطع المتعدد بأقل تكلفة، فإن توليد هيكل التحالف في ألعاب الرسم البياني الموزون ^{[ 6 ]} هو مشكلة إيجاد تجميع بحيث يكون مجموع تكاليف الحواف التي لم يتم قطعها هو الحد الأقصى: $${\displaystyle {\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}}$$ تُعرف هذه الصيغة أيضًا باسم مشكلة تقسيم الزمرة. ^{[ 7 ]}

يمكن إثبات أن جميع المسائل الأربع المذكورة أعلاه متكافئة. وهذا يعني أن التجميع الأمثل لأي من الأهداف الأربعة هو الأمثل لجميع الأهداف الأربعة.

إذا كان الرسم البياني يسمح بتجميع البيانات دون أي اختلافات، فإن حذف جميع الحواف السالبة وحساب المكونات المتصلة للرسم البياني المتبقي يُنتج تجميعًا مثاليًا. وقد وضع ديفيس شرطًا ضروريًا وكافيًا لوجود مثل هذا التجميع: لا يمكن لأي دورة في الرسم البياني أن تحتوي على حافة سالبة واحدة فقط. ^{[ 8 ]}

ناقش بانسال وآخرون ^{[ 9 ]} برهان اكتمال NP، وقدموا أيضًا خوارزمية تقريب بمعامل ثابت وخوارزمية تقريب بزمن متعدد الحدود لإيجاد المجموعات في هذا السياق. واقترح أيلون وآخرون ^{[ 10 ]} خوارزمية تقريب عشوائية من الدرجة الثالثة لنفس المشكلة.

CC-Pivot (G=(V,E + ,E − )) اختر محورًا عشوائيًا i ∈ V تعيين${\displaystyle C=\{i\}}$، V'=Ø لكل j ∈ V، j ≠ i؛ إذا كان (i,j) ∈ E + فإن أضف j إلى C وإلا (إذا كان (i,j) ∈ E − ) أضف j إلى V' ليكن G' هو الرسم البياني الجزئي المستحث بواسطة V' إرجاع التجميع C،CC-Pivot(G')

يُبين المؤلفون أن الخوارزمية المذكورة أعلاه هي خوارزمية تقريبية من الدرجة الثالثة لتجميع الارتباطات. أفضل خوارزمية تقريبية معروفة حاليًا لهذه المسألة، والتي تعمل في زمن متعدد الحدود، تحقق تقريبًا من الدرجة الثانية (2.06) عن طريق تقريب برنامج خطي، كما أوضح تشاولا ، وماكاريشيف، وشرام، وياروسلافتسيف . ^{[ 11 ]}

أثبت كاربينسكي وشودي ^{[ 12 ]} وجود مخطط تقريبي متعدد الحدود (PTAS) لتلك المشكلة على الرسوم البيانية الكاملة وعدد ثابت من المجموعات.

في عام ٢٠١١، أظهر باجون وغالون ^{[ ١٣ ]} أن تحسين دالة التجميع الارتباطي يرتبط ارتباطًا وثيقًا بأساليب التحسين المنفصلة المعروفة . في بحثهما، اقترحا تحليلًا احتماليًا للنموذج الضمني الأساسي الذي يسمح لدالة التجميع الارتباطي بتقدير العدد الأساسي للمجموعات. يشير هذا التحليل إلى أن الدالة تفترض توزيعًا احتماليًا أوليًا منتظمًا على جميع التقسيمات الممكنة بغض النظر عن عدد مجموعاتها. وبالتالي، يظهر توزيع احتمالي أولي غير منتظم على عدد المجموعات.

تقترح هذه الدراسة عدة خوارزميات تحسين منفصلة تتناسب بكفاءة مع عدد العناصر (أظهرت التجارب نتائج مع أكثر من 100,000 متغير). كما قيّمت دراسة باجون وغالون فعالية استعادة العدد الأساسي للمجموعات في تطبيقات متعددة.

يرتبط التجميع القائم على الارتباط بمهمة مختلفة، حيث يُفترض وجود ارتباطات بين سمات متجهات الميزات في فضاء عالي الأبعاد، مما يوجه عملية التجميع . قد تختلف هذه الارتباطات بين المجموعات المختلفة، وبالتالي لا يمكن لفك الارتباط الشامل اختزالها إلى التجميع التقليدي (غير المرتبط).

تؤدي الارتباطات بين مجموعات فرعية من السمات إلى أشكال مكانية مختلفة للتجمعات. لذا، يُحدد التشابه بين عناصر التجمعات من خلال مراعاة أنماط الارتباط المحلية. وبناءً على هذا المفهوم، تم تقديم المصطلح في المرجع ^{[ 14 ]} بالتزامن مع المفهوم المذكور أعلاه. وتُناقش طرق مختلفة لتجميع الارتباطات من هذا النوع في المرجع ^{[ 15 ]} ، بينما تُناقش العلاقة بأنواع التجميع المختلفة في المرجع ^{[ 16 ]} . انظر أيضًا: تجميع البيانات عالية الأبعاد .

يمكن إثبات أن التجميع الترابطي (وفقًا لهذا التعريف) يرتبط ارتباطًا وثيقًا بالتجميع الثنائي . وكما هو الحال في التجميع الثنائي، فإن الهدف هو تحديد مجموعات من العناصر التي تشترك في ارتباط في بعض سماتها؛ حيث يكون هذا الارتباط عادةً سمة مميزة للمجموعات الفردية.

• التنفيذ بلغة بايثون