<p>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)</p>

CC BY-SA 3.0
2011-07-28T17:56:18.153Z
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.
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-07-29T01:29:21.063Z
ah I see what you mean.
Suresh Venkat
CC BY-SA 3.0
2011-07-28T16:31:58.880Z
2011-07-28T16:31:58.880Z
Suresh Venkat
<p>As far as I understand a large number of clustering problems can be formulated as:</p>

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

<p>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 <a href="http://repository.cmu.edu/cgi/viewcontent.cgi?article=1170&amp;context=compsci" rel="nofollow">correlation clustering</a> can be written in the above form. For example, K-means minimizes the sum-of-squares which <a href="http://dl.acm.org/citation.cfm?id=1519389" rel="nofollow">is known</a> to be NP-hard.</p>

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

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

<p>for cliques $c_i$ in some set $C$.</p>

<p>Perhaps a more difficult problem is what I would informally call <strong>black-box</strong> clustering, i.e. problems of the above form where $f$ is <strong>unknown</strong> (i.e. we don't have access to an algebraic or analytical expression of $f$, but we can <strong>query it</strong>. I imagine using some sort of <a href="http://www.cs.wm.edu/~va/research/sirev.pdf" rel="nofollow">direct-search optimization</a> method for solving such problems.</p>

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

CC BY-SA 3.0
2011-08-01T22:55:51.517Z
Maybe you are looking for spatial index or space-fillin-curve?
Cybercartel
CC BY-SA 3.0
2012-05-06T17:52:14.067Z
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.
Amelio Vazquez-Reina
<reference-request><machine-learning><clustering>
Higher-order and black-box clustering
Amelio Vazquez-Reina
# Higher-order and black-box clustering

(Asked by: username_0 on 2011-07-27)

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](http://repository.cmu.edu/cgi/viewcontent.cgi?article=1170&context=compsci) can be written in the above form. For example, K-means minimizes the sum-of-squares which [is known](http://dl.acm.org/citation.cfm?id=1519389) 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](http://www.cs.wm.edu/~va/research/sirev.pdf) 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?

**Tags:** reference-request, machine-learning, clustering

> **Comments:**
> **username_1**: Maybe you are looking for spatial index or space-fillin-curve?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-07-28. Score: 2

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)

> **Comments:**
> **username_0**: 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.  
> **username_2**: ah I see what you mean.  

---

