As far as I understand a large number of clustering problems can be formulated as:

$\underset{\textbf{P}}{ \text{argmin}} \; \sum_{i,j} f \left(x_i, x_j\right)$

where $\textbf{P}$ is a partitioning of $\mathbf{x}$. In other words, the goal is to find a partitioning that is optimal with respect to a sum of pairwise contributions of the variables within and/or across clusters. Problems such as K-means and correlation clustering can be written in the above form. For example, K-means minimizes the sum-of-squares which is known to be NP-hard.

I am wondering if there is any work on what I informally would call higher-order or clustering, where the functions $f$ measure the affinity of general cliques of variables

$\underset{\textbf{P}}{\text{argmax}}\; \sum_{c_i} f(\mathbf{x}_{c_i})$

for cliques $c_i$ in some set $C$.

Perhaps a more difficult problem is what I would informally call black-box clustering, i.e. problems of the above form where $f$ is unknown (i.e. we don't have access to an algebraic or analytical expression of $f$, but we can query it. I imagine using some sort of direct-search optimization method for solving such problems.

Does anybody know of if these problems have been addressed in the literature? Perhaps they are known by other names?

  • $\begingroup$ Maybe you are looking for spatial index or space-fillin-curve? $\endgroup$ – Gigamegs Aug 1 '11 at 22:55
  • $\begingroup$ Since your sum is "within and across clusters", I don't see where $\mathbf{P}$ comes in. $\endgroup$ – user6973 May 6 '12 at 17:48
  • $\begingroup$ Thanks @RickyDemer, $\textbf{P}$ is encoded in the choice of the variables $x_i$. That said, in K-means for example we only look for contributions within clusters. $\endgroup$ – Amelio Vazquez-Reina May 6 '12 at 17:52

One example of what you might call non-linear clustering is kernel-based clustering, where the similarity function is described by a (non-linear) kernel function. This is a weak form of non-linearity, since there's a lifting map that makes everything linear (albeit in a Hilbert space)

| cite | improve this answer | |
  • $\begingroup$ Thanks @Suresh, but everything I have seen on kernel-based clustering seems to be linear (maybe also quadratic?) in pairwise contributions between variables. The function $f$ above can measure the affinity of a clique of any size. I will clarify this in the question. $\endgroup$ – Amelio Vazquez-Reina Jul 28 '11 at 17:56
  • $\begingroup$ ah I see what you mean. $\endgroup$ – Suresh Venkat Jul 29 '11 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.