קל לארגן דפים בעזרת אוספים אפשר לשמור ולסווג תוכן על סמך ההעדפות שלך.
כפי שצוין קודם, הרבה אלגוריתמים של קיבוץ לא מתאימים למערכי הנתונים שבהם נעשה שימוש בלמידת מכונה, שבדרך כלל מכילים מיליוני דוגמאות. לדוגמה, אלגוריתמים של אשכול היררכי אגרגטיבי או מפצל בוחנים את כל הצמדים של הנקודות, והמורכבות שלהם היא \(O(n^2 log(n))\) ו- \(O(n^2)\), בהתאמה.
הקורס הזה מתמקד ב-k-means כי הוא מתאים לעומס לפי \(O(nk)\), כאשר \(k\)הוא מספר האשכולות שבחר המשתמש. האלגוריתם הזה מקבצ נקודות ל-\(k\) אשכולות על ידי צמצום המרחקים בין כל נקודה לבין מרכז הכובד של האשכול שלה (ראו איור 1).
כתוצאה מכך, ה-k-means מתייחס לנתונים כאל מספר התפלגויות עגולות בערך, ומנסה למצוא אשכולות שתואמים להתפלגויות האלה. אבל נתונים מהעולם האמיתי מכילים חריגים וצבירים שמבוססים על צפיפות, ויכול להיות שהם לא יתאימו להנחות שעומדות בבסיס של k-means.
אלגוריתם של קיבוץ לפי k-means
האלגוריתם פועל לפי השלבים הבאים:
מציינים שער ראשוני ל- \(k\), שאפשר לשנות מאוחר יותר. בדוגמה הזו, בוחרים ב- \(k = 3\).
בוחרים באופן אקראי \(k\) נקודות מרכזיות.
איור 1: ניתוח k-means בשלב האתחול.
מקצים כל נקודה למרכז המסה הקרוב ביותר כדי לקבל \(k\) אשכולות ראשוניים.
איור 2: אשכולות ראשוניים.
לכל אשכול, מחשבים מרכז כובד חדש על ידי חישוב המיקום הממוצע של כל הנקודות באשכול. החצים באיור 4 מציגים את השינוי במיקומי מרכזי הכובד.
איור 3: מרכזי מסה מחושבים מחדש.
מקצים מחדש כל נקודה למרכז המסה החדש הקרוב ביותר.
איור 4: אשכולות אחרי ההקצאה מחדש.
חוזרים על שלבים 4 ו-5, ומחשבים מחדש את מרכזי הכובד ואת החברות באשכול עד שהנקודות לא משנות אשכולות. במקרה של מערכי נתונים גדולים, אפשר לעצור את האלגוריתם לפני ההתכנסות על סמך קריטריונים אחרים.
מכיוון שמיקומי מרכזי הכובד נבחרים בהתחלה באופן אקראי, יכול להיות שהמודל k-means יחזיר תוצאות שונות באופן משמעותי בהרצות עוקבות. כדי לפתור את הבעיה הזו, מריצים את k-means כמה פעמים ובוחרים את התוצאה עם מדדי האיכות הטובים ביותר. (נתאר את מדדי האיכות בהמשך הקורס). כדי לבחור מיקומי מרכז כובד ראשוניים טובים יותר, תצטרכו גרסה מתקדמת של k-means.
[[["התוכן קל להבנה","easyToUnderstand","thumb-up"],["התוכן עזר לי לפתור בעיה","solvedMyProblem","thumb-up"],["סיבה אחרת","otherUp","thumb-up"]],[["חסרים לי מידע או פרטים","missingTheInformationINeed","thumb-down"],["התוכן מורכב מדי או עם יותר מדי שלבים","tooComplicatedTooManySteps","thumb-down"],["התוכן לא עדכני","outOfDate","thumb-down"],["בעיה בתרגום","translationIssue","thumb-down"],["בעיה בדוגמאות/בקוד","samplesCodeIssue","thumb-down"],["סיבה אחרת","otherDown","thumb-down"]],["עדכון אחרון: 2025-02-25 (שעון UTC)."],[[["\u003cp\u003eThe k-means clustering algorithm groups data points into clusters by minimizing the distance between each point and its cluster's centroid.\u003c/p\u003e\n"],["\u003cp\u003eK-means is efficient, scaling as O(nk), making it suitable for large datasets in machine learning, unlike hierarchical clustering methods.\u003c/p\u003e\n"],["\u003cp\u003eThe algorithm iteratively refines clusters by recalculating centroids and reassigning points until convergence or a stopping criteria is met.\u003c/p\u003e\n"],["\u003cp\u003eDue to random initialization, k-means can produce varying results; running it multiple times and selecting the best outcome based on quality metrics is recommended.\u003c/p\u003e\n"],["\u003cp\u003eK-means assumes data is composed of circular distributions, which may not be accurate for all real-world data containing outliers or density-based clusters.\u003c/p\u003e\n"]]],[],null,["As previously mentioned, many clustering algorithms don't scale to the datasets\nused in machine learning, which often have millions of examples. For example,\nagglomerative or divisive hierarchical clustering algorithms look at all pairs\nof points and have complexities of \\\\(O(n\\^2 log(n))\\\\) and \\\\(O(n\\^2)\\\\),\nrespectively.\n\nThis course focuses on k-means because it scales as \\\\(O(nk)\\\\), where \\\\(k\\\\)\nis the number of clusters chosen by the user. This algorithm groups points into\n\\\\(k\\\\) clusters by minimizing the distances between each point and its\ncluster's centroid (see Figure 1).\n\nAs a result, k-means effectively treats data as composed of a number of roughly\ncircular distributions, and tries to find clusters corresponding to these\ndistributions. But real-world data contains outliers and density-based clusters\nand might not match the assumptions underlying k-means.\n\nk-means clustering algorithm\n\nThe algorithm follows these steps:\n\n1. Provide an initial guess for \\\\(k\\\\), which can be revised later. For this\n example, we choose \\\\(k = 3\\\\).\n\n2. Randomly choose \\\\(k\\\\) centroids.\n\n \u003cbr /\u003e\n\n **Figure 1: k-means at initialization.**\n\n \u003cbr /\u003e\n\n3. Assign each point to the nearest centroid to get \\\\(k\\\\) initial clusters.\n\n \u003cbr /\u003e\n\n **Figure 2: Initial clusters.**\n\n \u003cbr /\u003e\n\n4. For each cluster, calculate a new centroid by taking the mean position of\n all points in the cluster. The arrows in Figure 4 show the change in\n centroid positions.\n\n \u003cbr /\u003e\n\n **Figure 3: Recomputed centroids.**\n\n \u003cbr /\u003e\n\n5. Reassign each point to the nearest new centroid.\n\n \u003cbr /\u003e\n\n **Figure 4: Clusters after reassignment.**\n\n \u003cbr /\u003e\n\n6. Repeat steps 4 and 5, recalculating centroids and cluster membership, until\n points no longer change clusters. In the case of large datasets, you can\n stop the algorithm before convergence based on other criteria.\n\nBecause the centroid positions are initially chosen at random, k-means can\nreturn significantly different results on successive runs. To solve this\nproblem, run k-means multiple times and choose the result with the best quality\nmetrics. (We'll describe quality metrics later in this course.) You'll need an\nadvanced version of k-means to choose better initial centroid positions.\n\nThough a deep understanding of the math is not necessary, for those who are\ncurious, k-means is a special case of the\n[expectation-maximization algorithm](https://wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm). See\n[lecture notes on the topic](https://alliance.seas.upenn.edu/%7Ecis520/dynamic/2021/wiki/index.php?n=Lectures.EM#toc-1.2) from UPenn."]]
