3 ms·

For all those struggling to understand the mean shift algorithm, it's much easier to understand in pictures. Here's an article that explains it with some diagra

For all those struggling to understand the mean shift algorithm, it's much easier to understand in pictures. Here's an article that explains it with some diagrams: http://eric-yuan.me/continuously-adaptive-shift/ http://eric-yuan.me/continuously-adaptive-shift/ Basically, it goes like this: 1. Select a data point of interest. 2. Draw a circle of a specified radius around the point of interest. 3. Collect all data points within the circle and compute their mean. 4. Move the center of the circle to the mean. 5. Repeat 3 & 4 until convergence. Each iteration will move "uphill" on the density gradient of the data distribution until it reaches the top of the hill (a local maximum). 6. Repeat 1-5 for all data points. Points that converge to the same local maximum are members of the same cluster. The number of clusters is the number of local maxima. For higher dimensions, replace "circle" with sphere (3-D) or hypersphere (4 & higher dimensions). Obviously, this algorithm depends on a choice of radius, which determines the granularity of the search for local maxima.

thomasahle 10y ago
Do I understand correctly that you run the converging process on every single point? Couldn't you have a situation where points really far from a cluster would still converge to that cluster by this method? Something like a long string of points slowly getting closer and closer? Does the mean shift algorithm have any guarantees on running time and/or the quality of the clustering it finds?
- rcthompson 10y ago
  > Do I understand correctly that you run the converging process on every single point? I don't think you have to run it on every point in the data set. If your data set is very large, you could run it on a random sample of points, or a define a regular grid of starting positions at the resolution that you require. > Couldn't you have a situation where points really far from a cluster would still converge to that cluster by this method? Something like a long string of points slowly getting closer and closer? Yes, that's the idea. For each point, you're basically asking "If I start here and keep walking up the density gradient from here until I hit a maximum, where do I end up?" If the shape of the probability density function has a very long ridge, you could end up walking the entire length of the ridge until you hit the highest point. This means that you can have arbitrary-shaped clusters, within the smoothness bounds imposed by your chosen radius. This feature is considered a potential advantage over k-means clustering, which can only produce convex clusters. > Does the mean shift algorithm have any guarantees on running time and/or the quality of the clustering it finds? I haven't actually used it in practice, so I don't know.
fizixer 10y ago
So I guess the purpose is to find center-of-mass of a large collection of points, without using all those points for calculation (instead using only the ones inside a pre-defined radius)?
- rcthompson 10y ago
  Not the center of mass, the point with the greatest mass nearby. Think of a thin stick with a ball on one end. The center of mass, i.e. the point where the stick balances, might be somewhere along the stick, closer to the end with the ball on it. But the point of maximum local density will be at the center of the ball, no matter how long the stick is.
deleted 10y ago
[deleted]

thomasahle 10y ago

Do I understand correctly that you run the converging process on every single point? Couldn't you have a situation where points really far from a cluster would still converge to that cluster by this method? Something like a long string of points slowly getting closer and closer? Does the mean shift algorithm have any guarantees on running time and/or the quality of the clustering it finds?

rcthompson 10y ago
> Do I understand correctly that you run the converging process on every single point? I don't think you have to run it on every point in the data set. If your data set is very large, you could run it on a random sample of points, or a define a regular grid of starting positions at the resolution that you require. > Couldn't you have a situation where points really far from a cluster would still converge to that cluster by this method? Something like a long string of points slowly getting closer and closer? Yes, that's the idea. For each point, you're basically asking "If I start here and keep walking up the density gradient from here until I hit a maximum, where do I end up?" If the shape of the probability density function has a very long ridge, you could end up walking the entire length of the ridge until you hit the highest point. This means that you can have arbitrary-shaped clusters, within the smoothness bounds imposed by your chosen radius. This feature is considered a potential advantage over k-means clustering, which can only produce convex clusters. > Does the mean shift algorithm have any guarantees on running time and/or the quality of the clustering it finds? I haven't actually used it in practice, so I don't know.

fizixer 10y ago

So I guess the purpose is to find center-of-mass of a large collection of points, without using all those points for calculation (instead using only the ones inside a pre-defined radius)?

rcthompson 10y ago
Not the center of mass, the point with the greatest mass nearby. Think of a thin stick with a ball on one end. The center of mass, i.e. the point where the stick balances, might be somewhere along the stick, closer to the end with the ball on it. But the point of maximum local density will be at the center of the ball, no matter how long the stick is.

deleted 10y ago

[deleted]