All Questions
Tagged with k-means algorithms
20 questions
35
votes
1
answer
35k
views
Difference between standard and spherical k-means algorithms
I would like to understand, what is the major implementation difference between standard and spherical k-means clustering algorithms.
In each step, k-means computes distances between element vectors ...
- 1,329
14
votes
3
answers
42k
views
Why do we use k-means instead of other algorithms?
I researched about k-means and these are what I got: k-means is one of the simplest algorithm which uses unsupervised learning method to solve known clustering issues. It works really well with large ...
10
votes
3
answers
3k
views
Cycling in k-means algorithm
According to wiki the most widely used convergence criterion is "assigment hasn't changed". I was wondering whether cycling can occur if we use such convergence criterion? I'd be pleased if anyone ...
- 4,034
8
votes
1
answer
8k
views
Clustering algorithms for extremely sparse data
I am trying to cluster an extremely sparse text corpus, and I know the number of clusters (my data is the title and author list of scientific publications, for which I already know the number of ...
- 419
7
votes
4
answers
20k
views
How do I mathematically prove that k-means clustering converges to minimum squared error?
I am using k-means clustering to analyze and obtain patterns in traffic data. This well-known algorithm performs 2 steps per iteration.
Assign each object to a cluster closest to it, based on the ...
6
votes
2
answers
17k
views
How random are the results of the kmeans algorithm?
I have a question regarding the kmeans algorithm. I know kmeans is a randomized algorithm, but how random is it and what results can I expect. Suppose you have clustered a dataset into $4$ clusters, ...
- 413
2
votes
2
answers
2k
views
Finding cluster number based on distance & max element count
Given two constraints:
The maximum distance d an element can lie from a cluster centroid (or medoid)
The maximum number of elements n in one cluster
Is it possible to find the minimum number of ...
- 23
2
votes
1
answer
370
views
Choosing the best clustering algorithm and evaluating the results
I'm trying to separate my data into clusters using the k-means algorithm and the hierarchical algorithm, choose which algorithm fits my data the best, and evaluate the results. However, all of my ...
- 61
1
vote
1
answer
1k
views
How to implement k-means cluster analysis algorithm correctly?
I am trying to implement the K-mean analysis with the Standard algorithm.
My implementation seems to work, but I noticed some strange behavior. If the k is close to half of the length of the list to ...
- 113
1
vote
1
answer
140
views
In $k$-means, how is it NP-hard if the dimensionality of the data is at least $2$ ($d\geq 2$)?
In $k$-means, how is it NP-hard if the dimensionality of the data is at least $2$ ($d\geq 2$)? Can someone justify or give reasons to this statement?
Any guidance would be appreciated.
1
vote
1
answer
2k
views
Difference between Hartigan & Wong Algo to Lloyd's algorithm in K-means clustering
In the iterations of Hartigan and Wong Algo of K-Means clustering, If the centroid is updated in the last step, for each data point included, the within- cluster sum of squares for each data point if ...
- 1,195
1
vote
2
answers
327
views
K-Means clustering: optimal clusters for common data sets
I use scikit-learn to get IRIS and WINE clusters for evaluating an algorithm for K-means clustering. The K-means algorithm is a heuristic algorithm for solving the "minimum-sum-of-squares-clustering (...
- 111
1
vote
1
answer
2k
views
Are there any algorithms that give global optimum for K-Means?
The performance function of K-Means is minimum distance form the observations to the centroid of the closet cluster. For ideal solution we must find the real centroid of each cluster, but in ordinary ...
1
vote
0
answers
22
views
Spatial Temporal Clustering evenly spaced over time
I have a large dataset of spatio-temporal data. It has longitude and latitude coordinates, and a date for each observation. For example:
Long
Lat
Date
50
20.43
9-19-2010
51
19.5
10-4-2010
51
19.3
...
- 121
1
vote
0
answers
44
views
Differentiate between two set of points
Consider two sets of points (in the pictures below), whose "center of gravity" is same. What measure can differentiate between the two sets?
e.g.
Image 1 ...
- 161
1
vote
0
answers
52
views
Does a Local Minima Exists at K=2 in the Gap Statistic for the G-Means Algorithm
Currently, I am attempting to use the G-Means algorithm to attempt to solve the ill-defined image segmentation problem as it is a very algorithmically cheap solution to the ill-defined high-...
- 121
0
votes
1
answer
151
views
Questions about a k-means variant : recompute centroids after each point is reasigned
I have a variant of k-means, where the points are reassigned incrementally and I have a few questions about it.
Each time we reassign a point (we move the point from cluster $C_1 $to
$C_2$), we ...
- 1
0
votes
2
answers
1k
views
K-mean++ initialization algorithm alternative
I got this question as an exercise, and I frankly don't know where to begin:
Consider the deterministic variant of the k−means++ algorithm where the set of initial centroids are selected in the ...
- 25
0
votes
0
answers
1k
views
What are differences between K-means versions: Lloyd, Forgy, Macquen, Hartigan and other?
I'm looking for the (perhaps brief) explanation of the main differences between the different K-means clustering procedures, such as between Lloyd, Forgy, MacQueen and Hartigan, and possibly other ...
- 333
0
votes
0
answers
35
views
Would the result of a K-means clustering run with k = 27 equal the result of three "sub-runs", with total K = 3^3^3?
Suppose I want to try two K-means clustering methods. In the first one, I set k = 27, the algorithm converges, and I get some result set of centroids Y. In the second method, I want to do three "sub-...
- 646