أساسيات تعلم الآلة2008مبتدئ10 دقيقة قراءة

غابة العَزْل

Isolation Forest

Liu, F. T. · Ting, K. M. · Zhou, Z.-H. — ICDM

المشكلة

الطرق التقليدية لكشف الشذوذ تعتمد على فكرة واحدة: افهم أولاً كيف تبدو البيانات «العادية»، ثم أيّ شيء لا يشبهها أعلِن عنه. المشكلة أن هذا النهج فيه ثغرتان أساسيتان. الثغرة الأولى: الكاشف يصرف كل جهده في تعلُّم الحالة الطبيعية بدل أن يركّز على الشاذّ نفسه، فتكثر الإنذارات الخاطئة أو تمرّ شواذّ حقيقية دون رصد. الثغرة الثانية: التكلفة الحسابية. حسابات المسافة والكثافة تتطلب مقارنات زوجية تنمو بشكل تربيعي، فحين تتعامل مع بيانات ضخمة أو عالية الأبعاد يصبح الكشف الفوري — كرصد الاحتيال أو اختراقات الشبكات — غير ممكن عملياً.

الإسهام

فكرة مختلفة جذرياً: بدل أن تسأل «كيف تبدو البيانات العادية؟»، اسأل «كم هو سهل أن أعزل هذه النقطة؟». (iForest) تبني مجموعة أشجار ثنائية عشوائية (iTrees)، كل شجرة تأخذ عيّنة صغيرة وتقسّمها بشكل متكرر باختيار سمة عشوائية ونقطة فصل عشوائية. النقاط الشاذّة — لأنها قليلة ومختلفة عن الأغلبية — تنعزل بسرعة بعدد قليل من التقسيمات، فيكون مسارها من جذر الشجرة إلى الورقة قصيراً. أما درجة الشذوذ فتُحسب بتسوية متوسط مقارنةً بما نتوقعه من شجرة بحث ثنائية عادية. المحصّلة: تعمل بتعقيد زمني خطّي واستهلاك ذاكرة ضئيل، وتتفوّق على الكواشف المبنية على المسافة والكثافة، خاصةً مع البيانات الكبيرة.

الأثر

صارت غابة العَزْل الخيار التلقائي لكشف الشذوذ بدون إشراف في مكتبة scikit-learn وفي خطوط الإنتاج الصناعية. الفكرة المحورية — أن الشاذّ سهل العَزْل بدل أن يكون صعب التوصيف — فتحت الباب أمام امتدادات مثل غابة العَزْل الموسَّعة وSCiForest وغابات القطع العشوائي للتعامل مع البيانات المتدفقة. تُستخدم اليوم على نطاق واسع في كشف الاحتيال والأمن السيبراني ومراقبة جودة التصنيع والتشخيص الطبي، وتجاوزت 5,000 اقتباس مما يجعلها من أكثر أوراق تأثيراً.

تخيّل فناء مدرسة مليء بالأطفال، وطُلب منك أن تجد الشخص الذي لا ينتمي لهذا المكان — مثلاً شخص بالغ دخل بالخطأ. الطريقة المعتادة هي أن تفحص كل طفل وتبني صورة ذهنية عن «الطفل الطبيعي»، ثم تبحث عمّن لا يطابق هذه الصورة. عملية مُرهقة وبطيئة.

غابة العَزْل تعكس السؤال تماماً: لا تدرس الجميع، فقط حاول أن تعزل أيّ شخص. ارسم أسواراً عشوائية في الفناء. الشخص البالغ — أطول، بملابس مختلفة، يقف بعيداً — ينعزل من أول سور أو اثنين. لكن لو أردت عزل طفل محدّد من وسط المجموعة، ستحتاج أسواراً كثيرة لأنهم كلهم متشابهون ومتقاربون.

القاعدة بسيطة: كلما احتجت أسواراً أقل لعزل شيء ما، كان أكثر شذوذاً.

المشكلة: توصيف الحالة الطبيعية مُكلِف وغير مباشر

حتى عام 2008، كانت الفكرة السائدة في واحدة: افهم البيانات الطبيعية أولاً، ثم أيّ شيء يخرج عنها يُعدّ شاذاً. أساليب مثل DBSCAN وعامل الشذوذ المحلي (LOF) والكواشف المبنية على المسافة كلها اتّبعت هذا المنطق. لكن هذا النهج يعاني من مشكلتين جوهريتين:

يتعلّم الشيء الخطأ. الكاشف يبذل جهده في فهم الحالة الطبيعية، لا في تمييز الشاذّ. فحين تكون الحدود بين الطبيعي والشاذّ غير واضحة، إمّا يُغرقك بإنذارات كاذبة لأنه يُعلِّم كل ما هو غير مألوف قليلاً (ظاهرة الإغراق — swamping)، أو تفلت منه شواذّ حقيقية لأنها تتخفّى وسط مجموعة متشابهة (ظاهرة التقنُّع — masking).
التكلفة الحسابية باهظة. حسابات المسافة والكثافة تتطلب مقارنات زوجية بتعقيد $O(n^2)$ . كمثال عملي: على مجموعة بيانات من 500,000 حزمة شبكية، احتاج كاشف ORCA أكثر من 9,000 ثانية. بهذه السرعة، الكشف الفوري أمر مستحيل عملياً.

آلية العَزْل: تقسيمات عشوائية على سمات عشوائية

فكرة شجرة العَزْل (iTree) بسيطة: خذ عيّنة فرعية صغيرة من بياناتك (عادةً 256 نقطة). اختر عشوائياً، ثم اختر قيمة فصل عشوائية بين حدَّيها الأدنى والأعلى. النقاط تحت قيمة الفصل تذهب يساراً، والباقي يذهب يميناً. كرّر هذه العملية بشكل تعاودي حتى تنعزل كل نقطة في ورقتها — أو حتى تصل إلى الحدّ الأقصى لعمق الشجرة.

الناتج شجرة ثنائية، وطول المسار لكل نقطة — أي عدد الحواف من الجذر إلى ورقتها — يكشف لك مدى سهولة عزلها. النقطة الشاذّة التي تقع بعيداً عن التجمّع الرئيسي بقيم غير مألوفة تنفصل بسرعة: مسارها قصير. أمّا النقطة الطبيعية المحاطة بنقاط مشابهة في كثيف، فتحتاج تقسيمات كثيرة قبل أن تنفرد: مسارها طويل.

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

افتح في المختبر

انقر «بناء الشجرة» وشاهد كيف تعزل التقسيمات العشوائية النقطة الشاذّة (الحمراء) بسرعة، بينما النقاط الطبيعية (الزرقاء) تحتاج تقسيمات أكثر بكثير.

تستيقظ التجربة عند وصولك…

الخوارزمية: مرحلتا التدريب والتقييم

الخوارزمية لا تحتاج إلّا : عدد الأشجار $t$ (تلقائياً 100) وحجم العيّنة الفرعية $\psi$ (تلقائياً 256). وتعمل على مرحلتين واضحتين:

مرحلة : لكل شجرة من الأشجار الـ $t$ ، اسحب $\psi$ نقطة عشوائياً بدون إرجاع. ضع حدّاً أقصى لعمق الشجرة عند $l = \lceil \log_2 \psi \rceil$ . ثم ابنِ شجرة العَزْل بتكرار الخطوة التالية: اختر سمة عشوائية $q$ ، واختر نقطة فصل عشوائية $p$ بين أصغر وأكبر قيمة لهذه السمة في المجموعة الحالية. النقاط التي تحقّق $q < p$ تذهب يساراً والباقي يميناً. تتوقف العملية حين تبقى نقطة واحدة في ، أو تتطابق جميع النقاط، أو يُبلَغ حدّ العمق.

مرحلة التقييم: مرِّر كل نقطة اختبار عبر كل شجرة واحسب عدد الحواف من الجذر إلى الورقة التي تصل إليها — هذا هو $h(x)$ . إذا وصلت النقطة إلى عقدة خارجية لا تزال تحتوي عدة نقاط (لأن الشجرة بلغت حدّ العمق قبل عزلها)، أضف تعديلاً $c(\text{Size})$ يُقدّر العمق الإضافي الذي كانت الشجرة ستحتاجه. بعد ذلك، خذ متوسط $h(x)$ على جميع الأشجار للحصول على $E[h(x)]$ ، واحسب منه درجة الشذوذ.

افتح في المختبر

تابع المرحلتين خطوة بخطوة: كيف تُبنى الأشجار من العيّنات الفرعية، وكيف تُحسب أطوال المسارات ودرجات الشذوذ.

تستيقظ التجربة عند وصولك…

درجة الشذوذ: من طول المسار إلى رقم بين 0 و1

أطوال المسارات الخام لا تصلح للمقارنة مباشرةً بين مجموعات بيانات بأحجام مختلفة. مسار بطول 8 في عيّنة من 256 نقطة لا يعني الشيء نفسه في عيّنة من 1024 نقطة. إذاً نحتاج مرجعاً نُسوّي على أساسه.

هنا تأتي ملاحظة ذكية: بنية شجرة العَزْل تشبه تماماً بنية (BST). الوصول إلى ورقة خارجية في شجرة العَزْل يُعادل بحثاً فاشلاً في شجرة بحث ثنائية. لذا يمكننا استخدام الصيغة المعروفة لمتوسط طول المسار في بحث BST فاشل كخط أساس لعملية .

c(n) = 2H(n-1) - \frac{2(n-1)}{n}

متوسط طول المسار لبحث فاشل في شجرة بحث ثنائية — خط الأساس للتسوية — H(i) هو العدد التوافقي، ويُقرَّب بـ ln(i) + 0.5772 (ثابت أويلر). الدالة c(n) تنمو بمعدّل O(log n)، فتعطينا مرجعاً لطول المسار لا يتأثر بحجم البيانات.

بعد أن حصلنا على هذا المرجع، يمكننا تعريف درجة الشذوذ $s$ لأي نقطة $x$ بالصيغة التالية:

s(x, n) = 2^{-\frac{E[h(x)]}{c(n)}}

درجة الشذوذ في غابة العَزْل — E[h(x)] هو متوسط طول المسار عبر جميع الأشجار. حين يكون E[h(x)] قريباً من الصفر، تقترب الدرجة من 1 — أي شذوذ شبه مؤكّد. وحين يساوي c(n) تقريباً، تكون الدرجة 0.5 — لا إشارة واضحة في أيّ اتجاه. وحين يقترب من n−1، تنخفض الدرجة نحو الصفر — نقطة طبيعية بلا شك.

تخيّل هذه الدرجة كـمؤشر غرابة: كلما اقتربت من 1 زاد احتمال أن النقطة شاذّة. عند 0.5 المؤشر في وضع الحياد — لا دليل في أيّ اتجاه. وكلما انخفضت الدرجة عن 0.5 ازداد اطمئنانك بأن النقطة طبيعية.

افتح في المختبر

حرّك المنزلق لتغيير متوسط طول المسار ولاحظ كيف تتغير درجة الشذوذ. انتبه أن 0.5 هي نقطة الحياد: لا دليل على شذوذ ولا على طبيعية.

تستيقظ التجربة عند وصولك…

لماذا تساعد العيّنة الفرعية: بيانات أقل، كشف أفضل

هذه ربما أكثر خصائص غابة العَزْل إثارةً للدهشة. في أغلب أساليب نعتقد أن بيانات أكثر تعني نتائج أفضل. لكن هنا العكس صحيح: أخذ عيّنة فرعية صغيرة يُحسّن الكشف فعلاً. كيف ذلك؟

حين تستخدم كل البيانات، تتكدّس النقاط الطبيعية حول الشواذّ وتُصعّب عزلها — وهذا ما يُسمى بظاهرة الإغراق (swamping). كذلك قد تندمج تجمّعات الشواذّ مع تجمّعات النقاط الطبيعية فتتقنّع وتختفي (masking). لكن حين تأخذ عيّنة صغيرة من 256 نقطة فقط، يخفّ الازدحام: النقاط الطبيعية المحيطة بالشواذّ تتبدّد، وتجمّعات الشواذّ تنكمش إلى حفنة واضحة يسهل تمييزها.

النتائج العملية مثيرة: على مجموعة بيانات Mulcross (4096 نقطة)، أعطى استخدام كل البيانات = 0.67 فقط. لكن مع عيّنة فرعية من 128 نقطة قفزت القيمة إلى 0.91. بيانات أقل أعطت كشفاً أفضل بكثير.

افتح في المختبر

بدّل بين العيّنة الكاملة والعيّنة الفرعية الصغيرة ولاحظ كيف تبرز الشواذّ بوضوح حين يقلّ الازدحام حولها.

تستيقظ التجربة عند وصولك…

الخوارزمية في شيفرة برمجية

غابة العَزْل — تطبيق كاملpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np

def c(n):
    """متوسط طول المسار لبحث فاشل في شجرة بحث ثنائية (المُسوِّي)."""
    if n <= 1: return 0
    if n == 2: return 1
    H = np.log(n - 1) + 0.5772156649   # تقريب العدد التوافقي
    return 2 * H - 2 * (n - 1) / n

class ITree:
    """شجرة عَزْل واحدة: قسّم تعاودياً حتى الانعزال."""
    def __init__(self, X, height=0, limit=8):
        self.n = len(X)
        if height >= limit or self.n <= 1:
            self.is_leaf = True
        else:
            self.is_leaf = False
            q = np.random.randint(X.shape[1])       # سمة عشوائية
            lo, hi = X[:, q].min(), X[:, q].max()
            self.split_val = np.random.uniform(lo, hi)
            self.split_att = q
            left_mask = X[:, q] < self.split_val
            self.left  = ITree(X[left_mask],  height + 1, limit)
            self.right = ITree(X[~left_mask], height + 1, limit)

    def path_length(self, x, e=0):
        if self.is_leaf:
            return e + c(self.n)            # تعديل للشجرة الفرعية غير المبنية
        if x[self.split_att] < self.split_val:
            return self.left.path_length(x, e + 1)
        return self.right.path_length(x, e + 1)

def iforest_scores(X, t=100, psi=256):
    """ابنِ t شجرة من عيّنات فرعية بحجم psi وأعِد درجات الشذوذ."""
    trees = []
    limit = int(np.ceil(np.log2(psi)))
    for _ in range(t):
        idx = np.random.choice(len(X), size=min(psi, len(X)), replace=False)
        trees.append(ITree(X[idx], limit=limit))

    scores = np.zeros(len(X))
    for i, x in enumerate(X):
        avg_h = np.mean([tree.path_length(x) for tree in trees])
        scores[i] = 2 ** (-avg_h / c(psi))   # درجة الشذوذ
    return scores

# الاستخدام: درجات قريبة من 1 ← شذوذ، قريبة من 0.5 ← طبيعي

الأداء والكفاءة

تعقيد التدريب هو $O(t\psi \log \psi)$ ، وتعقيد التقييم $O(nt \log \psi)$ حيث $n$ حجم بيانات الاختبار. وبما أن $\psi$ و $t$ ثوابت صغيرة (256 و100)، فالمرحلتان عملياً خطّيتان في $n$ .

لتوضيح الفارق العملي: على مجموعة بيانات Http التي تحتوي 567,497 سجلاً، أنهت غابة العَزْل العمل في 15.6 ثانية فقط — بينما احتاج كاشف ORCA إلى 9,487 ثانية. هذا فرق بمعامل 600 ضعف. والأهم أن الدقة لم تتراجع: غابة العَزْل حققت AUC = 1.00 مقابل 0.36 فقط لـORCA.

استهلاك الذاكرة اقتصادي بالقدر نفسه. مع $\psi = 256$ تحتوي كل شجرة على 511 عقدة كحدّ أقصى، و100 شجرة تعني أن النموذج بأكمله يتسع في بضع مئات من الكيلوبايت — حجم يناسب الأنظمة المدمجة أو وكلاء المراقبة الفورية.

افتح في المختبر

قارن بين غابة العَزْل وORCA وLOF من حيث AUC ووقت التشغيل على مجموعات بيانات مرجعية مختلفة. لاحظ كيف تتّسع الفجوة كلما كبرت البيانات.

تستيقظ التجربة عند وصولك…

تقارب سريع: بضع أشجار تكفي

من أجمل الخصائص العملية لغابة العَزْل أن أداءها يستقر بسرعة. أظهرت الورقة أن AUC يتقارب قبل الوصول إلى $t = 100$ شجرة في جميع مجموعات البيانات المُختبَرة. وكذلك الأمر مع حجم العيّنة الفرعية: الأداء شبه مثالي عند $\psi = 256$ ، وهو رقم ضئيل جداً مقارنةً بالبيانات الأصلية (أقل من 0.05% في مجموعة من 500 ألف نقطة). زيادة $\psi$ فوق 256 لا تُضيف شيئاً سوى وقت معالجة إضافي.

الخلاصة العملية: يمكنك الاعتماد على القيم التلقائية (100 شجرة وعيّنة بحجم 256) دون الحاجة لضبط دقيق. هذه متانة نادرة في عالم التعلُّم الآلي حيث ضبط المعاملات الفائقة يستهلك عادةً وقتاً وجهداً كبيرين.

العَزْل مقابل التوصيف: تحوّل جوهري

الكواشف التقليدية مثل LOF وORCA وDBSCAN تبني أولاً تصوّراً عن البيانات الطبيعية ثم تقيس مدى انحراف كل نقطة عنه. هذا يتطلّب حساب مسافات أو كثافات بين كل الأزواج — تعقيد $O(n^2)$ . غابة العَزْل لا تحسب أي أصلاً. هي تستخدم تقسيمات عشوائية — بتكلفة $O(\log n)$ لكل نقطة في كل شجرة — وتسأل سؤالاً أبسط بكثير: «كم تقسيمة أحتاج لعزل هذه النقطة؟»

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

افتح في المختبر

على اليسار: غابة العَزْل تعزل النقطة الشاذّة ببضع تقسيمات عشوائية. على اليمين: أسلوب المسافة يحتاج حساب المسافة إلى كل نقطة أخرى.

تستيقظ التجربة عند وصولك…

لماذا أحدثت فرقاً

2008
غابة العَزْل (iForest)
الورقة الأصلية التي طرحت فكرة كشف الشذوذ عبر العَزْل، بتعقيد زمني خطّي واعتماد على عيّنات فرعية صغيرة. نُشرت في مؤتمر ICDM.
2010
SCiForest
طوّرت غابة العَزْل لتتعامل مع الشواذّ المتجمّعة في عناقيد، وذلك باستخدام تقسيمات بمستويات مائلة بدلاً من التقسيمات المحاذية للمحاور.
2012
كشف الشذوذ القائم على العَزْل (TKDD)
النسخة الموسَّعة للورقة في شكل مقالة دورية، مع تحليل نظري أعمق وتجارب إضافية. نُشرت في دورية ACM TKDD.
2018
غابة العَزْل الموسَّعة (EIF)
استبدلت التقسيمات المحاذية للمحاور بتقسيمات عبر مستويات عشوائية، مما أزال العناقيد الوهمية والتحيّزات التي كانت تظهر في خرائط درجة الشذوذ.
2020
غابة القطع العشوائي (للتدفق)
أمازون أخذت فكرة العَزْل وكيّفتها للعمل مع البيانات المتدفقة، مما أتاح كشف الشذوذ لحظياً في خدمات AWS مثل Kinesis Analytics.

المرجعLiu, Ting, Zhou. Isolation Forest. ICDM, 2008.

مصطلحات هذه الورقة

كشف الشذوذAnomaly Detection
غابة العَزْلIsolation Forest
رصد القيم الشاذةOutlier Detection
شجرة القرار الإحصائيةDecision Tree
الغابة العشوائية خوارزميةRandom Forest
شجرة البحث الثنائيةBinary Search Tree
طول المسارPath Length
التقليص المكانيsubsampling
النماذج التجميعية الهجينةEnsemble
التعلّم غير الخاضع للإشرافUnsupervised Learning