Canopy clustering algorithm

<h2 id="description">Description</h2>
<p>The algorithm proceeds as follows, using two thresholds 
  
    
      
        
          T
          
            1
          
        
      
    
    {\displaystyle T_{1}}
  
 (the loose distance) and 
  
    
      
        
          T
          
            2
          
        
      
    
    {\displaystyle T_{2}}
  
 (the tight distance), where 
  
    
      
        
          T
          
            1
          
        
        >
        
          T
          
            2
          
        
      
    
    {\displaystyle T_{1}>T_{2}}
  
 .<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<ol><li>Begin with the set of data points to be clustered.</li>
<li>Remove a point from the set, beginning a new 'canopy' containing this point.</li>
<li>For each point left in the set, assign it to the new canopy if its distance to the first point of the canopy is less than the loose distance 
  
    
      
        
          T
          
            1
          
        
      
    
    {\displaystyle T_{1}}
  
.</li>
<li>If the distance of the point is additionally less than the tight distance 
  
    
      
        
          T
          
            2
          
        
      
    
    {\displaystyle T_{2}}
  
, remove it from the original set.</li>
<li>Repeat from step 2 until there are no more data points in the set to cluster.</li>
<li>These relatively cheaply clustered canopies can be sub-clustered using a more expensive but accurate algorithm.</li></ol>
<p>An important note is that individual data points may be part of several canopies. As an additional speed-up, an approximate and fast distance metric can be used for 3, where a more accurate and slow distance metric can be used for step 4.
</p>
<h2 id="applicability">Applicability</h2>
<p>Since the algorithm uses distance functions and requires the specification of distance thresholds, its applicability for high-dimensional data is limited by the <a href="/facts/Curse_of_dimensionality/dk7SnY6L">curse of dimensionality</a>. Only when a cheap and approximative – low-dimensional – distance function is available, the produced canopies will preserve the clusters produced by K-means.
</p><p>Its benefits include:
</p>
<ul><li>The number of instances of training data that must be compared at each step is reduced.</li>
<li>There is some evidence that the resulting clusters are improved.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>McCallum, A.; Nigam, K.; and Ungar L.H. (2000) "Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching", Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 169-178 doi:10.1145/347090.347123 <a href="http://www.kamalnigam.com/papers/canopy-kdd00.pdf" target="_blank">http://www.kamalnigam.com/papers/canopy-kdd00.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>McCallum, A.; Nigam, K.; and Ungar L.H. (2000) "Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching", Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 169-178 doi:10.1145/347090.347123 <a href="http://www.kamalnigam.com/papers/canopy-kdd00.pdf" target="_blank">http://www.kamalnigam.com/papers/canopy-kdd00.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>"The Canopies Algorithm". courses.cs.washington.edu. Retrieved 2014-09-06. <a href="http://courses.cs.washington.edu/courses/cse590q/04au/slides/DannyMcCallumKDD00.ppt" target="_blank">http://courses.cs.washington.edu/courses/cse590q/04au/slides/DannyMcCallumKDD00.ppt</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Mahout description of Canopy-Clustering
 Retrieved 2022-07-02. <a href="https://mahout.apache.org/docs/latest/algorithms/clustering/canopy/" target="_blank">https://mahout.apache.org/docs/latest/algorithms/clustering/canopy/</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Canopy clustering algorithm open-in-new

Canopy clustering algorithm