127
The standard k-means algorithm isn't directly applicable to categorical data, for various reasons. The sample space for categorical data is discrete, and doesn't have a natural origin. A Euclidean distance function on such a space isn't really meaningful. As someone put it, "The fact a snake possesses neither wheels nor legs allows us to say nothing about ...
52
K-means is not the most appropriate algorithm here.
The reason is that k-means is designed to minimize variance. This is, of course, appearling from a statistical and signal procssing point of view, but your data is not "linear".
Since your data is in latitude, longitude format, you should use an algorithm that can handle arbitrary distance functions, in ...
24
In my opinion, there are solutions to deal with categorical data in clustering. R comes with a specific distance for categorical data. This distance is called Gower (http://www.rdocumentation.org/packages/StatMatch/versions/1.2.0/topics/gower.dist) and it works pretty well.
20
(In addition to the excellent answer by Tim Goodman)
The choice of k-modes is definitely the way to go for stability of the clustering algorithm used.
The clustering algorithm is free to choose any distance metric / similarity score. Euclidean is the most popular. But any other metric can be used that scales according to the data distribution in each ...
19
For clustering, your data must be indeed integers. Moreover, since k-means is using euclidean distance, having categorical column is not a good idea. Therefore you should also encode the column timeOfDay into three dummy variables. Lastly, don't forget to standardize your data. This might be not important in your case, but in general, you risk that the ...
17
This question seems really about representation, and not so much about clustering.
Categorical data is a problem for most algorithms in machine learning. Suppose, for example, you have some categorical variable called "color" that could take on the values red, blue, or yellow. If we simply encode these numerically as 1,2, and 3 respectively, our algorithm ...
12
An approach that yields more consistent results is K-means++. This approach acknowledges that there is probably a better choice of initial centroid locations than simple random assignment. Specifically, K-means tends to perform better when centroids are seeded in such a way that doesn't clump them together in space.
In short, the method is as follows:
...
12
k-means is based on averages.
It models clusters using means, and thus the improvement by adding more data is marginal. The error of the average estimation reduces with 1/sqrt(n); so adding more data pays off less and less...
Strategies for such large data always revolve around sampling:
If you want sublinear runtime, you have to do sampling!
In fact, ...
12
Let us briefly talk about a probabilistic generalisation of k-means: the Gaussian Mixture Model (GMM).
In k-means, you carry out the following procedure:
- specify k centroids, initialising their coordinates randomly
- calculate the distance of each data point to each centroid
- assign each data point to its nearest centroid
- update the coordinates of the ...
11
Online k-means (more commonly known as sequential k-means) and traditional k-means are very similar. The difference is that online k-means allows you to update the model as new data is received.
Online k-means should be used when you expect the data to be received one by one (or maybe in chunks). This allows you to update your model as you get more ...
10
I don't think any of the clustering techniques "just" work at such scale. The most scalable supposedly is k-means (just do not use Spark/Mahout, they are really bad) and DBSCAN (there are some good distributed versions available).
But you will be facing many other challenges besides scale because clustering is difficult. It's not as if it's just enough to ...
8
K-means should be right in this case. Since k-means tries to group based solely on euclidean distance between objects you will get back clusters of locations that are close to each other.
To find the optimal number of clusters you can try making an 'elbow' plot of the within group sum of square distance. This may be helpful (http://nbviewer.ipython.org/...
8
Taking a stab:
I am trying to identify a clustering technique with a similarity measure that would work for categorical and numeric binary data.
Gower Distance is a useful distance metric when the data contains both continuous and categorical variables.
There are techniques in R kmodes clustering and kprototype that are designed for this type of ...
8
K-means
Your data has $7$ dimensions so k-means is worth to try. See the PCA of your data and check if any cluster is visible there as K-means will have a tough time if clusters are not Gaussian. the setup is:
Each person is a point in $7D$ space (a $50\times7$ matrix)
Apply PCA and inspect it.
If different clusters visible then you will have a result
...
7
The original MacQueen k-means publication (the first to use the name "kmeans") is an online algorithm.
MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations". Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability 1. University of California Press. pp. 281–297
After assigning each ...
7
GPS coordinates can be directly converted to a geohash. Geohash divides the Earth into "buckets" of different size based on the number of digits (short Geohash codes create big areas and longer codes for smaller areas). Geohash is an adjustable precision clustering method.
7
Just posting a summary of above comments and some more thoughts so that this question is removed from "unanswered questions".
Image_doctor's comment is right that these graphs are typical for k-means. (I am not familiar with the "Silhouette" measure though.) The in-cluster variance is expected to go down continuously with increasing k. The elbow is where ...
7
I play around quite a bit with location data and have found examples both where k-means works fine and where k-means is a poor representation and DBSCAN is a great fit.
If you've ever gone hiking or mountain climbing on a day with fog or a low cloud cover, there are times where you get to the top of the peak and can only see the surrounding peaks poking up ...
6
As a side comment note that using K-means for 10D data might end up in nowhere according to the curse of dimensionality. Of course it varies a bit according to the nature of the data but once I tried to determine the threshold in which K-Means starts behaving strange regarding the dimensionalty, I got something like 7D. After 7 dimensions it started to miss ...
6
Since you accepted another answer, which says this can't be done, I am editing this to include an example of it being done. Hope this helps!
Original Answer:
The most logical way to transform hour is into two variables that swing back and forth out of sink. Imagine the position of the end of the hour hand of a 24-hour clock. The x position swings back and ...
6
In that link you posted, you can look at the python full solution here at the end and go through it to see what all is distributed.
In short, some parts are distributed, like reading data from the file, but the very important parts like the distance computation are not.
Running down, we see:
sc = SparkContext("local[6]", "PythonKMeans")
This ...
6
PCA reduces dimensionality. It does not change the number of observations you have. Nor does it change the order of the data. The n-th observation in your original dataset will still be the n-th observation post-PCA.
Choosing the number of components in PCA and choosing the number of clusters in K-Means are independent of each other. Both K-Means and PCA ...
6
I would say hierarchical clustering is usually preferable, as it is both more flexible and has fewer hidden assumptions about the distribution of the underlying data.
With k-Means clustering, you need to have a sense ahead-of-time what your desired number of clusters is (this is the 'k' value). Also, k-means will often give unintuitive results if (a) ...
5
I may be misunderstanding your question, but usually k-means chooses your centroids randomly for you depending on the number of clusters you set (i.e. k). Choosing the number for k tends to be a subjective exercise. A good place to start is an Elbow/Scree plot which can be found here:
http://en.wikipedia.org/wiki/...
5
There are several approaches. You can start from the second one.
Equal-width (distance) partitioning:
It divides the range into N intervals of equal size: uniform grid
if A and B are the lowest and highest values of the attribute, the width of intervals will be: W = (B-A)/N.
The most straightforward
- Outliers may dominate presentation
- Skewed data is ...
5
You can use HDBSCAN for this. The python package has support for haversine distance which will properly compute distances between lat/lon points.
As the docs mention, you will need to convert your points to radians first for this to work. The following psuedocode should do the trick:
points = np.array([[lat1, lon1], [lat2, lon2], ...])
rads = np.radians(...
5
I am probably very late with my answer, but if you are still dealing with geo clustering, you may find this study interesting. It deals with comparison of two fairly different approaches to classifying geographic data: K-means clustering and latent class growth modeling.
One of the images from the study:
The authors concluded that the end results were ...
5
Finding the elbow can be made more easier by computing the angles between the consecutive segments.
Replace your:
kIdx = 10-1
with:
seg_threshold = 0.95 #Set this to your desired target
#The angle between three points
def segments_gain(p1, v, p2):
vp1 = np.linalg.norm(p1 - v)
vp2 = np.linalg.norm(p2 - v)
p1p2 = np.linalg.norm(p1 - p2)
...
5
When you have an unbalanced data set, the algorithm is going to weight its success on each data point equally, meaning the majority class comes out as much more important than the minority class. The typical solution is to sample down the majority class until it's the same size as the minority class, and an alternate (similar) solution is to adjust the cost ...
5
There is no good evaluation data at all for clustering that would allow such conclusions.
There isn't even good real data where you could say variant 1 of k-means is better than variant 2 of k-means.
There is also no good evaluation measure that would handle the notion of "noise" well either.
So: don't go by some number.
Clustering is about solving a ...
Only top voted, non community-wiki answers of a minimum length are eligible
