فهم العنقدة الهرميّة
تبدأ العنقدة التجميعيّة بكل مشاهدة عنقودًا من عنصر واحد، وتدمج مرارًا أقلّ العنقودين تباينًا إلى أن يبقى عنقود واحد. ويُسجَّل مقدار التباين الذي وقع عنده كل دمج بوصفه ارتفاعه، وسجلّ عمليّات الدمج هذا هو مخطّط الشجرة.
وقطع المخطّط أفقيًا ينتج عنقدة، وعدد الخطوط الرأسيّة التي يعبرها القطع هو عدد العناقيد. فالشجرة الواحدة تحوي إذن جوابًا لكل k دفعةً واحدة، وهذه هي الميزة العمليّة الرئيسة على خوارزميّة المتوسّطات K. والعنقدات الناتجة متداخلة، إذ يُنقّح كل قطع ما فوقه.
وذلك التداخل افتراض لا هديّة. فالطريقة تشترط أن تقع عناقيد مستوًى داخل عناقيد المستوى الذي فوقه، فإن لم يكن التجميع الحقيقي متداخلًا - كأن يقطع أفضل انقسام بحسب سمة أفضلَ انقسام بحسب أخرى - فلن يستردّه أي قطع للشجرة، وستُفرَض هرميّة على بيانات لا هرميّة فيها.
والدمج يقتضي تباينًا بين المجموعات لا بين النقاط، وليس ثمّة وجه واحد صحيح لتوسيع أحدهما إلى الآخر. فالوصل الأقصى يأخذ أكبر مسافة بين نقطة من مجموعة ونقطة من الأخرى، والأدنى أصغرها، والمتوسّط متوسّطها، والمركزي المسافة بين المركزين. وهذا الاختيار يغيّر الجواب لا عرضه فحسب.
كيفية الحساب
complete: max d(a, b) single: min d(a, b) average: mean d(a, b), a ∈ A, b ∈ B
حيث
- A, B
- العنقودان اللذان يُقاس التباين بينهما
- d(a, b)
- التباين بين مشاهدة مفردة من A وأخرى من B
- height
- قيمة تباين المجموعتين لحظة اندماج العنقودين
مثال على العنقدة الهرميّة
خذ عشر نقاط في المستوي: مجموعة متراصّة من ثلاث يسارًا، ومجموعة متراصّة من ثلاث يمينًا، وأربع نقاط متساوية التباعد تصل بينهما. اقطع كل مخطّط شجرة إلى عنقودين فتختلف الوصلات. فالوصل الأقصى والمتوسّط يشطران البيانات 5 و5، من وسط الجسر. والوصل الأدنى يعطي 3 و7.
والسبب في التعريف لا في تفصيل تنفيذي. فالوصل الأدنى يدمج على أصغر مسافة، فتلتصق كل نقطة من الجسر واحدةً بعد أخرى بالكتلة المتنامية، وتجرّ السلسلة مجموعةً كاملة معها - أي عنقودًا متذيّلًا. أما الوصل الأقصى والمتوسّط فينظران إلى أكبر المسافات وإلى متوسّطها، فيأبيان دمج مجموعتين متباعدتين في جملتهما.
ويذكر جيمس وزملاؤه هذا بوصفه النمط العامّ: فالوصل الأدنى يميل إلى إنتاج عناقيد متذيّلة، بينما يعطي الأقصى والمتوسّط مخطّطات أكثر اتّزانًا. وللوصل المركزي عيب خاصّ به هو الانقلاب، إذ يندمج عنقودان عند ارتفاع أدنى من ارتفاع أحدهما، فتعسر قراءة الشجرة.
المزايا والعيوب
المزايا
- لا حاجة إلى الالتزام بعدد العناقيد قبل الملاءمة.
- مخطّط الشجرة ملخّص قابل للتأويل للبنية على كل المقاييس دفعةً واحدة.
- حتميّ: فبخلاف المتوسّطات K لا تهيئة عشوائيّة تُعاد منها التشغيلات.
- يعمل انطلاقًا من مصفوفة تباين وحدها، فينطبق حيثما وُجدت مسافة ذات معنًى.
العيوب
- يفرض هرميّةً متداخلة سواء أكانت في البيانات أم لا.
- اختيارا الوصل ومقياس التباين يغيّران النتيجة، ولا يمكن انتقاء أيٍّ منهما من البيانات.
- لا يُعاد النظر في دمج قطّ، فينتشر خطأ مبكّر إلى الشجرة كلّها.
- تنمو الكلفة سريعًا مع عدد المشاهدات، وهو ما يحدّ من استعمالها على البيانات الكبيرة.
الأسئلة الشائعة
كيف يُقرأ مخطّط الشجرة قراءةً صحيحة؟
بارتفاع الدمج وحده. فالمشاهدتان اللتان تندمجان في الأسفل متشابهتان، واللتان تندمجان قرب القمّة ليستا كذلك. والموضع الأفقي لا يحمل معلومةً البتّة - إذ يمكن إعادة ترتيب الأوراق بحرّية دون تغيير الشجرة، وقد لا تلتقي مشاهدتان متجاورتان إلا عند القمّة.
أي وصل ينبغي استعماله؟
الوصل الأقصى أو المتوسّط افتراضًا، لأنهما يعطيان مخطّطات متّزنة. ويُتجنَّب الوصل الأدنى ما لم يكن التسلسل هو ما تريد كشفه فعلًا، وقد ينتج الوصل المركزي انقلابات تجعل الشجرة غير مقروءة.
كيف يُختار عدد العناقيد؟
بتقرير موضع القطع، وهو حكم لا حساب. فلا خطأ محجوزًا يُتحقَّق في مقابله، والممارسة الأمينة أن تجرّب عدّة مجموعات معقولة من الاختيارات وتُبلّغ بالبنية التي تظهر في أغلبها.
الخلاصة
العنقدة الهرميّة تُغني عن تثبيت k سلفًا وتستبدل به الوصل ومقياس التباين وارتفاع القطع - ولا تستطيع البيانات اختيار أيٍّ منها عنك. فاقرأ التشابه من ارتفاعات الدمج وحدها، وفضّل الوصل الأقصى أو المتوسّط، وعامل الشجرة فرضيّةً عن البنية لا نتيجةً محقّقة.