التجميع الهرمي هو خوارزمية تعلم آلي غير خاضعة للإشراف تعمل على تجميع البيانات في مجموعات عنقودية متداخلة. تشمل الأنواع الرئيسية التجميع التراكمي (Agglomerative) والتجميع التقسيمي (Divisive). يساعد تحليل التجميع الهرمي في اكتشاف الأنماط والارتباطات داخل مجموعات البيانات. يتم عرض النتائج في مخطط شجرة عنقودية (Dendrogram) يُبرز العلاقات بين المجموعات بناءً على المسافات بينها.
التجميع هو تقنية تعلم آلي غير خاضعة للإشراف تُستخدم في تحليل البيانات لاكتشاف الكائنات المتشابهة وتجميعها. يعمل تحليل التجميع الهرمي (HCA)، أو التجميع الهرمي، على تنظيم الكائنات داخل تسلسل هرمي دون فرض ترتيب خطي عليها. تُستخدم طرق التجميع الهرمي في العديد من المجالات مثل علم الأحياء، وتحليل الصور، والعلوم الاجتماعية لاستكشاف الأنماط والتعرف عليها في مجموعات البيانات. تشمل حالات الاستخدام تصنيف السكان في الأبحاث السريرية، وتقسيم العملاء، واكتشاف مجتمعات العُقَد في نماذج الشبكات.
هناك نوعان من التجميع الهرمي:
التجميع التراكمي أو النهج التصاعدي1، وهو أسلوب يبدأ بدمج المجموعات العنقودية الصغيرة تدريجيًا في مجموعات أكبر حتى تتشكل مجموعة عنقودية واحدة شاملة.
التجميع التقسيمي (Divisive)، أو النهج التنازلي، حيث تبدأ جميع البيانات في مجموعة واحدة ثم تستمر في الانقسام إلى مجموعات متتالية حتى تصبح كل مجموعة مكونة من عنصر واحد فقط.2
يتطلب تحليل التجميع الهرمي قدرة حسابية عالية، مما يجعله مكلفًا من الناحية الحسابية. يمكن أن يساعد استخدام الكومة (Heap) في تقليل زمن المعالجة، لكنه يزيد من متطلبات الذاكرة. يتبع كل من التجميع التقسيمي والتجميع التراكمي نهجًا جشعًا، حيث تتخذ الخوارزمية قرارات الدمج أو التقسيم بناءً على أفضل اختيار محلي في كل مرحلة من العملية. يمكن أيضًا تحديد معيار توقف، بحيث تتوقف الخوارزمية عن الدمج أو التقسيم عند الوصول إلى عدد معين من المجموعات العنقودية وفقًا لمعيار محدد مسبقًا.
يُستخدم مخطط الشجرة العنقودية (Dendrogram)3، وهو مخطط شجري، في كثير من الأحيان لتمثيل التسلسل الهرمي للمجموعات العنقودية بصريًا. يُظهر هذا المخطط ترتيب عمليات الدمج أو التقسيم التي تمت بين المجموعات العنقودية، كما يوضح درجة التشابه أو المسافة بين نقاط البيانات. يمكن أيضًا فهم مخططات الشجرة العنقودية على أنها قوائم متداخلة4 تحتوي على خصائص تصف العلاقات بين البيانات.
تستخدم خوارزميات التجميع الهرمي مفهوم مصفوفة التباين لتحديد المجموعات التي يجب دمجها أو تقسيمها. تمثل التباينات المسافة بين نقطتي بيانات كما تُقاس باستخدام طريقة الربط المختارة. تعبر القيم الموجودة في مصفوفة التباين عن:
- المسافة5، مسافة إقليدية كمثال، بين نقاط فردية داخل مجموعة
- معيار تجميع الروابط، الذي يحدد التباين كدالة للمسافات الزوجية بين النقاط عبر المجموعات
دعنا نستكشف أكثر طرق الربط شيوعًا التي تعتمد على مسافة إقليدية. من بين مقاييس المسافة الأخرى التي يمكن استخدامها مسافة Minkowski و Hamming و Mahalanobis و Hausdorf و Manhattan. تجدر الإشارة إلى أن كل طريقة ربط تؤدي إلى تكوين مجموعات عنقودية مختلفة من نفس مجموعة البيانات. يعتمد اختيار طريقة التجميع المناسبة على عدة عوامل، مثل نوع البيانات التي يتم تجميعها، وكثافتها، وشكل المجموعة العنقودية، ووجود القيم الخارجية أو التشويش في مجموعة البيانات.
تقوم طريقة الربط الأحادي بتحليل المسافات الثنائية بين العناصر في مجموعتين، ثم تعتمد الحد الأدنى للمسافة بينهما. تتعامل هذه الطريقة بشكل جيد مع الأشكال غير الإهليلجية للمجموعات، لكنها تتأثر بالضوضاء والقيم الخارجية. تواجه هذه الطريقة تحديًا يُعرف باسم تأثير السلسلة6، حيث يمكن لنقاط قليلة تكوين جسر بين مجموعتين، مما يؤدي إلى دمجهما في مجموعة واحدة. يمكن تمثيل معايير الربط الأدنى على النحو التالي:
mina∈A,b∈Bd(a,b)
حيث تمثل A و B مجموعتين من الملاحظات و d هي دالة المسافة.
يمكن أيضًا حساب مسافات المجموعات بناءً على النقاط الأبعد عن بعضها البعض. تُعد طريقة الربط الأقصى أقل تأثرًا بالتشويش والقيم الخارجية مقارنةً بطريقة الربط الأدنى، ولكن استخدامها قد يؤدي إلى انحراف النتائج عند التعامل مع المجموعات غير الكروية أو الكبيرة. غالبًا ما تنتج طريقة الربط الأقصى مجموعات أكثر انتظامًا مقارنةً بطريقة الربط الأدنى. يمكن تمثيل معايير الربط الأقصى بالصيغة التالية:
maxa∈A,b∈Bd(a,b)
حيث تمثل A و B مجموعتين من الملاحظات و d هي المسافة.
تحدد هذه الطرق، التي قدمها Sokal و Michener7 ، المسافة بين المجموعات على أنها متوسط المسافة بين أزواج النقاط عبر جميع النقاط داخل المجموعات. يمكن أن تكون الخوارزمية إما طريقة المجموعة الزوجية غير الموزونة مع المتوسط الحسابي (UPGMA) أو طريقة المجموعة الزوجية الموزونة مع المتوسط الحسابي (WPGMA). تشير "غير الموزونة" هنا إلى أن جميع المسافات تساهم بالتساوي في كل متوسط
.يتم تمثيل UPGMA بالمعادلة التالية
1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)
حيث تمثل *A* و*B* مجموعتين من الملاحظات و*d* هي المسافة.
يمت متثيل WPGMA بالمعادلة التالية
d(i∪j,k)=d(i,k)+d(j,k)2
حيث i و j هما أقرب مجموعتين يتم دمجهما في كل خطوة لتشكيل مجموعة جديدة تضم اتحاد j و j. بعد ذلك، يمكننا حساب المسافة إلى مجموعة أخرى k، وهي المتوسط الحسابي لمتوسط المسافات بين نقاط البيانات في k و i و k و j.
هنا، نستخدم المسافة بين مراكز المجموعات أو النقاط المركزية. يتم حساب المسافة بين النقاط المركزية باستخدام دالة المسافة:
∥μA-μB∥2
حيث يمثل μA النقطة المركزية للمجموعة A و μB النقطة المركزية للمجموعة B.
قدم Joe H. Ward طريقة من زيادة مجموع المربعات (MISSQ) في الستينيات8. في هذه الطريقة، تبدأ كل نقطة بيانات في مجموعة مستقلة، مما يجعل مجموع المربعات بين نقاط البيانات يساوي صفرًا في البداية، ثم يزداد مع دمج المجموعات. تعمل طريقة وارد على تقليل مجموع المسافات المربعة بين النقاط والمراكز الهندسية للمجموعات أثناء عملية الدمج. تُعد طريقة Ward خيارًا جيدًا للمتغيرات الكمية، كما أنها أقل تأثرًا بالتشويش والقيم الخارجية في البيانات.9 يمكن تمثيل هذه الطريقة بالمعادلة التالية:
∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2
حيث يمثل متوسط A ومتوسط B النقاط المركزية لكل من المجموعتين A و B على التوالي، و x هي نقطة بيانات تنتمي إلى تحالف A و B
يمكن تحسين طريقة الحد الأدنى للتباين التي طرحها Ward من خلال استخدام خوارزمية Lance-Williams. تستخدم هذه الخوارزميات صيغة تكرارية لتحديث مسافات المجموعات والعثور على أقرب زوج من المجموعات لدمجهما.
في التجميع الهرمي التراكمي، المعروف أيضًا باسم التداخل التراكمي (Agglomerative)، تبدأ كل نقطة بيانات كمجموعة مستقلة. تستخدم الخوارزمية معيار ربط محدد يعتمد على مصفوفة التباين لتحديد أي زوج من المجموعات سيتم دمجه. تتحرك الخوارزمية صعودًا في التسلسل الهرمي وتستمر في دمج المجموعات حتى يتم ربط جميع النقاط معًا، مما يؤدي إلى إنشاء سلسلة هرمية من المجموعات المتداخلة. بشكل عام، تتضمن خطوات التجميع التراكمي ما يلي:10
1. احسب مصفوفة التباين باستخدام مقياس مسافة معينة
.2. قم بتخصيص كل نقطة بيانات لمجموعة معينة.
3. ادمج المجموعات بناءً على معيار الارتباط لتحديد التشابه بين المجموعات.
4. حدِّث مصفوفة المسافة.
5. كرر الخطوتين 3 و4 حتى تتبقى مجموعة عنقودية واحدة أو يتم استيفاء أي معيار إيقاف.
تم تطوير مبادئ التجميع التقسيمي (Divisive) على يد Macnaughton-Smith وزملاؤه11 في عام 1964، وتمت دراستها بشكل أعمق لاحقًا على يد Kaufman and Rousseeuw باستخدام خوارزمية DIANA (تحليل التجميع التقسيمي) في عام 1990.12 يستخدم التجميع التقسيمي نهجًا معاكسًا للتجميع التراكمي (Agglomerative)، حيث تبدأ جميع نقاط البيانات في مجموعة واحدة يتم تقسيمها تدريجيًا إلى مجموعات أصغر. تستمر عملية التقسيم حتى تصبح جميع المجموعات المتبقية أحادية العنصر أو يتم الوصول إلى معيار إيقاف مثل عدد محدد مسبقًا من المجموعات. تُعد الأساليب التقسيمية أكثر كفاءة في تحديد المجموعات الكبيرة13، كما يمكن أن تكون أكثر دقة من الأساليب التراكمية، حيث تأخذ الخوارزمية في الاعتبار توزيع مجموعة البيانات بالكامل منذ بداية العملية.
لتحسين الكفاءة، تستخدم طرق التجميع التقسيمي خوارزميات التجميع المسطح مثل تجميع K-means لتقسيم مجموعة البيانات إلى مجموعات. يجب تحديد عدد المجموعات مسبقًا. تقوم خوارزمية K-means بتقسيم المجموعات عن طريق تقليل مجموع التربيعات داخل المجموعات بين النقاط المركزية. يُعرف هذا المعيار باسم معيار القصور الذاتي.14 تشمل خطوات التجميع التقسيمي ما يلي:15
1. ابدأ بجميع نقاط البيانات لمجموعة بيانات بحجم N (d1، d2، d3 ... dN) داخل مجموعة واحدة.
2. قسّم المجموعة إلى مجموعتين غير متشابهتين أو غير متجانستين باستخدام طريقة التجميع المسطح مثل خوارزمية k-means
.3. كرر الخطوة 2، مع اختيار أفضل مجموعة لتقسيمها وإزالة القيمة الخارجية من المجموعة الأقل ترابطًا بعد كل تكرار.
4. توقف عندما تكون كل نقطة بيانات في مجموعة مستقلة، وإلا فكرر الخطوة 3.
يتم عرض نتائج التجميع عادةً في مخطط شجرة عنقودية (Dendrogram)، وهو بنية شجرية ثنائية. يمثل المحور x في المخطط نقاط البيانات، في حين يمثل المحور y أو ارتفاع الخطوط، مدى التباعد بين المجموعات عند دمجها.
يمكنك استخدام مخطط الشجرة العنقودية (Dendrogram) لتحديد عدد المجموعات في نموذج التجميع النهائي.16 إحدى الاستراتيجيات هي تحديد نقطة القطع الطبيعية في المخطط حيث تصبح الفروع أقل كثافة وأطول. بدلًا من ذلك، يمكن تحديد عدد المجموعات من خلال عدد الخطوط العمودية التي يتم قطعها عند رسم خط أفقي عبر المخطط.
في الصورة التوضيحية المعروضة هنا، يقطع الخط الأفقي H1 خطين عموديين. يشير ذلك إلى وجود مجموعتين عند هذه المرحلة من العملية—مجموعة تحتوي على النقاط 5 و8 و2، ومجموعة أخرى تضم باقي النقاط. كلما تمكن الخط الأفقي من التحرك لأعلى أو لأسفل دون قطع خطوط أفقية أخرى في مخطط الشجرة العنقودية، كان اختيار هذا العدد من المجموعات أكثر ملاءمة لنموذج التجميع الخاص بك. في المثال أدناه، يحدد الخط الأفقي H2 أربع مجموعات. لا يمكن للخط الأفقي H2 التحرك لأعلى ولأسفل بنفس مدى H1 قبل أن يقطع خطوطًا أفقية أخرى، مما يشير إلى أن خيار المجموعتين (H1) ربما يكون أكثر ملاءمة لنموذج التجميع الخاص بك.
يُنتج نموذج التجميع القوي مجموعات ذات تشابه داخلي عالٍ وتباين خارجي منخفض.17 ومع ذلك، قد يكون من الصعب تحديد جودة المجموعات، حيث يمكن أن يؤثر اختيار معيار الربط وعدد المجموعات بشكل كبير على النتائج. لذلك، عند بناء نموذج التجميع، جرب خيارات مختلفة واختر تلك التي تساعدك بشكل أفضل في استكشاف الأنماط داخل مجموعة البيانات لاستخدامها في المستقبل. تشمل العوامل التي يجب أخذها في الاعتبار ما يلي:18
- عدد المجموعات العملية أو المنطقية لمجموعة البيانات (بالنظر إلى حجم مجموعة البيانات وأشكال المجموعات والشويش في البيانات وما إلى ذلك)
- الإحصاءات، مثل المتوسط، والقيم القصوى والدنيا لكل مجموعة
أفضل مقياس لاختلاف التشابه أو معيار الارتباط الذي يجب تطبيقه.
- تأثير أي قيم خارجية أو متغيرات النتائج
أي معرفة محددة بالمجال أو مجموعة البيانات.
تشمل الطرق الأخرى التي تساعد في تحديد العدد الأمثل للمجموعات19 ما يلي:
طريقة الكوع (Elbow Method)، حيث يتم رسم مجموع المربعات داخل المجموعات العنقودية مقابل عدد المجموعات لتحديد نقطة الكوع، وهي النقطة التي يبدأ فيها الرسم البياني بالتسطّح، مما يشير إلى العدد الأمثل للعنقوديات.
- إحصائية الفجوة، حيث تقارن مجموع المربعات الفعلي داخل المجموعة بمجموع المربعات المتوقع داخل المجموعة العنقودية للتوزيع المرجعي الفارغ وفقًا لتوزيع مرجعي فارغ، ومن ثم تحديد أكبر فجوة للإشارة إلى العدد الأمثل للمجموعات العنقودية.
يوفر التجميع الهرمي لعلماء البيانات رؤى حول هيكلة البيانات والعلاقات بينها، كما يمكن تطبيقه في حالات استخدام متنوعة.
يمكن أن يساعد التجميع الهرمي في تحليل الاتجاهات وتقسيم بيانات العملاء—على سبيل المثال، من خلال تصنيفهم وفقًا لاختيار المنتجات، أو الخصائص الديموغرافية، أو سلوك الشراء، أو ملف المخاطر، أو التفاعلات مع وسائل التواصل الاجتماعي.
يمكن أن تضم مجموعات المرضى في الأبحاث السريرية آلاف الأفراد. يساعد التجميع الهرمي في تصنيف المجموعات المختلطة إلى مجموعات أكثر تجانسًا20 من خلال استخدام معايير مثل التشخيص الطبي، والاستجابات الفسيولوجية، أو الطفرات الجينية. كما يمكن تطبيقه لتصنيف الكائنات الحية بناءً على الخصائص البيولوجية لفهم التطور عبر الأجيال.
يُستخدم التجميع الهرمي في تطبيقات التعرف على النصوص المستندة إلى الصور لتجميع الأحرف المكتوبة يدويًا وفقًا لأشكالها. كما يُستخدم لتخزين المعلومات واسترجاعها بناءً على معايير محددة أو لتصنيف نتائج البحث.
تُستخدم كل من لغة Python ولغة R على نطاق واسع في علم البيانات. تتميز Python بمرونتها وقدرتها على التعامل مع مجموعة واسعة من المهام. من ناحية أخرى، تم تصميم R خصيصًا للحوسبة الإحصائية، حيث توفر خيارات غنية لتحليل التجميع الهرمي وتصور بياناته بفعالية.
توفر Python دالة AgglomerativeClustering21 (انظر أيضًا أمثلة التجميع التراكمي22 على sklearn)، وتوفر SciPy دالة لرسم المخططات الشجرية (Dendrograms)23. تعمل الحزم مثل dendextend24 على تعزيز وظائف المخططات الشجرية في R، مما يحسن تحليل الحساسية ويمكّنك من مقارنة المخططات الشجرية المختلفة والتعامل معها. للحصول على تجربة عملية، شاهد دروسنا التعليمية خطوة بخطوة: كيفية تنفيذ التجميع الهرمي في Python وكيفية تنفيذ التجميع الهرمي في R
1 Murtagh, F., Legendre, P., “Ward’s Hierarchical Agglomerative Clustering Method: Which Algorithms Implement Ward’s Criterion?,” 2014, J Classif 31, 274–295, https://link.springer.com/article/10.1007/s00357-014-9161-z
2 Kaufman, L.; Rousseeuw, P. J., Finding Groups in Data: An Introduction to Cluster Analysis. Wiley. Chp 6. Divisive Analysis (Program DIANA) pp. 253–279, https://onlinelibrary.wiley.com/doi/book/10.1002/9780470316801
3 Galili, T., “Introduction to dendextend,” The Comprehensive R Archive Network, 2023, https://cran.r-project.org/web/packages/dendextend/index.html
4 Lecture Notes from Penn State Eberly College of Science, “Hierarchical Clustering”, https://online.stat.psu.edu/stat555/node/85/
5, 17 Maimon, O., Rokach, L., Data Mining and Knowledge Discovery Handbook, 2010 2nd ed, Springer, https://link.springer.com/book/10.1007/978-0-387-09823-4
6 Sokal, R, Michener, C., “A statistical method for evaluating systematic relationships,” 1958, University of Kansas Science Bulletin, 38: 1409–1438, https://archive.org/details/cbarchive_33927_astatisticalmethodforevaluatin1902/page/n1/mode/2up
7 Ward, J. H., “Hierarchical Grouping to Optimize an Objective Function,” 1963, Journal of the American Statistical Association, 58 (301): 236–244, https://www.tandfonline.com/doi/abs/10.1080/01621459.1963.10500845.
8 Lecture Notes from Penn State Eberly College of Science, “Applied Multivariate Statistical Analysis”, https://online.stat.psu.edu/stat505/lesson/14/14.7
9, 15 Shetty P. and Singh S., “Hierarchical Clustering: A Survey,” International Journal of Applied Research, Vol 7 Issue 4, Part C, 2021, https://www.allresearchjournal.com/archives/?year=2021&vol=7&issue=4&part=C&ArticleId=8484
10 Macnaugton-Smith, P., Williams, W., Dale, M., et al., “Dissimilarity Analysis: a new Technique of Hierarchical Sub-division,” Nature 202, 1034–1035 (1964), https://www.nature.com/articles/2021034a0
12 Boehmke, B., Greenwell, B., Hands-On Machine Learning with R, Taylor and Francis, 2020, https://bradleyboehmke.github.io/HOML/
13 Cavalli-Sforza, L. L., and Edwards A. W. F., “Phylogenetic analysis: models and estimation procedures,” 1967, Evolution 21: 550–570 and Am. J. Hum. Genet. 19: 233–257, https://pmc.ncbi.nlm.nih.gov/articles/PMC1706274/
14 Sci-kit learn 1.3.2, 2.3 Clustering, https://scikit-learn.org/stable/modules/clustering.html
16 Lecture notes from MIT OpenCourseWare, 2017, https://ocw.mit.edu/courses/15-071-the-analytics-edge-spring-2017/pages/clustering/recommendations-worth-a-million-an-introduction-to-clustering/video-5-hierarchical-clustering/
18 Lecture notes from the University of Washington, 2001, https://courses.cs.washington.edu/courses/csep546/04au/pdf-slides/10.pdf
19 Boehmke, B., University of Cincinnati Business Analytics R Programming Guide, https://uc-r.github.io/hc_clustering#algorithms
20 QCBS R Workshop Series, https://r.qcbs.ca/workshop09/book-en/clustering.html
21 Zhongheng Zhang et al., “Hierarchical cluster analysis in clinical research with heterogeneous study population: highlighting its visualization with R,” Annals of Translational Medicine. 2017 Feb; 5(4): 75, https://atm.amegroups.org/article/view/13789/14063
22, 23 Scit-kit learn 1.3.2 documentation, https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html
24 SciPy Manual v1.11.4, https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.dendrogram.html