DBSCAN עם Scikit-Learn ב- Python

מבוא

אתה עובד בחברת ייעוץ כמדען נתונים. הפרויקט שאליו הוקצת כעת מכיל נתונים מסטודנטים שסיימו לאחרונה קורסים בנושאי כספים. החברה הפיננסית שמעבירה את הקורסים רוצה להבין האם ישנם גורמים משותפים המשפיעים על התלמידים לרכוש את אותם קורסים או לרכוש קורסים שונים. על ידי הבנת הגורמים הללו, החברה יכולה ליצור פרופיל סטודנט, לסווג כל סטודנט לפי פרופיל ולהמליץ ​​על רשימת קורסים.

בעת בדיקת נתונים מקבוצות סטודנטים שונות, נתקלת בשלוש נטיות של נקודות, כמו ב-1, 2 ו-3 להלן:

שימו לב שבחלקה 1, ישנן נקודות סגולות מאורגנות בחצי עיגול, עם מסה של נקודות ורודות בתוך העיגול הזה, מעט ריכוז של נקודות כתומות מחוץ לחצי עיגול זה, וחמש נקודות אפורות שרחוקות מכל השאר.

בחלקה 2 יש מסה עגולה של נקודות סגולות, עוד אחת של נקודות כתומות, וגם ארבע נקודות אפורות רחוקות מכל השאר.

ובחלקה 3, אנו יכולים לראות ארבעה ריכוזים של נקודות, סגול, כחול, כתום, ורוד, ועוד שלוש נקודות אפורות מרוחקות.

עכשיו, אם הייתם בוחרים במודל שיוכל להבין נתוני תלמידים חדשים ולקבוע קבוצות דומות, האם יש אלגוריתם מקבץ שיכול לתת תוצאות מעניינות לסוג זה של נתונים?

כשתיארנו את העלילות, הזכרנו מונחים כמו מסה של נקודות ו ריכוז נקודות, המציין שיש אזורים בכל הגרפים עם צפיפות גדולה יותר. התייחסנו גם ל חוזר ו חצי עגול צורות, שקשה לזהות על ידי ציור קו ישר או רק בחינת הנקודות הקרובות ביותר. בנוסף, יש כמה נקודות מרוחקות שסביר להניח שיחרגו מהתפלגות הנתונים העיקרית, מה שמציג יותר אתגרים או רעש בעת קביעת הקבוצות.

אלגוריתם מבוסס צפיפות שיכול לסנן רעשים, כגון DBSCAN (Dאחדות-Bכמו Sפטריאלי Cברק של Aהשלכות עם Noise), היא בחירה חזקה למצבים עם אזורים צפופים יותר, צורות מעוגלות ורעש.

על DBSCAN

DBSCAN הוא אחד האלגוריתמים המצוטטים ביותר במחקר, הפרסום הראשון שלו מופיע ב-1996, זה נייר DBSCAN מקורי. במאמר, החוקרים מדגימים כיצד האלגוריתם יכול לזהות אשכולות מרחביים לא ליניאריים ולטפל ביעילות בנתונים בעלי ממדים גבוהים יותר.

הרעיון המרכזי מאחורי DBSCAN הוא שיש מספר מינימלי של נקודות שיהיו במרחק מוגדר או רַדִיוּס מנקודת האשכול ה"מרכזית" ביותר, הנקראת נקודת ליבה. הנקודות ברדיוס זה הן נקודות השכונה, והנקודות בקצה השכונה הן הנקודות נקודות גבול or נקודות גבול. הרדיוס או מרחק השכונה נקרא שכונת אפסילון, ε-שכונה או רק ε (הסמל לאות יוונית אפסילון).

בנוסף, כאשר ישנן נקודות שאינן נקודות ליבה או נקודות גבול מכיוון שהן חורגות מהרדיוס עבור השתייכות לאשכול שנקבע וגם אין להן את המספר המינימלי של נקודות להיות נקודת ליבה, הן נחשבות נקודות רעש.

זה אומר שיש לנו שלושה סוגים שונים של נקודות, כלומר, הליבה, גבול ו רעש. יתרה מזאת, חשוב לציין שהרעיון העיקרי מבוסס ביסודו על רדיוס או מרחק, מה שהופך את DBSCAN – כמו רוב המודלים המקבצים – תלוי במדד המרחק הזה. מדד זה יכול להיות אוקלידי, מנהטן, מהלנוביס ועוד רבים. לכן, חיוני לבחור מדד מרחק מתאים שמתחשב בהקשר של הנתונים. לדוגמה, אם אתה משתמש בנתוני מרחק נסיעה מ-GPS, זה עשוי להיות מעניין להשתמש במדד שלוקח את פריסות הרחוב בחשבון, כגון מרחק מנהטן.

כדי למצוא את נקודת הליבה, DBSCAN יבחר תחילה נקודה באופן אקראי, ימפה את כל הנקודות בתוך ה-ε-שכונת שלה, וישווה את מספר השכנים של הנקודה שנבחרה למספר המינימלי של נקודות. אם לנקודה שנבחרה יש מספר שווה או יותר שכנים ממספר הנקודות המינימלי, היא תסומן כנקודת ליבה. נקודת ליבה זו ונקודות השכנות שלה יהוו את האשכול הראשון.

לאחר מכן, האלגוריתם יבחן כל נקודה של האשכול הראשון ויראה אם ​​יש לה מספר שווה או יותר נקודות שכנות ממספר הנקודות המינימלי בתוך ε. אם כן, הנקודות השכנות הללו יתווספו גם לאשכול הראשון. תהליך זה יימשך עד שלנקודות של האשכול הראשון יהיו פחות שכנים ממספר הנקודות המינימלי בתוך ε. כאשר זה קורה, האלגוריתם מפסיק להוסיף נקודות לאותו אשכול, מזהה נקודת ליבה נוספת מחוץ לאותו אשכול ויוצר אשכול חדש עבור אותה נקודת ליבה חדשה.

לאחר מכן DBSCAN יחזור על תהליך האשכול הראשון של מציאת כל הנקודות המחוברות לנקודת ליבה חדשה של האשכול השני עד שלא יהיו עוד נקודות להוסיף לאותו אשכול. לאחר מכן הוא יתקל בנקודת ליבה נוספת ויצור אשכול שלישי, או שהוא יחזור על כל הנקודות שלא הסתכל עליהן בעבר. אם נקודות אלו נמצאות במרחק ε מאשכול, הן מתווספות לאותו אשכול, והופכות לנקודות גבול. אם הם לא, הם נחשבים לנקודות רעש.

מעניין לדעת איך האלגוריתם DBSCAN עובד, אם כי, למרבה המזל, אין צורך לקודד את האלגוריתם, ברגע שלספריית Scikit-Learn של Python כבר יש מימוש.

בואו נראה איך זה עובד בפועל!

ייבוא ​​נתונים לאשכולות

כדי לראות איך DBSCAN עובד בפועל, נשנה מעט פרויקטים ונשתמש במערך נתונים קטן של לקוחות שיש לו את הז'אנר, הגיל, ההכנסה השנתית וההוצאות של 200 לקוחות.

ציון ההוצאות נע בין 0 ל-100 ומייצג את התדירות שבה אדם מוציא כסף בקניון בסולם מ-1 עד 100. במילים אחרות, אם ללקוח יש ציון 0, הוא אף פעם לא מוציא כסף, ואם הציון הוא 100, הם המוציאים הגבוהים ביותר.

לאחר הורדת מערך הנתונים, תראה שזהו קובץ CSV (ערכים מופרדים בפסיקים) שנקרא shopping-data.csv, נטען אותו ל-DataFrame באמצעות Pandas ונשמור אותו ב- customer_data מִשְׁתַנֶה:

import pandas as pd path_to_file = '../../datasets/dbscan/dbscan-with-python-and-scikit-learn-shopping-data.csv'
customer_data = pd.read_csv(path_to_file)

כדי להסתכל על חמש השורות הראשונות של הנתונים שלנו, אתה יכול לבצע customer_data.head():

זו התוצאה:

 CustomerID Genre Age Annual Income (k$) Spending Score (1-100)
0 1 Male 19 15 39
1 2 Male 21 15 81
2 3 Female 20 16 6
3 4 Female 23 16 77
4 5 Female 31 17 40

על ידי בחינת הנתונים, נוכל לראות מספרי זיהוי של לקוחות, ז'אנר, גיל, הכנסות ב-k$ וציוני הוצאות. זכור שחלק מהמשתנים הללו או כולם ישמשו במודל. למשל, אם היינו משתמשים Age ו Spending Score (1-100) כמשתנים עבור DBSCAN, המשתמש במדד מרחק, חשוב להביא אותם לסולם משותף כדי להימנע מהכנסת עיוותים שכן Age נמדד בשנים ו Spending Score (1-100) יש טווח מוגבל מ-0 עד 100. זה אומר שנבצע איזשהו קנה מידה של נתונים.

אנו יכולים גם לבדוק אם הנתונים זקוקים לעיבוד מוקדם נוסף מלבד קנה המידה על ידי בדיקה אם סוג הנתונים עקבי ולוודא אם ישנם ערכים חסרים שיש לטפל בהם על ידי ביצוע של Panda info() שיטה:

customer_data.info()

זה מציג:

<class 'pandas.core.frame.DataFrame'>
RangeIndex: 200 entries, 0 to 199
Data columns (total 5 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 CustomerID 200 non-null int64 1 Genre 200 non-null object 2 Age 200 non-null int64 3 Annual Income (k$) 200 non-null int64 4 Spending Score (1-100) 200 non-null int64 dtypes: int64(4), object(1)
memory usage: 7.9+ KB

אנו יכולים לראות שאין ערכים חסרים מכיוון שיש 200 ערכים שאינם אפסיים עבור כל תכונת לקוח. אנו יכולים גם לראות שרק בעמודת הז'אנר יש תוכן טקסט, מכיוון שהוא משתנה קטגורי, שמוצג כ object, וכל שאר התכונות הן מספריות, מהסוג int64. לפיכך, מבחינת עקביות סוגי הנתונים והיעדר ערכי אפס, הנתונים שלנו מוכנים לניתוח נוסף.

נוכל להמשיך להמחיש את הנתונים ולקבוע אילו תכונות יהיו מעניינות להשתמש ב-DBSCAN. לאחר בחירת התכונות הללו, נוכל להגדיל אותן.

מערך נתונים זה של לקוחות זהה לזה המשמש במדריך הסופי שלנו לאשכולות היררכית. כדי ללמוד עוד על נתונים אלה, כיצד לחקור אותם, ועל מדדי מרחק, אתה יכול להסתכל על מדריך סופי לאשכולות היררכית עם Python ו-Skit-Learn!

הדמיה של נתונים

באמצעות Seaborn's pairplot(), נוכל לשרטט גרף פיזור עבור כל שילוב של תכונות. מאז CustomerID הוא רק זיהוי ולא תכונה, נסיר אותו עם drop() לפני התכנון:

import seaborn as sns customer_data = customer_data.drop('CustomerID', axis=1) sns.pairplot(customer_data);

תפוקות אלה:

כאשר מסתכלים על שילוב התכונות המיוצר על ידי pairplot, הגרף של Annual Income (k$) עם Spending Score (1-100) נראה שמציג בסביבות 5 קבוצות של נקודות. נראה שזה השילוב המבטיח ביותר של תכונות. אנחנו יכולים ליצור רשימה עם השמות שלהם, לבחור אותם מתוך customer_data DataFrame, ואחסן את הבחירה ב- customer_data משתנה שוב לשימוש במודל העתידי שלנו.

selected_cols = ['Annual Income (k$)', 'Spending Score (1-100)']
customer_data = customer_data[selected_cols]

לאחר בחירת העמודות, נוכל לבצע את קנה המידה שנדון בסעיף הקודם. כדי להביא את התכונות לאותו קנה מידה או לתקנן אותם, אנחנו יכולים לייבא סקייט-Learn's StandardScaler, צור אותו, התאם את הנתונים שלנו כדי לחשב את הממוצע וסטיית התקן שלו, ותמיר את הנתונים על ידי הפחתת הממוצע שלהם וחלוקתם בסטיית התקן. זה יכול להיעשות בשלב אחד עם fit_transform() שיטה:

from sklearn.preprocessing import StandardScaler ss = StandardScaler() scaled_data = ss.fit_transform(customer_data)

המשתנים מותאמים כעת, ונוכל לבחון אותם על ידי הדפסת התוכן של ה- scaled_data מִשְׁתַנֶה. לחלופין, אנו יכולים גם להוסיף אותם לחדש scaled_customer_data DataFrame יחד עם שמות העמודות והשתמש ב- head() שוב שיטה:

scaled_customer_data = pd.DataFrame(columns=selected_cols, data=scaled_data)
scaled_customer_data.head()

תפוקות אלה:

 Annual Income (k$) Spending Score (1-100)
0 -1.738999 -0.434801
1 -1.738999 1.195704
2 -1.700830 -1.715913
3 -1.700830 1.040418
4 -1.662660 -0.395980 

הנתונים האלה מוכנים לאשכול! בעת הצגת DBSCAN, הזכרנו את מספר הנקודות המינימלי ואת האפסילון. יש לבחור את שני הערכים הללו לפני יצירת המודל. בוא נראה איך זה נעשה.

בחירת Min. דגימות ואפסילון

כדי לבחור את המספר המינימלי של נקודות עבור אשכול DBSCAN, יש כלל אצבע שקובע שהוא צריך להיות שווה או גבוה ממספר הממדים בנתונים פלוס אחד, כמו ב:

$$
טקסט{דקות נקודות} >= טקסט{מידות נתונים} + 1
$$

המידות הן מספר העמודות ב-dataframe, אנו משתמשים ב-2 עמודות, כך שהמינימום. הנקודות צריכות להיות 2+1, כלומר 3, או יותר. עבור דוגמה זו, בואו נשתמש 5 דקות. נקודות.

$$
טקסט{5 (מינימום נקודות)} >= טקסט{2 (מידות נתונים)} + 1
$$

כעת, כדי לבחור את הערך עבור ε יש שיטה שבה א השכנים הקרובים ביותר האלגוריתם משמש כדי למצוא את המרחקים של מספר מוגדר מראש של הנקודות הקרובות ביותר עבור כל נקודה. מספר השכנים המוגדר מראש הוא המינימום. נקודות שבחרנו זה עתה מינוס 1. אז, במקרה שלנו, האלגוריתם ימצא את 5-1, או 4 הנקודות הקרובות ביותר עבור כל נקודה בנתונים שלנו. אלה הם k-שכנים ו שלנו k שווה ל -4.

$$
טקסט{k-שכנים} = טקסט{דקות. נקודות} – 1
$$

לאחר מציאת השכנים, נסדר את המרחקים שלהם מהגדול לקטן ונשרטט את מרחקי ציר ה-y והנקודות בציר ה-x. בהסתכלות על העלילה, נגלה היכן היא דומה לכיפוף של מרפק ולנקודת ציר ה-y שמתארת ​​שכפוף המרפק הוא הערך המוצע של ε.

כדי לבצע את השלבים הללו, נוכל לייבא את האלגוריתם, להתאים אותו לנתונים, ואז נוכל לחלץ את המרחקים והמדדים של כל נקודה עם kneighbors() שיטה:

from sklearn.neighbors import NearestNeighbors
import numpy as np nn = NearestNeighbors(n_neighbors=4) nbrs = nn.fit(scaled_customer_data)
distances, indices = nbrs.kneighbors(scaled_customer_data)

לאחר מציאת המרחקים, נוכל למיין אותם מהגדול לקטן ביותר. מכיוון שהעמודה הראשונה של מערך המרחקים היא של הנקודה אל עצמה (כלומר כולם הם 0), והעמודה השנייה מכילה את המרחקים הקטנים ביותר, ואחריה העמודה השלישית בעלת המרחקים הגדולים מהשנייה, וכן הלאה, נוכל לבחור רק את ערכי העמודה השנייה ואחסנו אותם ב- distances מִשְׁתַנֶה:

distances = np.sort(distances, axis=0)
distances = distances[:,1] 

עכשיו, כשיש לנו את המרחקים הקטנים ביותר שלנו, אנחנו יכולים לייבא matplotlib, שרטט את המרחקים וצייר קו אדום על המקום שבו נמצא "עיקול המרפק":

import matplotlib.pyplot as plt plt.figure(figsize=(6,3))
plt.plot(distances)
plt.axhline(y=0.24, color='r', linestyle='--', alpha=0.4) plt.title('Kneighbors distance graph')
plt.xlabel('Data points')
plt.ylabel('Epsilon value')
plt.show();

זו התוצאה:

שימו לב שכאשר משרטטים את הקו, נגלה את ערך ε, במקרה זה, הוא כן 0.24.

סוף סוף יש לנו את נקודות המינימום שלנו ו-ε. עם שני המשתנים, נוכל ליצור ולהפעיל את מודל DBSCAN.

יצירת מודל DBSCAN

כדי ליצור את המודל, נוכל לייבא אותו מ-Scikit-Learn, ליצור אותו עם ε שזהה ל- eps טיעון, ונקודות המינימום שאליהן הוא ה mean_samples טַעֲנָה. לאחר מכן נוכל לאחסן אותו במשתנה, בואו נקרא לזה dbs והתאימו אותו לנתונים המותאמים:

from sklearn.cluster import DBSCAN dbs = DBSCAN(eps=0.24, min_samples=5)
dbs.fit(scaled_customer_data)

בדיוק ככה, מודל ה-DBSCAN שלנו נוצר והוכשר על הנתונים! כדי לחלץ את התוצאות, אנו ניגשים ל- labels_ תכונה. אנחנו יכולים גם ליצור חדש labels טור ב scaled_customer_data מסגרת נתונים ומלא אותה בתוויות החזויות:

labels = dbs.labels_ scaled_customer_data['labels'] = labels
scaled_customer_data.head()

זו התוצאה הסופית:

 Annual Income (k$) Spending Score (1-100) labels
0 -1.738999 -0.434801 -1
1 -1.738999 1.195704 0
2 -1.700830 -1.715913 -1
3 -1.700830 1.040418 0
4 -1.662660 -0.395980 -1

שימו לב שיש לנו תוויות עם -1 ערכים; אלו הם ה נקודות רעש, אלה שאינם שייכים לאף אשכול. כדי לדעת כמה נקודות רעש מצא האלגוריתם, נוכל לספור כמה פעמים הערך -1 מופיע ברשימת התוויות שלנו:

labels_list = list(scaled_customer_data['labels'])
n_noise = labels_list.count(-1)
print("Number of noise points:", n_noise)

תפוקות אלה:

Number of noise points: 62

אנחנו כבר יודעים ש-62 נקודות מהנתונים המקוריים שלנו של 200 נקודות נחשבו לרעש. מדובר ברעש רב, מה שמעיד שאולי ה-DBSCAN clustering לא התייחס לנקודות רבות כחלק מאשכול. נבין מה קרה בקרוב, כאשר נתווה את הנתונים.

בתחילה, כאשר צפינו בנתונים, נראה היה שיש להם 5 אשכולות של נקודות. כדי לדעת כמה אשכולות יצרו DBSCAN, נוכל לספור את מספר התוויות שאינן -1. ישנן דרכים רבות לכתוב את הקוד הזה; כאן, כתבנו לולאת for, שתעבוד גם עבור נתונים שבהם DBSCAN מצא אשכולות רבים:

total_labels = np.unique(labels) n_labels = 0
for n in total_labels: if n != -1: n_labels += 1
print("Number of clusters:", n_labels)

תפוקות אלה:

Number of clusters: 6

אנו יכולים לראות שהאלגוריתם חזה שלנתונים יהיו 6 אשכולות, עם נקודות רעש רבות. בואו נדמיין את זה על ידי תכנון זה עם זה של Seaborn scatterplot:

sns.scatterplot(data=scaled_customer_data, x='Annual Income (k$)', y='Spending Score (1-100)', hue='labels', palette='muted').set_title('DBSCAN found clusters');

זו התוצאה:

בהסתכלות על העלילה, אנו יכולים לראות ש-DBSCAN תפס את הנקודות שהיו מחוברות בצורה צפופה יותר, ונקודות שיכולות להיחשב כחלק מאותו אשכול היו רעש או נחשבו ליצירת אשכול קטן יותר.

אם נדגיש את האשכולות, שימו לב כיצד DBSCAN מקבל אשכול 1 לחלוטין, שהוא האשכול עם פחות מרווח בין נקודות. ואז הוא מקבל את החלקים של אשכולות 0 ו-3 שבהם הנקודות קרובות זו לזו, תוך התחשבות בנקודות מרווחות יותר כרעש. זה גם מחשיב את הנקודות בחצי השמאלי התחתון כרעש ומפצל את הנקודות בפינה הימנית התחתונה ל-3 אשכולות, שוב לוכד אשכולות 4, 2 ו-5 שבהם הנקודות קרובות יותר זו לזו.

אנחנו יכולים להתחיל להגיע למסקנה ש-DBSCAN היה מצוין ללכידת האזורים הצפופים של האשכולות, אבל לא כל כך לזיהוי הסכימה הגדולה יותר של הנתונים, התיחום של 5 האשכולות. יהיה מעניין לבדוק אלגוריתמים נוספים של אשכולות עם הנתונים שלנו. בואו נראה אם ​​מדד יאשש השערה זו.

הערכת האלגוריתם

כדי להעריך את DBSCAN נשתמש ב- ציון צללית אשר ייקח בחשבון את המרחק בין נקודות של אותו אשכול ואת המרחקים בין אשכולות.

ראשית, אנחנו יכולים לייבא silhouette_score מ-Skit-Learn, אם כן, העבר לזה את העמודות והתוויות שלנו:

from sklearn.metrics import silhouette_score s_score = silhouette_score(scaled_customer_data, labels)
print(f"Silhouette coefficient: {s_score:.3f}")

תפוקות אלה:

Silhouette coefficient: 0.506

לפי ציון זה, נראה ש-DBSCAN יכול ללכוד כ-50% מהנתונים.

סיכום

DBSCAN יתרונות וחסרונות

DBSCAN הוא אלגוריתם או מודל מקבצים ייחודיים מאוד.

אם נסתכל על היתרונות שלו, הוא טוב מאוד בקליטת אזורים צפופים בנתונים ונקודות רחוקות מאחרים. המשמעות היא שהנתונים לא חייבים להיות בעלי צורה ספציפית והם יכולים להיות מוקפים בנקודות אחרות, כל עוד הן מחוברות בצפיפות.

זה מחייב אותנו לציין נקודות מינימום ו-ε, אבל אין צורך לציין את מספר האשכולות מראש, כמו ב-K-Means, למשל. זה יכול לשמש גם עם מסדי נתונים גדולים מאוד מכיוון שהוא תוכנן עבור נתונים במידות גבוהות.

לגבי החסרונות שלו, ראינו שהוא לא יכול ללכוד צפיפויות שונות באותו אשכול, ולכן הוא מתקשה עם הבדלים גדולים בצפיפות. זה תלוי גם במדד המרחק ובקנה המידה של הנקודות. זה אומר שאם הנתונים לא מובנים היטב, עם הבדלים בקנה מידה ועם מדד מרחק לא הגיוני, הוא כנראה לא יצליח להבין אותם.

הרחבות DBSCAN

ישנם אלגוריתמים נוספים, כגון DBSCAN היררכי (HDBSCAN) ו הזמנת נקודות לזיהוי מבנה האשכולות (OPTICS), הנחשבות להרחבות של DBSCAN.

גם HDBSCAN וגם OPTICS יכולים בדרך כלל לבצע ביצועים טובים יותר כאשר יש אשכולות בצפיפות משתנים בנתונים והם גם פחות רגישים לבחירה או לדקה ההתחלתית. נקודות ופרמטרים ε.

• הפצת תוכן ויחסי ציבור מופעל על ידי SEO. קבל הגברה היום.
• Platoblockchain. Web3 Metaverse Intelligence. ידע מוגבר. גישה כאן.
• מקור: https://stackabuse.com/dbscan-with-scikit-learn-in-python/