Abstract
Kernel methods are popular in clustering due to their generality anddiscriminating power. However, we show that many kernel clustering criteriahave density biases theoretically explaining some practically significantartifacts empirically observed in the past. For example, we provide conditionsand formally prove the density mode isolation bias in kernel K-means for acommon class of kernels. We call it Breiman's bias due to its similarity to thehistogram mode isolation previously discovered by Breiman in decision treelearning with Gini impurity. We also extend our analysis to other popularkernel clustering methods, e.g. average/normalized cut or dominant sets, wheredensity biases can take different forms. For example, splitting isolated pointsby cut-based criteria is essentially the sparsest subset bias, which is theopposite of the density mode bias. Our findings suggest that a principledsolution for density biases in kernel clustering should directly address datainhomogeneity. We show that density equalization can be implicitly achievedusing either locally adaptive weights or locally adaptive kernels. Moreover,density equalization makes many popular kernel clustering objectivesequivalent. Our synthetic and real data experiments illustrate density biasesand proposed solutions. We anticipate that theoretical understanding of kernelclustering limitations and their principled solutions will be important for abroad spectrum of data analysis applications across the disciplines.