Balanced clustering

<p>Balanced clustering is a special case of <a href="/facts/Cluster_analysis/HUeDnWPt">clustering</a> where, in the strictest sense, cluster sizes are constrained to 
  
    
      
        ⌊
        
          
            n
            k
          
        
        ⌋
      
    
    {\displaystyle \lfloor {n \over k}\rfloor }
  
 or 
  
    
      
        ⌈
        
          
            n
            k
          
        
        ⌉
      
    
    {\displaystyle \lceil {n \over k}\rceil }
  
, where 
  
    
      
        n
      
    
    {\displaystyle n}
  
 is the number of points and 
  
    
      
        k
      
    
    {\displaystyle k}
  
 is the number of clusters. A typical algorithm is balanced <a href="/facts/K-means_clustering/vxIcqHwN">k-means</a>, which minimizes <a href="/facts/Mean_squared_error/kz3TR7bv">mean square error (MSE)</a>. Another type of balanced clustering called balance-driven clustering has a two-objective cost function that minimizes both the imbalance and the MSE. Typical cost functions are ratio cut and Ncut. Balanced clustering can be used for example in scenarios where freight has to be delivered to 
  
    
      
        n
      
    
    {\displaystyle n}
  
 locations with 
  
    
      
        k
      
    
    {\displaystyle k}
  
 cars. It is then preferred that each car delivers to an equal number of locations.
</p>

Balanced clustering open-in-new

Balanced clustering