البتولا

جزء من سلسلة عن
التعلم الآلي واستخراج البيانات
النماذج التعلم تحت الإشراف التعلم غير الخاضع للإشراف التعلم شبه الخاضع للإشراف التعلم الذاتي التعلم التعزيزي التعلم الفوقي التعلم عبر الإنترنت التعلم الدفعي التعلم المنهجي التعلم المبني على القواعد الذكاء الاصطناعي الرمزي العصبي الهندسة العصبية Quantum machine learning
Problems Classification Generative modeling Regression Clustering Dimensionality reduction Density estimation Anomaly detection Data cleaning AutoML Association rules Semantic analysis Structured prediction Feature engineering Feature learning Learning to rank Grammar induction Ontology learning Multimodal learning
Supervised learning (classification • regression) Apprenticeship learning Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Fuzzy Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE SDL
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection RANSAC k-NN Local outlier factor Isolation forest
Artificial neural network Autoencoder Deep learning Feedforward neural network Recurrent neural network LSTM GRU ESN reservoir computing Boltzmann machine Restricted GAN Diffusion model SOM Convolutional neural network U-Net LeNet AlexNet DeepDream Neural radiance field Transformer Vision Mamba Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning SARSA Temporal difference (TD) Multi-agent Self-play
Learning with humans Active learning Crowdsourcing Human-in-the-loop RLHF
Model diagnostics Coefficient of determination Confusion matrix Learning curve ROC curve
Mathematical foundations Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Journals and conferences ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Related articles Glossary of artificial intelligence List of datasets for machine-learning research List of datasets in computer vision and image processing Outline of machine learning
v t e

BIRCH ( التخفيض التكراري المتوازن والتجميع باستخدام التسلسلات الهرمية ) هي خوارزمية لتعدين البيانات غير خاضعة للإشراف تُستخدم لإجراء التجميع الهرمي على مجموعات بيانات كبيرة بشكل خاص. ^[1] مع التعديلات، يمكن أيضًا استخدامها لتسريع التجميع باستخدام طريقة k-means ونمذجة الخليط الغاوسي باستخدام خوارزمية التوقع والتعظيم . ^[2] تتمثل إحدى مزايا BIRCH في قدرتها على تجميع نقاط البيانات المترية متعددة الأبعاد الواردة بشكل تدريجي وديناميكي في محاولة لإنتاج أفضل تجميع عالي الجودة لمجموعة معينة من الموارد ( قيود الذاكرة والوقت ). في معظم الحالات، يتطلب BIRCH مسحًا واحدًا فقط لقاعدة البيانات.

يزعم مخترعو BIRCH أنها "أول خوارزمية تجميع مقترحة في مجال قاعدة البيانات للتعامل مع "الضوضاء" (نقاط البيانات التي لا تشكل جزءًا من النمط الأساسي) بشكل فعال"، ^[1] متفوقة على DBSCAN بشهرين. حصلت خوارزمية BIRCH على جائزة SIGMOD لاختبار الزمن لمدة 10 سنوات في عام 2006. ^[3]

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

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

تأخذ خوارزمية BIRCH كمدخلات مجموعة من نقاط البيانات N ، ممثلة كمتجهات ذات قيمة حقيقية ، وعددًا مرغوبًا من المجموعات K. وهي تعمل في أربع مراحل، المرحلة الثانية منها اختيارية.

تقوم المرحلة الأولى ببناء شجرة ميزات التجميع ( ) من نقاط البيانات، وهي عبارة عن بنية بيانات شجرة متوازنة الارتفاع ، يتم تعريفها على النحو التالي: ${\displaystyle CF}$

• بالنظر إلى مجموعة من نقاط البيانات ذات الأبعاد N، يتم تعريف ميزة التجميع للمجموعة على أنها ثلاثية ، حيث ${\displaystyle CF}$${\displaystyle CF=(N,{\overrightarrow {LS}},SS)}$
  • ${\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}$هو المجموع الخطي.
  • ${\displaystyle SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}}$هو المجموع المربع لنقاط البيانات.
• يتم تنظيم ميزات التجميع في شجرة CF ، وهي شجرة متوازنة الارتفاع مع معاملين: ^{[ يحتاج إلى توضيح ]} عامل التفرع والعتبة . تحتوي كل عقدة غير ورقية على إدخالات على الأكثر من النموذج ، حيث هو مؤشر إلى عقدة الطفل رقم th وميزة التجميع التي تمثل المجموعة الفرعية المرتبطة. تحتوي العقدة الورقية على إدخالات على الأكثر لكل من النموذج . كما أن لديها مؤشرين prev و next والتي تستخدم لتسلسل جميع العقد الورقية معًا. يعتمد حجم الشجرة على المعلمة . يلزم أن تتناسب العقدة مع صفحة بحجم . ويتم تحديدها بواسطة . لذلك يمكن تغييرها لضبط الأداء . إنه تمثيل مضغوط للغاية لمجموعة البيانات لأن كل إدخال في عقدة ورقية ليس نقطة بيانات واحدة ولكنه مجموعة فرعية.${\displaystyle B}$${\displaystyle T}$${\displaystyle B}$${\displaystyle [CF_{i},child_{i}]}$${\displaystyle child_{i}}$${\displaystyle i}$${\displaystyle CF_{i}}$${\displaystyle L}$${\displaystyle [CF_{i}]}$${\displaystyle T}$${\displaystyle P}$${\displaystyle B}$${\displaystyle L}$${\displaystyle P}$${\displaystyle P}$

في الخطوة الثانية، تقوم الخوارزمية بمسح جميع إدخالات الأوراق في الشجرة الأولية لإعادة بناء شجرة أصغر، مع إزالة القيم المتطرفة وتجميع المجموعات الفرعية المزدحمة في مجموعات أكبر. تم وضع علامة على هذه الخطوة على أنها اختيارية في العرض الأصلي لـ BIRCH. ${\displaystyle CF}$${\displaystyle CF}$

في الخطوة الثالثة، يتم استخدام خوارزمية تجميع موجودة لتجميع جميع إدخالات الأوراق. هنا يتم تطبيق خوارزمية تجميع هرمية تراكمية مباشرة على المجموعات الفرعية الممثلة بمتجهاتها . كما توفر المرونة للسماح للمستخدم بتحديد إما العدد المطلوب من المجموعات أو عتبة القطر المطلوبة للمجموعات. بعد هذه الخطوة، يتم الحصول على مجموعة من المجموعات التي تلتقط نمط التوزيع الرئيسي في البيانات. ومع ذلك، قد توجد أخطاء طفيفة ومحلية يمكن التعامل معها من خلال الخطوة الاختيارية 4. في الخطوة 4، يتم استخدام نقاط مركز المجموعات المنتجة في الخطوة 3 كبذور وإعادة توزيع نقاط البيانات إلى أقرب بذور لها للحصول على مجموعة جديدة من المجموعات. توفر لنا الخطوة 4 أيضًا خيار تجاهل القيم المتطرفة. أي نقطة بعيدة جدًا عن أقرب بذرة لها يمكن التعامل معها كقيمة متطرفة. ${\displaystyle CF}$

This section is missing information about BIRCH equations for Diameter D, Distances D0, D1, D3 and D4. Please expand the section to include this information. Further details may exist on the talk page. (July 2023)

بالاعتماد فقط على ميزة التجميع ، يمكن حساب نفس القياسات دون معرفة القيم الفعلية الأساسية. ${\displaystyle CF=[N,{\overrightarrow {LS}},SS]}$

• مركز الثقل:${\displaystyle {\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}}$
• نصف القطر:${\displaystyle R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}}$
• متوسط ​​مسافة الارتباط بين المجموعات و :${\displaystyle CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]}$${\displaystyle CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]}$${\displaystyle D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}}$

في الحالات متعددة الأبعاد، يجب استبدال الجذر التربيعي بقاعدة مناسبة.

يستخدم BIRCH المسافات DO إلى D3 للعثور على أقرب ورقة، ثم يستخدم نصف القطر R أو القطر D ليقرر ما إذا كان سيتم امتصاص البيانات في الورقة الموجودة أو ما إذا كان سيتم إضافة ورقة جديدة.

لسوء الحظ، هناك قضايا عددية مرتبطة باستخدام المصطلح في BIRCH. عند الطرح أو ما شابه ذلك في المسافات الأخرى مثل ، يمكن أن يحدث إلغاء كارثي ويؤدي إلى دقة ضعيفة، وقد يتسبب ذلك في بعض الحالات في أن تكون النتيجة سلبية (ثم يصبح الجذر التربيعي غير محدد). ^[2] يمكن حل ذلك باستخدام ميزات مجموعة BETULA بدلاً من ذلك، والتي تخزن العدد والمتوسط ​​ومجموع الانحرافات التربيعية بدلاً من ذلك بناءً على خوارزميات عبر الإنترنت أكثر موثوقية عدديًا لحساب التباين . بالنسبة لهذه الميزات، تنطبق نظرية الجمع المماثلة. عند تخزين متجه أو مصفوفة للانحرافات التربيعية، يمكن أيضًا استخدام شجرة BIRCH CF الناتجة لتسريع نمذجة الخليط الغوسي باستخدام خوارزمية التوقع والتعظيم ، بالإضافة إلى التجميع باستخدام متوسطات k والتجميع التراكمي الهرمي . ${\displaystyle SS}$${\displaystyle {\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}}$${\displaystyle D_{2}}$${\displaystyle CF=(N,\mu ,S)}$${\displaystyle N}$${\displaystyle \mu }$

بدلاً من تخزين المجموع الخطي ومجموع المربعات، يمكننا بدلاً من ذلك تخزين المتوسط ​​والانحراف التربيعي عن المتوسط ​​في كل سمة من سمات المجموعة ، ^[4] حيث ${\displaystyle CF'=(N,\mu ,S)}$

• ${\displaystyle n}$هو وزن العقدة (عدد النقاط)
• ${\displaystyle \mu }$هو متجه مركز العقدة (المتوسط ​​الحسابي، مركز الثقل)
• ${\displaystyle S}$هو مجموع الانحرافات التربيعية عن المتوسط ​​(إما متجهًا أو مجموعًا للحفاظ على الذاكرة، اعتمادًا على التطبيق)

الفرق الرئيسي هنا هو أن S يتم حسابها بالنسبة للمركز، وليس بالنسبة للأصل.

يمكن تحويل نقطة واحدة إلى ميزة مجموعة . ولدمج ميزتين من ميزات المجموعة ، نستخدم ${\displaystyle x}$${\displaystyle CF_{x}=(1,x,0)}$${\displaystyle CF_{AB}=CF_{A}+CF_{B}}$

• ${\displaystyle N_{AB}=N_{A}+N_{B}}$
• ${\displaystyle \mu _{AB}=\mu _{A}+{\frac {N_{B}}{N_{AB}}}(\mu _{B}-\mu _{A})}$(تحديث تدريجي للمتوسط)
• ${\displaystyle S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})\circ (\mu _{B}-\mu _{AB})}$في شكل متجه باستخدام حاصل الضرب لكل عنصر على حدة، على التوالي
• ${\displaystyle S_{AB}=S_{A}+S_{B}+N_{B}(\mu _{B}-\mu _{A})^{T}(\mu _{B}-\mu _{AB})}$لتحديث مجموع قياسي للانحرافات التربيعية

تستخدم هذه الحسابات حسابات أكثر موثوقية عدديًا (راجع الحساب عبر الإنترنت للتباين ) والتي تتجنب طرح قيمتين مربعتين متشابهتين. مركز الثقل هو ببساطة متجه مركز العقدة ، ويمكن استخدامه مباشرة لحسابات المسافة باستخدام، على سبيل المثال، المسافات الإقليدية أو مانهاتن. يبسط نصف القطر إلى والقطر إلى . ${\displaystyle \mu }$${\displaystyle R={\sqrt {{\frac {1}{N}}S}}}$${\displaystyle D={\sqrt {{\frac {2}{N-1}}S}}}$

يمكننا الآن حساب المسافات المختلفة من D0 إلى D4 المستخدمة في خوارزمية BIRCH على النحو التالي: ^[4]

• يتم حساب المسافة الإقليدية ومسافة مانهاتن باستخدام مراكز CF${\displaystyle D_{0}=\|\mu _{A}-\mu _{B}\|}$${\displaystyle D_{1}=\|\mu _{A}-\mu _{B}\|_{1}}$${\displaystyle \mu }$
• المسافة بين المجموعات${\displaystyle D_{2}={\sqrt {{\frac {1}{N_{A}}}S_{A}+{\frac {1}{N_{B}}}S_{B}+{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}}$
• المسافة داخل المجموعة${\displaystyle D_{3}={\sqrt {{\frac {2}{N_{AB}(N_{AB}-1)}}\left(N_{AB}(S_{A}+S_{B})+N_{A}N_{B}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}\right)}}}$
• التباين - زيادة المسافة${\displaystyle D_{4}={\sqrt {{\frac {N_{A}N_{B}}{N_{AB}}}{\big \|}\mu _{A}-\mu _{B}{\big \|}^{2}}}}$

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

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

1. التجميع باستخدام طريقة k-means ، حيث يتم ترجيح الأوراق حسب عدد النقاط، N.
2. k-means++ ، عن طريق أخذ عينات من ميزات المجموعة بشكل متناسب مع حيث أن هي المراكز المختارة مسبقًا، و هي ميزة مجموعة BETULA.${\displaystyle S+N\min _{i}||\mu -c_{i}||}$${\displaystyle c_{i}}$${\displaystyle (N,\mu ,S)}$
3. نمذجة الخليط الغاوسي ، حيث يمكن أيضًا أخذ التباين S في الاعتبار، وإذا كانت الأوراق تخزن التباينات أيضًا.
4. التجميع التراكمي الهرمي ، حيث يمكن تهيئة الارتباط باستخدام التكافؤ التالي للارتباطات لمسافات BIRCH: ^[5]

المراسلات بين ارتباطات HAC ومسافات BIRCH ^[5]

ربط HAC	مسافة البتولا
اتحاد الجامعات الأمريكية	د2²
WPGMA	د0²
جناح	2 د4²

• يحتوي ELKI على خشب البتولا والبيتولا.
• يحتوي scikit-learn على إصدار محدود من BIRCH، والذي يدعم فقط مسافة D0، والعتبات الثابتة، والذي يستخدم فقط نقاط مركز الأوراق في خطوة التجميع. ^[6]