Answers.Body: <p>Though obviously large noise in the training data can affect the quality of the k-means clustering result, it's guaranteed to converge to a <em>local</em> minimum of its objective function <span class="math-container">$J$</span> which is the sum of squared distances between data points and their assigned centroids. k-means does not guarantee finding the global minimum due to its sensitivity to initial centroid positions.</p>
  <p>The algorithm starts by initializing k centroids, usually chosen randomly. Each data point is then assigned to the nearest centroid which minimizes the distance between the data points and centroids within each cluster. The centroids are then updated to be the mean of the data points assigned to them which minimizes the sum of squared distances within each cluster. Each iteration of the assignment and update steps above leads to a monotonic non-increase in <span class="math-container">$J$</span>. Since <span class="math-container">$J$</span> is bounded below (cannot be less than zero) and decreases monotonically along with the fact that the number of possible assignments of <span class="math-container">$n$</span> data points to <span class="math-container">$k$</span> clusters is finite, the algorithm must eventually reach a state where further iterations do not change the assignments and centroids, even with many outlier noises.</p>
  <p>In practice to deal with possible large noise, <a href="https://en.wikipedia.org/wiki/DBSCAN" rel="nofollow noreferrer">density-based spatial clustering of applications with noise (DBSCAN)</a> is preferred.</p>
  <blockquote>
  <p>DBSCAN does not require one to specify the number of clusters in the data a priori, as opposed to k-means... DBSCAN has a notion of noise, and is robust to outliers.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-27T20:08:57.753Z
Answers.LastActivityDate: 2024-12-27T20:14:42.040Z
Answers.LastEditDate: 2024-12-27T20:14:42.040Z
Answers.UserDisplayName: cinch
Body: <p>Is the following statement correct?</p>
  <p>&quot;k-means may diverge if there is noise in the data.&quot;</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-27T20:21:31.663Z
Comments.Text: What do you mean by noise? Is it same as outlier?
Comments.UserDisplayName: Muhammad Ikhwan Perwira
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-27T21:36:00.480Z
Comments.Text: @MuhammadIkhwanPerwira Just vote to close questions that are not clear enough, which is the case here. Do you already have the privilege to vote to close questions? This is an extremely lazy question.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-12-27T22:02:35.410Z
Comments.Text: @nbro No, I don't.
Comments.UserDisplayName: Muhammad Ikhwan Perwira
Tags: <clustering><k-means>
Title: question about k-means convergence under noise
UserDisplayName: DSPinfinity
ThreadText: # question about k-means convergence under noise
  
  (Asked by: username_0 on 2024-12-27)
  
  Is the following statement correct?
  
  "k-means may diverge if there is noise in the data."
  
  **Tags:** clustering, k-means
  > **Comments:**
  > **username_1**: What do you mean by noise? Is it same as outlier?  
  > **username_2**: @MuhammadIkhwanPerwira Just vote to close questions that are not clear enough, which is the case here. Do you already have the privilege to vote to close questions? This is an extremely lazy question.  
  > **username_1**: @nbro No, I don't.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2024-12-27. Score: 1 | Accepted answer
  
  Though obviously large noise in the training data can affect the quality of the k-means clustering result, it's guaranteed to converge to a *local* minimum of its objective function $J$ which is the sum of squared distances between data points and their assigned centroids. k-means does not guarantee finding the global minimum due to its sensitivity to initial centroid positions.
  
  The algorithm starts by initializing k centroids, usually chosen randomly. Each data point is then assigned to the nearest centroid which minimizes the distance between the data points and centroids within each cluster. The centroids are then updated to be the mean of the data points assigned to them which minimizes the sum of squared distances within each cluster. Each iteration of the assignment and update steps above leads to a monotonic non-increase in $J$. Since $J$ is bounded below (cannot be less than zero) and decreases monotonically along with the fact that the number of possible assignments of $n$ data points to $k$ clusters is finite, the algorithm must eventually reach a state where further iterations do not change the assignments and centroids, even with many outlier noises.
  
  In practice to deal with possible large noise, [density-based spatial clustering of applications with noise (DBSCAN)](https://en.wikipedia.org/wiki/DBSCAN) is preferred.
  
  > DBSCAN does not require one to specify the number of clusters in the data a priori, as opposed to k-means... DBSCAN has a notion of noise, and is robust to outliers.
  
  
  ---
  
  