خوارزمية التجميع HCS

📅 آخر تحديث: ٢١ يوليو ٢٠٢٦
✍️ نُشر في: ٢١ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

خوارزمية التجميع للرسوم البيانية الفرعية عالية الترابط (HCS) (المعروفة أيضًا باسم خوارزمية HCS ، وأسماء أخرى مثل المجموعات/المكونات/النوى عالية الترابط ) هي خوارزمية تعتمد على ترابط الرسوم البيانية لتحليل التجميع . تعمل هذه الخوارزمية من خلال تمثيل بيانات التشابه في رسم بياني للتشابه، ثم إيجاد جميع الرسوم البيانية الفرعية عالية الترابط. ولا تفترض هذه الخوارزمية أي افتراضات مسبقة حول عدد المجموعات. وقد نُشرت هذه الخوارزمية بواسطة إيريز هارتوف ورون شامير في عام 2000. [ 1 ]

تقدم خوارزمية HCS حلاً للتجميع، وهو أمر ذو معنى جوهري في مجال التطبيق، حيث يجب أن يكون قطر كل مجموعة حلول 2 بينما سيكون قطر اتحاد مجموعتي حلول 3.

نمذجة التشابه والمعالجة المسبقة

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

الخوارزمية

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

تُحدد خوارزمية التجميع HCS جميع الرسوم البيانية الفرعية التي تحتوي على n رأسًا بحيث يحتوي القطع الأدنى لتلك الرسوم البيانية الفرعية على أكثر من n/2 حافة، وتُصنفها على أنها مجموعات. يُطلق على هذا النوع من الرسوم البيانية الفرعية اسم الرسم البياني الفرعي عالي الاتصال (HCS). لا تُعتبر الرؤوس المفردة مجموعات، ويتم تجميعها في مجموعة أحادية S.

بالنظر إلى الرسم البياني للتشابه G(V,E)، ستتحقق خوارزمية التجميع HCS مما إذا كان متصلاً بشكل كبير بالفعل، وإذا كان الأمر كذلك، فستعيد G، وإلا فستستخدم القطع الأدنى لـ G لتقسيم G إلى رسمين بيانيين فرعيين H و H'، وستقوم بتشغيل خوارزمية التجميع HCS بشكل متكرر على H و H'.

مثال

يوضح الرسم المتحرك التالي كيف تقوم خوارزمية التجميع HCS بتقسيم الرسم البياني للتشابه إلى ثلاث مجموعات.

الشفرة الزائفة

الدالة HCS(G(V, E)) هي: إذا كانت G متصلة بشكل كبير، فأرجع ( G )، وإلا فأرجع ( H1 , H2 , C ) ← MINIMUMCUT( G ). HCS( H1 ) HCS( H2 ) نهاية إذا نهاية الدالة

تُعدّ خطوة إيجاد القطع الأدنى على الرسم البياني G إجراءً فرعيًا يمكن تنفيذه باستخدام خوارزميات مختلفة لهذه المسألة. انظر أدناه مثالًا لخوارزمية إيجاد القطع الأدنى باستخدام العشوائية.

تعقيد

يُحدَّد زمن تشغيل خوارزمية التجميع HCS بالمعادلة N × f(n, m). حيث f(n, m) هي التعقيد الزمني لحساب القطع الأدنى في رسم بياني ذي n رأسًا و m ضلعًا، و N هو عدد المجموعات التي تم العثور عليها. في العديد من التطبيقات، يكون N  <<  n.

للحصول على خوارزميات سريعة لإيجاد القطع الأدنى في رسم بياني غير مرجح:

إثباتات الخصائص

تمتلك المجموعات التي تنتجها خوارزمية التجميع HCS العديد من الخصائص التي يمكن أن توضح تجانس الحل وفصله.

النظرية 1: قطر كل رسم بياني عالي الاتصال هو اثنين على الأكثر.

البرهان: ليكن n=|G|. إذا كان للمخطط G رأس x بدرجة ≤ n/2، فإن G يحتوي على قطع أدنى (يعزل x) بحواف ≤ n/2، لذا فإن G ليس عالي الاتصال. أما إذا كان G عالي الاتصال، فإن درجة كل رأس فيه تكون ≥ n/2. هناك نظرية شهيرة في نظرية المخططات تنص على أنه إذا كانت درجة كل رأس في G ≥ n/2، فإن قطر G (أطول مسار بين أي رأسين) ≤ 2.

النظرية 2 (أ) عدد الحواف في الرسم البياني عالي الاتصال هو دالة تربيعية. (ب) عدد الحواف التي تُزال في كل تكرار لخوارزمية HCS هو دالة خطية على الأكثر.

البرهان: (أ) من النظرية 1 نعلم أن درجة كل رأس أكبر من أو تساوي n/2. لذلك، يجب أن يكون عدد الحواف في الرسم البياني عالي الاتصال على الأقل (n × n/2)/2، حيث نجمع درجات كل رأس ونقسم على 2.

(ب) بحسب التعريف، فإن كل تكرار يزيل قطعًا أدنى مع حواف أقل من أو تساوي n/2.

تُقدّم النظريتان 1 و2أ مؤشراً قوياً على تجانس المجموعة النهائية. أما الحلول الأفضل فتتناول الحالة التي تكون فيها جميع رؤوس المجموعة متصلة، وهو أمر بالغ الصرامة، كما أنه صعب الحل من فئة NP .

تشير النظرية 2ب إلى الانفصال حيث أن أي مجموعتين نهائيتين C1 و C2 لم تكونا منفصلتين إلا إذا كان هناك على الأكثر O(C1+C2) من الحواف بينهما (على عكس الحواف التربيعية داخل المجموعات).

الاختلافات

تبني العناصر الفردية : يمكن للمجموعات التي تبقى كعناصر فردية بعد عملية التجميع الأولية أن "تتبناها" بناءً على مدى تشابهها مع المجموعة. إذا كان الحد الأقصى لعدد الجيران لمجموعة معينة كبيرًا بما يكفي، فيمكن إضافتها إلى تلك المجموعة.

إزالة الرؤوس ذات الدرجة المنخفضة : عندما يحتوي الرسم البياني المُدخل على رؤوس ذات درجات منخفضة، لا يُنصح بتشغيل الخوارزمية لأنها مُكلفة حسابيًا وغير مُفيدة. بدلاً من ذلك، يُمكن تحسين الخوارزمية بإزالة جميع الرؤوس ذات الدرجة الأقل من عتبة مُعينة.

أمثلة على استخدام نظام HCS

مراجع

  1. ↑ هارتوف، إي.؛ شامير، ر. (2000)، "خوارزمية تجميع تعتمد على اتصال الرسم البياني" ، رسائل معالجة المعلومات ، 76 ( 4-6 ): 175-181 ، doi : 10.1016/S0020-0190(00)00142-3
  2. ^ إي هارتوف، آو شميت، جيه لانج، إس ماير-إيويرت، إتش ليراش، آر شامير. "خوارزمية لتجميع بصمات [كدنا]." علم الجينوم 66، لا. 3 (2000): 249-256.
  3. ↑ جوريسيكا، إيغور، ودينيس ويغل. اكتشاف المعرفة في علم البروتينات. المجلد 8. مطبعة CRC، 2006.
  4. ↑ Xu, Rui, and Donald Wunsch. “Survey of clustering algorithms.” Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.
  5. ↑ شاران، ر.؛ شامير، ر. (2000)، "CLICK: خوارزمية تجميع مع تطبيقات لتحليل التعبير الجيني"، وقائع ISMB '00 ، 8 : 307-316C، PMID 10977092 
  6. ↑ هوفنر، ف.؛ كوموسيفيتش، س.؛ ليبتراو، أ.؛ نيدرماير، ر. (2014)، "تقسيم الشبكات البيولوجية إلى مجموعات عالية الترابط مع تغطية قصوى للحواف"، معاملات IEEE/ACM في علم الأحياء الحاسوبي والمعلوماتية الحيوية ، 11 (3): 455-467 ، CiteSeerX 10.1.1.377.1900 ، doi : 10.1109/TCBB.2013.177 ، PMID 26356014 ، S2CID 991687