Mining maximal high occupancy itemsets with a size-coupled upper bound

في المكتبات الشاسعة والصامتة للبيانات الحديثة، حيث تُسجل ملايين المعاملات في كل ثانية، سعى الباحثون منذ فترة طويلة لإيجاد وسيلة للعثور على المجموعات الأكثر دلالة من العناصر. تخيل سوبر ماركت يسجل كل عنصر يضعه العميل في عربته. تركز الأساليب التقليدية لتحليل هذه البيانات على التكرار: فهي تحصي عدد المرات التي يظهر فيها زوج معين من العناصر، مثل الخبز والزبدة، معاً. وإذا ظهر هذا الزوج بما يكفي من المرات، يتم تمييزه كنمط ذي دلالة. ومع ذلك، فإن هذا النهج يغفل تفصيلاً حاسماً حول سياق تلك المشتريات. فقد يظهر زوج من العناصر في آلاف المعاملات، ولكن إذا كانت تلك المعاملات عبارة عن طلبات ضخمة تحتوي على مئات المنتجات الأخرى، فإن هذا الزوج لا يمثل سوى جزء ضئيل جداً من الاهتمام الفعلي للعميل. ولحل هذه المشكلة، طور العلماء طريقة لا تقيس فقط عدد مرات ظهور العناصر معاً، بل تقيس أيضاً مدى الحيز الذي تشغله فعلياً في المعاملة. هذا المقياس، المسمى "الاستحواذ" (occupancy)، يحسب كسر إجمالي العناصر في المعاملة التي تغطيها مجموعة معينة. إنه يطرح سؤالاً مختلفاً: عندما تظهر هذه العناصر، هل تهيمن على السلة، أم أنها مجرد ملاحظة هامشية صغيرة في طلب أكبر بك much؟

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

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

ولمعالجة ذلك، صمم "فان" خوارزمية جديدة تسمى MHOI-Miner. فبدلاً من محاولة إدراج كل مجموعة ممكنة ثم تصفية المجموعات الصغيرة، بُنيت الخوارزمية لتطارد المجموعات الكبرى مباشرة. وهي تفعل ذلك باستخدام اختصار رياضي ذكي، أو "حد أعلى" (upper bound)، للتنبؤ بإمكانات المجموعة قبل اكتمال تكوينها. تخيل متنزهاً يحاول العثور على أعلى قمة في سلسلة جبال يغطيها الضباب. النهج القياسي سيكون تسلق كل تلة وقياس ارتفاعها، واستبعاد التلال المنخفضة في النهاية. أما طريقة "فان" فهي تشبه امتلاك خريطة تخبر المتنزه: "إذا سلكت هذا المسار المحدد، فإن أعلى ما يمكن أن تصل إليه سيكون أقل من القمة التي تبحث عنها بالفعل". وهذا يسمح للخوارزمية بالتوقف عن استكشاف ذلك المسار فوراً، مما يوفر كميات هائلة من الوقت وذاكرة الحاسوب.

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

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

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

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