Meanshift clustering-01 principle analysis

Intro

   I used... In my work meanshift, Do not trace too complex principles and various algorithm variants , original paper wait . Only conceptually , Make a brief summary and introduction to the principle . The main logic , Reference resources sklearn Source code .

And commonly used k-means equally ,meanshift It is also an iterative algorithm . What we pay attention to is nothing more than the following ：

• Iterative logic , How to iterate
• The conditions for the termination of the iteration
• How to type the sample label

The main logic

sklearn The code logic of is as follows ：

• initialization : Generate bandwidth and seeds. If not specified bandwidth and seeds, It will generate
• Parallelization completes all seeds Iteration , Every seed It is equivalent to a separate iterative process
  • Iteration termination condition :max_iter=300 Or the threshold is less than 1e-3 * bandwidth
  • At the first iteration ,seed Is the clustering center , Get the center point bandwidth All sample points in the range
  • Recalculate the center point ( That is, find the mean ), Perform the previous step , Until the iteration stop condition is met
• Merge cluster centers
  • Sort according to the number of samples covered by each central point , Calculate the distance between each center point in turn
  • stay bandwidth Two central points within , Keep the center point with a high number of coverage samples
• Call the sample label
  • Find the nearest center point near each sample , Then the modified samples belong to this category
  • cluster_all=False, be bandwidth Points outside are named -1, Otherwise, it is the nearest cluster center

Ref

[1] https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html

                                2021-03-29 Jiulong lake, Jiangning District, Nanjing