# Higher-order and black-box clustering

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?

• Maybe you are looking for spatial index or space-fillin-curve? Aug 1 '11 at 22:55
• Since your sum is "within and across clusters", I don't see where $\mathbf{P}$ comes in.
– user6973
May 6 '12 at 17:48
• 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. May 6 '12 at 17:52

• 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. Jul 28 '11 at 17:56