# Cluster non-vector data based on similarity rating

I have a list $S$ of $N$ non-vector elements (in this case words or concepts), and I'd like to partition them into k subsets of similar words.

For each pair $(a,b)$ with $a,b \in S$, I have a number $p_{a,b}\in [0,1]$ representing a noisy probability that $a$ and $b$ are in the same class (I asked my respondents to group them into $k$ subsets for various values of $k$, so $p_{a,b}$ is how often users put them in the same class, averaged over all $k$).

The standard approach seems to be, for given $k$, to find $f:S\to\{1,...,k\}$ minimizing $$\displaystyle\sum_{c=1}^k \sum_{f(a)=f(b)=c} cost(p_{a,b})$$ for some proper choice of $cost$. However all algortihms I find require the elements to be vectors of data. Here, I really only have this user-based similarity rating, and that is for each pair $(a,b)$; I have no meaningful data for the actual words/sentences $a$ and $b$. Do any known clustering algorithms take data purely about the pairs, without needing the elements to be numerical/vectorial?

Essentially, you have a similarity matrix or distance matrix (how often they are put into different groups).

That is the typical input for Hierarchical Agglomerative Clustering (HAC). By no means these methods are restricted to numerical vectors. One of the few methods that really needs numerical vectors is k-means, because it needs to be able to compute means.

Your objective function should correspond exactly to one of the average linkage strategies.

• Thanks! I'm not so familiar with other methods than k-means to do HAC. Could you point me to one or more methods that would work well for this type of problem? (Easy to understand/implement is a bonus.) – user1111929 Aug 13 '17 at 22:46
• HAC is a method different from k-means. – Anony-Mousse Aug 13 '17 at 23:16

Interesting problem. If I understand correctly you essentially have a dataset where each input is a pair of sentence ID's and the output is the corresponding label, which here is the probability that those two sentences 'belonging together' constructed as you described. You want to learn some representation of the sentences that reflects the pairing labels.

One way you could do this is through a siamese neural network. Essentially you have a neural network whose input is some vector representation of sentence (perhaps a N-hot representation of the sentence, i.e. a vector of 0's of the length of your vocabulary, with 1's for the particular words in the sentence, or perhaps you could first convert the sentences to some other representation using the methods suggested in this answer). Then the output of this neural network is another vector - this will be your new your representation.

Now for a pair of sentences, we put both through the same neural network. Then we take the cosine similarity of the two outputs (or some other similarity network). Then we can consider this as the output probability that the two sentences are the same. We can compare this to the 'true' probability from your labels, and backpropagate the cross-entropy loss (or whatever loss term is appropriate/works best) to the neural network parameters (note we have done two forward passes, one for each sentence, but we only update the parameters once, averaging over both of these forward passes).

I'm sure there are other ways to do this (maybe you could draw a probabilistic graphical model) but this is what first came to my mind.

• Yes, the database could be seen in that format. However, vector representations of the sentences are not meaningful in this case. Half of them are just words, and often even technical terms known only to the respondents (i.e. not present in any dictionaries). – user1111929 Aug 6 '17 at 15:24
• Well if your sentences are meaningless then you can't really expect to extract any representation from them I suppose... Isn't the N-hot approach still feasible here? Edit: – nlml Aug 6 '17 at 15:37
• I think I'm a bit clearer on what you mean now. If the words are really completely meaningless, then maybe you could look for some sort of graph-based clustering method? Nodes are sentences, edges would be the pairing probabilities, and you can treat unknown edges as latent. Maybe even this? tkipf.github.io/graph-convolutional-networks – nlml Aug 6 '17 at 15:45
• You can indeed see the problem as a complete edge-weighted graph, where the nodes are the elements and the pairing probabilities are the edge weights, and I'm looking for a nontrivial partition of the nodes into k cliques so that the intra-clique edges have high probability. Unfortunately, the link you post deals with (semi)supervised regression/classification problems, and requires a vectorial input for each node, so I'm afraid that's not applicable here. – user1111929 Aug 6 '17 at 16:56
• Ah yep good point. Didn't look at the link in enough detail, sorry. There must be approaches out there for optimising the cliques as you say I would have thought. A quick google turned up this sciencedirect.com/science/article/pii/S1877050914004256 ? Another thought: maybe you could do something similar to the siamese network but without neural nets. Just have a latent vector z for each sentence, then perform stochastic gradient descent on these z's where the cost is cross-entropy between their cosine similarity and the target probability. Might work? – nlml Aug 6 '17 at 17:53