تحديد المجهول باستخدام المقاييس العنقودية

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

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

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

فهم التجميع: مثال موجز

دعنا نحدد نموذجًا لمجموعة البيانات التي سنستخدمها لشرح مختلف مفاهيم التجميع المتري وفحص أنواع المجموعات التي قد تنتجها.

أولاً ، بعض الرموز والمصطلحات الشائعة:

• $ D $: مجموعة البيانات
• $ A $، $ B $: مجموعتان تشكلان مجموعات فرعية من مجموعة البيانات الخاصة بنا
• $ C $: مجموعة الحقيقة الأساسية لـ $ D $ التي سنقارن بين مجموعة أخرى
  • يحتوي تجميع $ C $ على مجموعات $ K $ ، $ C = {C_1،…، C_k} $
• $ C '$: مجموعة ثانية من $ D $
  • تجميع $ C '$ has $ K' $ clusters، $ C '= {C ^ \ prime_1،…، C ^ \ prime_ {k ^ \ prime}} $

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

للتمييز بين التجميع العام $ C $ ومجموعات الأمثلة لدينا ، سنستخدم حرفًا صغيرًا $ c $ لوصف أمثلة المجموعات لدينا:

• $ c $ ، مع المجموعات على أساس الشكل: $ c = {c_1، c_2} $ ، حيث يمثل $ c_1 $ البنطلون و $ c_2 $ يمثل القمصان
• $ c '$ ، مع المجموعات على أساس اللون: $ c' = {c'_1، c'_2} $ ، حيث يمثل $ c'_1 $ الملابس الحمراء و $ c'_2 $ يمثل الملابس السوداء
• $ c '' $ مع العناقيد على أساس الشكل واللون: $ c '' = {{c ^ {\ prime \ prime}} _ 1، {c ^ {\ prime \ prime}} _ 2، {c ^ {\ prime \ prime}} _ 3، {c ^ {\ prime \ prime}} _ 4} $ ، حيث $ {c ^ {\ prime \ prime}} _ 1 $ يمثل سراويل حمراء ، $ {c ^ {\ prime \ prime}} _ 2 يمثل $ بنطلون أسود ، ويمثل $ {c ^ {\ prime \ prime}} _ 3 دولارات قمصانًا حمراء ، و {c ^ {\ prime \ prime}} _ 4 دولارات قمصانًا سوداء

قد تتضمن المجموعات الإضافية أكثر من أربع مجموعات بناءً على ميزات مختلفة ، مثل ما إذا كان القميص بلا أكمام أو بدون أكمام.

كما رأينا في مثالنا ، تقسم طريقة التجميع جميع العينات في مجموعة بيانات إلى مجموعات فرعية منفصلة غير فارغة. في المجموعة $ c $ ، لا توجد صورة تنتمي إلى كل من مجموعة البنطلونات الفرعية ومجموعة القمصان الفرعية: $ c_1 \ cap c_2 = \ emptyset $. يمكن تمديد هذا المفهوم ؛ لا توجد مجموعتان فرعيتان من أي مجموعة لها نفس العينة.

نظرة عامة على تجميع مقاييس المقارنة

يمكن وصف معظم معايير مقارنة المجموعات باستخدام مصفوفة الارتباك للزوج $ C ، C '$. ستكون مصفوفة الارتباك عبارة عن مصفوفة $ K \ مرات K '$ التي يكون عنصرها $ kk' $ th (العنصر الموجود في الصف $ k $ th والعمود $ k '$ th) هو عدد العينات في تقاطع المجموعات $ C_k $ من $ C $ و $ C '_ {k'} $ من $ C '$:

\ [n_ {kk '} = | C_k \ cap C' _ {k '} | \]

سنقوم بتفصيل ذلك باستخدام مثالنا المبسط للسراويل والقمصان السوداء والحمراء ، بافتراض أن مجموعة البيانات $ D $ بها 100 بنطلون أحمر ، و 200 بنطلون أسود ، و 200 قميص أحمر ، و 300 قميص أسود. لنفحص مصفوفة الارتباك لـ $ c $ و $ c '' $:

بما أن $ K = 2 $ و $ K '' = 4 $ ، فهذه مصفوفة $ 2 \ مرات 4 $. لنختار $ k = 2 $ و $ k '' = 3 $. نرى هذا العنصر $ n_ {kk '} = n_ {23} = 200 دولار. هذا يعني أن تقاطع $ c_2 $ (قمصان) و $ {c ^ {\ prime \ prime}} _ 3 $ (قمصان حمراء) هو 200 ، وهذا صحيح منذ $ c_2 \ cap {c ^ {\ prime \ prime} } _3 $ سيكون ببساطة مجموعة القمصان الحمراء.

يمكن تصنيف المقاييس العنقودية على نطاق واسع إلى ثلاث مجموعات بناءً على طريقة مقارنة المجموعة الأساسية:

في هذه المقالة ، نتطرق فقط إلى عدد قليل من المقاييس العديدة المتاحة ، ولكن أمثلةنا ستساعد في تحديد مجموعات المقاييس الثلاث.

العد الزوجي

يتطلب عد الأزواج فحص جميع أزواج العينات ، ثم عد الأزواج حيث تتفق المجموعات وتختلف. يمكن أن ينتمي كل زوج من العينات إلى واحدة من أربع مجموعات ، حيث يتم الحصول على عدد عناصر المجموعة ($ N_ {ij} $) من مصفوفة الارتباك:

• $ S_ {11} $ ، مع $ N_ {11} $ element: عناصر الزوج موجودة في نفس المجموعة تحت كل من $ C $ و $ C '$
  • سيكون زوج من القمصان الحمراء أقل من $ S_ {11} $ عند المقارنة بين $ c $ و $ c '' $
• $ S_ {00} $ ، مع $ N_ {00} $ element: عناصر الزوج موجودة في مجموعات مختلفة تحت كل من $ C $ و $ C '$
  • سيكون زوج من القميص الأحمر والسراويل السوداء أقل من $ S_ {00} $ عند المقارنة بين $ c $ و $ c '' $
• $ S_ {10} $ ، مع $ N_ {10} $ element: عناصر الزوج موجودة في نفس المجموعة في $ C $ ومجموعات مختلفة في $ C '$
  • سيكون زوج من القميص الأحمر والقميص الأسود أقل من $ S_ {10} $ عند المقارنة بين $ c $ و $ c '' $
• $ S_ {01} $ ، مع $ N_ {01} $ element: عناصر الزوج موجودة في مجموعات مختلفة في $ C $ ونفس المجموعة في $ C '$
  • لا يحتوي $ S_ {01} $ على عناصر ($ N_ {01} = 0 $) عند مقارنة $ c $ و $ c '' $

يتم تعريف فهرس Rand على أنه $ (N_ {00} + N_ {11}) / (n (n-1) / 2) $ ، حيث يمثل $ n $ عدد العينات ؛ يمكن قراءتها أيضًا على أنها (عدد الأزواج المعالجة بالمثل) / (إجمالي عدد الأزواج). على الرغم من أن قيمته تتراوح نظريًا بين 0 و 1 ، إلا أن نطاقه غالبًا ما يكون أضيق كثيرًا من الناحية العملية. تعني القيمة الأعلى تشابهًا أكبر بين المجموعات. (قد يمثل فهرس راند 1 تطابقًا تامًا حيث تحتوي مجموعتان على مجموعات متطابقة.)

يتمثل أحد قيود مؤشر Rand في سلوكه عندما يزداد عدد المجموعات ليقترب من عدد العناصر ؛ في هذه الحالة ، يتقارب باتجاه 1 ، مما يخلق تحديات في قياس التشابه العنقودي بدقة. تم تقديم العديد من الإصدارات المحسنة أو المعدلة من فهرس Rand لمعالجة هذه المشكلة. أحد الاختلافات هو مؤشر Rand المعدل ؛ ومع ذلك ، فإنه يفترض أن مجموعتين يتم رسمهما بشكل عشوائي مع عدد ثابت من العناقيد والعناصر العنقودية.

نظرية المعلومات

تستند هذه المقاييس على المفاهيم العامة لنظرية المعلومات. سنناقش اثنين منهم: الانتروبيا والمعلومات المتبادلة (MI).

يصف الانتروبيا مقدار المعلومات الموجودة في التجمع. إذا كانت الانتروبيا المرتبطة بالتجمع تساوي 0 ، فلا يوجد عدم يقين بشأن مجموعة عينة منتقاة عشوائيًا ، وهذا صحيح عندما يكون هناك عنقود واحد فقط.

يصف MI مقدار المعلومات التي تعطيها إحدى المجموعات عن الأخرى. يمكن أن يشير MI إلى مقدار معرفة مجموعة العينة في $ C $ يقلل من عدم اليقين حول مجموعة العينة في $ C '$.

المعلومات المتبادلة المطابقة هي MI التي يتم تطبيعها بواسطة المتوسط ​​الهندسي أو الحسابي لانتروبيا التجمعات. لا يرتبط معيار MI بقيمة ثابتة ، لذا فإن المعلومات المتبادلة الموحدة توفر مقياس تجميع أكثر قابلية للتفسير.

مقياس شائع آخر في هذه الفئة هو تباين المعلومات (VI) الذي يعتمد على كل من الانتروبيا و MI للتجمعات. لنفترض أن $ H (C) $ هو إنتروبيا عنقود و $ I (C، C ') $ هو MI بين مجموعتين. يمكن تعريف VI بين مجموعتين على أنه $ VI (C، C ') = H (C) + H (C') - 2I (C، C ') $. يمثل VI من 0 تطابقًا مثاليًا بين مجموعتين.

تعيين التداخل

تتضمن مقاييس التداخل المحددة تحديد أفضل تطابق للمجموعات في $ C $ مع المجموعات في $ C '$ بناءً على الحد الأقصى من التداخل بين المجموعات. بالنسبة لجميع المقاييس في هذه الفئة ، يعني الرقم 1 أن المجموعات متطابقة.

يقوم مقياس المطابقة الأقصى بمسح مصفوفة الارتباك بترتيب تنازلي ويتطابق مع أكبر إدخال لمصفوفة الارتباك أولاً. ثم يزيل المجموعات المتطابقة ويكرر العملية بالتتابع حتى يتم استنفاد المجموعات.

مقياس F هو مقياس تداخل مجموعة آخر. على عكس الحد الأقصى لمقياس المطابقة ، يتم استخدام مقياس F بشكل متكرر لمقارنة التجميع بالحل الأمثل ، بدلاً من مقارنة مجموعتين.

تطبيق المقاييس العنقودية مع مقياس F.

نظرًا للاستخدام الشائع لـ F-Measure في نماذج التعلم الآلي والتطبيقات المهمة مثل محركات البحث ، سنستكشف مقياس F بمزيد من التفاصيل مع مثال.

تعريف قياس F

لنفترض أن $ C $ هو الحقيقة الأساسية أو الحل الأمثل. لأي مجموعة $ k $ th في $ C $ ، حيث $ k \ in [1، K] $ ، سنحسب مقياس F فرديًا مع كل مجموعة في نتيجة التجميع $ C '$. يشير مقياس F الفردي هذا إلى مدى جودة وصف العنقود $ C ^ \ prime_ {k '} $ للمجموعة $ C_k $ ويمكن تحديده من خلال الدقة والاسترجاع (مقياسان لتقييم النموذج) لهذه المجموعات. لنعرّف $ I_ {kk '} $ على أنه تقاطع العناصر في مجموعة $ C $' s $ k $ th ومجموعة $ C '$' s $ k '$ th ، و $ \ lvert C_k \ rvert $ كرقم من العناصر في مجموعة $ k $ th.

• الدقة $ p = \ frac {I_ {kk '}} {\ lvert C' _ {k '} \ rvert} $

  

• استدعاء $ r = \ frac {I_ {kk '}} {\ lvert C_ {k} \ rvert} $

بعد ذلك ، يمكن حساب مقياس F الفردي للمجموعة $ k $ th و $ k '$ th على أنه المتوسط ​​التوافقي للدقة والاستدعاء لهذه المجموعات:

\ [F_ {kk '} = \ frac {2rp} {r + p} = \ frac {2I_ {kk'}} {| C_k | + | C '_ {k'} |} \]

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

\ [F (C، C ') = \ frac {1} {n} \ sum_ {i = 1} ^ K n_imax (F (C_i، C'_j)) \ forall j \ in {1، K'} \ ]

كما ترى ، فإن مقياس F الإجمالي هو المجموع المرجح لمقاييس F الفردية الخاصة بنا للتجمعات.

إعداد البيانات والنتائج المتوقعة

أي كمبيوتر محمول Python مناسب للتعلم الآلي ، مثل دفتر Jupyter ، سيعمل كبيئتنا. قبل أن نبدأ ، قد ترغب في فحص README لمستودع GitHub الخاص بي ، وملف المثال readme_help_example.ipynb الممتد ، وملف requirements.txt (المكتبات المطلوبة).

سنستخدم البيانات النموذجية في مستودع GitHub ، والذي يتكون من مقالات إخبارية. يتم ترتيب البيانات مع المعلومات بما في ذلك category headline date short_description :

يمكننا استخدام الباندا لقراءة البيانات وتحليلها ومعالجتها. سنقوم بفرز البيانات حسب التاريخ وتحديد عينة صغيرة (10000 عنوان إخباري) لعرضنا التوضيحي نظرًا لأن مجموعة البيانات الكاملة كبيرة:

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

عند التشغيل ، سترى نتيجة دفتر الملاحظات 30 ، نظرًا لوجود 30 فئة في عينة البيانات هذه. يمكنك أيضًا تشغيل df.head(4) لمعرفة كيفية تخزين البيانات. (يجب أن يتطابق مع الجدول المعروض في هذا القسم.)

تحسين ميزات التجميع

قبل تطبيق التجميع ، يجب علينا أولاً معالجة النص مسبقًا لتقليل الميزات الزائدة في نموذجنا ، بما في ذلك:

• تحديث النص ليكون له حالة موحدة.
• إزالة الأحرف الرقمية أو الخاصة.
• أداء اللماتة.
• إزالة كلمات التوقف.

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

يتم عرض العناوين الرئيسية الناتجة المعالجة مسبقًا على أنها processed_input ، والتي يمكنك ملاحظتها عن طريق تشغيل df.head(4) :

الآن ، نحتاج إلى تمثيل كل عنوان كمتجه رقمي حتى نتمكن من تطبيق أي نموذج للتعلم الآلي عليه. هناك العديد من تقنيات استخراج الميزات لتحقيق ذلك ؛ سنستخدم TF-IDF (مصطلح تردد الوثيقة العكسي). تقلل هذه التقنية من تأثير الكلمات التي تحدث بكثرة في المستندات (في مثالنا ، عناوين الأخبار) ، حيث من الواضح أنه لا ينبغي أن تكون هذه هي السمات الحاسمة في تجميعها أو تصنيفها.

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

بعد ذلك ، سوف نجرب أول طريقة للتجميع لدينا ، التجميع التراكمي ، على متجهات السمات هذه.

طريقة التجميع 1: التجميع التكتلي

بالنظر إلى فئات الأخبار المعينة باعتبارها الحل الأمثل ، دعنا نقارن هذه النتائج بتلك الخاصة بالتكتل العنقودي (مع العدد المطلوب من المجموعات مثل 30 نظرًا لوجود 30 فئة في مجموعة البيانات):

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

سوف نحدد المجموعات الناتجة عن طريق تسميات عدد صحيح ؛ العناوين التي تنتمي إلى نفس المجموعة يتم تعيين نفس تصنيف العدد الصحيح. ترجع وظيفة cluster_measure من الوحدة النمطية compare_clusters بين المجموعات في مستودع جيثب لدينا مقياس F الكلي وعدد المجموعات المتطابقة تمامًا حتى نتمكن من معرفة مدى دقة نتيجة التجميع لدينا:

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

عند مقارنة نتائج هذه المجموعة مع الحل الأمثل ، نحصل على مقياس F منخفض يبلغ 0.198 و 0 عنقود تتطابق مع مجموعات الفصل الفعلية ، مما يوضح أن المجموعات التراكمية لا تتوافق مع الفئات الرئيسية التي اخترناها. دعنا نتحقق من الكتلة في النتيجة لنرى كيف تبدو.

 df[df['class_prd'] == 0]['category'].value_counts()

عند فحص النتائج ، نرى أن هذه المجموعة تحتوي على عناوين رئيسية من جميع الفئات:

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

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

طريقة التجميع 2: K- يعني

دعنا نجرب خوارزمية تجميع أخرى شائعة على نفس مجموعة البيانات: k-mean clustering. سننشئ إطار بيانات جديدًا ونستخدم وظيفة cluster_measure مرة أخرى:

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

مثل نتيجة التجميع التراكمي ، شكلت نتيجة التجميع k-mean لدينا مجموعات تختلف عن الفئات المعطاة لدينا: لديها مقياس F يبلغ 0.18 عند مقارنتها بالحل الأمثل. نظرًا لأن نتيجتي التجميع لهما مقاييس F متشابهة ، سيكون من المثير للاهتمام مقارنتها ببعضها البعض. لدينا بالفعل التجمعات ، لذلك نحتاج فقط إلى حساب مقياس F. أولاً ، سنقوم بإحضار كلتا النتيجتين في عمود واحد ، مع وجود class_gt لإخراج التجميع التجميعي ، و class_prd بها ناتج التجميع k-mean:

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

باستخدام مقياس F أعلى يبلغ 0.4 ، يمكننا أن نلاحظ أن مجموعات الخوارزميتين أكثر تشابهًا مع بعضها البعض مقارنة بالحل الأمثل.

اكتشف المزيد حول نتائج المجموعات المحسّنة

سيؤدي فهم مقاييس مقارنة المجموعات المتاحة إلى توسيع نطاق تحليل نموذج التعلم الآلي الخاص بك. لقد رأينا مقياس F-clustering قيد التنفيذ ، وقدمنا ​​لك الأساسيات التي تحتاجها لتطبيق هذه المعارف على نتيجة التجميع التالية. لمعرفة المزيد ، إليك أفضل اختياراتي لمزيد من القراءة:

• مقارنة المجموعات - نظرة عامة بقلم دوروثيا واغنر وسيلك واغنر
• مقارنة المجموعات - مسافة تستند إلى المعلومات بواسطة مارينا ميلا
• المقاييس النظرية للمعلومات لمقارنة المجموعات: المتغيرات والخصائص والتطبيع والتصحيح للفرصة بواسطة نجوين شوان فينه وجوليان إيبس وجيمس بيلي

---

مزيد من القراءة على مدونة Toptal Engineering:

• علم بيانات الرسم البياني باستخدام Python / NetworkX
• تصنيف صور شبه خاضع للإشراف مع بيانات غير مصنفة
• التضمينات في التعلم الآلي: تبسيط البيانات المعقدة

تعرب مدونة Toptal Engineering عن امتنانها لـ Luis Bronchal لمراجعة نماذج التعليمات البرمجية المقدمة في هذه المقالة.