خوارزمية الاختزال التكراري BIRCH في التنقيب عن البيانات

إنّ (BIRCH) هي “الاختزال التكراري المتوازن والتكتل باستخدام التسلسلات الهرمية” عبارة عن خوارزمية عملية التنقيب عن البيانات غير الخاضعة للإشراف والتي تؤدي التجميع الهرمي على مجموعات البيانات الكبيرة، ومع التعديلات يمكن استخدامه أيضًا لتسريع تجميع الوسائل (k) ونمذجة خليط (Gaussian2).

مبدأ خوارزمية الاختزال التكراري BIRCH

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

تُعد خوارزميات التجميع الأساسية مثل خوارزميات (K) والتكتل العنقودي أكثر خوارزميات التجميع شيوعًا، ولكن عند إجراء التجميع على مجموعات بيانات كبيرة جدًا، فإنّ (BIRCH) و(DBSCAN) هما خوارزميات التجميع المتقدمة المفيدة لأداء التجميع الدقيق على مجموعات البيانات الكبيرة، وعلاوةً على ذلك يُعتبر (BIRCH) مفيدًا جدًا نظرًا لسهولة تنفيذه.

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

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

قيود خوارزمية الاختزال التكراري BIRCH

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

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

مراحل عمل خوارزمية الاختزال التكراري BIRCH

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

1- بناء شجرة CF

يلخص (BIRCH) مجموعات البيانات الكبيرة إلى مناطق أصغر كثيفة تسمى إدخالات ميزة (Clustering Feature)، كما يتم تعريف إدخال ميزة التجميع على أنه ثلاثي مرتب (N ، LS ، SS) حيث (N) هو عدد نقاط البيانات في المجموعة، و(LS) هو المجموع الخطي لنقاط البيانات و(SS) هو المجموع التربيعي لنقاط البيانات في العنقود، ويمكن أن يتكون إدخال (CF) من إدخالات (CF) أخرى، واختياريًا يمكن تكثيف شجرة (CF) الأولية هذه في (CF) أصغر.

2- التجميع الشامل

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

تم بناء هيكل الشجرة للبيانات المعطاة بواسطة خوارزمية (BIRCH) تسمى شجرة ميزة (Clustering) (شجرة CF)، حيث تعتمد هذه الخوارزمية على شجرة (CF) (ميزات التجميع)، وبالإضافة إلى ذلك تستخدم هذه الخوارزمية ملخصًا منظمًا على شكل شجرة لإنشاء مجموعات.

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

كذلك تديرها وتحتفظ بالمعلومات الضرورية للبيانات المعطاة لمزيد من المجموعات الهرمية وهذا يمنع الحاجة إلى العمل مع البيانات الكاملة المعطاة كمدخلات، كما يتم تمثيل المجموعة الشجرية لنقاط البيانات مثل (CF) بثلاثة أرقام (N ، LS ، SS)، وهناك أربع مراحل بشكل أساسي تتبعها خوارزمية (BIRCH):

• مسح البيانات في الذاكرة.

• تكثيف البيانات (تغيير حجم البيانات).

• التجميع العالمي.

• مجموعات التكرير.

اثنان منهم “تغيير حجم البيانات وتحسين المجموعات” اختياريان في هذه المراحل الأربع، وتأتي في العملية عندما يتطلب الأمر مزيدًا من الوضوح، ولكن مسح البيانات يشبه تمامًا تحميل البيانات في نموذج وبعد تحميل البيانات تقوم الخوارزمية بمسح البيانات بالكامل وتناسبها في أشجار (CF).

معلمات خوارزمية الاختزال التكراري BIRCH

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

• العتبة: الحد “العتبة” هو الحد الأقصى لعدد نقاط البيانات التي يمكن لمجموعة فرعية في العقدة الطرفية لشجرة (CF) الاحتفاظ بها.

• (Branching_factor): تحدد هذه المعلمة الحد الأقصى لعدد مجموعات (CF) الفرعية في كل عقدة (عقدة داخلية).

• (n_clusters): عدد المجموعات المراد إرجاعها بعد اكتمال خوارزمية (BIRCH) بأكملها أي عدد المجموعات بعد خطوة التجميع النهائية، ولا يتم تنفيذ خطوة التجميع النهائية إذا تم تعيينها إلى لا شيء ويتم إرجاع المجموعات الوسيطة.

مزايا خوارزمية الاختزال التكراري BIRCH

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

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

• تمثل (BIRCH) الاختزال التكراري المتوازن والتكتل باستخدام التسلسلات الهرمية، حيث إنّه مصمم لتجميع كمية هائلة من السجلات الرقمية عن طريق تكامل التجميع الهرمي وطرق التجميع الأخرى بما في ذلك التقسيم التكراري.

تقدم (BIRCH) مفهومين لميزة التجميع وشجرة ميزات التجميع (شجرة CF) والتي يتم استخدامها لتلخيص وصف المجموعة، كما تسهل هذه الهياكل طريقة التجميع لتحقيق أفضل سرعة وقابلية للتوسع في قواعد البيانات الضخمة، وكما أنّها تجعلها فعالة في التجميع المتزايد والديناميكي للكائنات الواردة.