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?
 A: 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.
A: 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.
