# Techniques for Collection/Graph Conversion to Cluster-able Data

Here are my problems; any techniques/papers as to how to approach this problem would be much appreciated. I also apologize for the vagueness of my question title; I do not really know if there is a term for what I am trying to do.

Problem 1:

Suppose we have a $$n$$-dimensional space $$\mathcal{X}$$. Say we have a set $$X$$ of data points $$x$$ which lie in $$\mathcal{X}$$. Now, suppose we have a set $$\mathcal{C}$$, which is a collection of sets $$\{C_i\}$$ which partition $$X$$. There is no restriction on the size of a given $$C_i$$. I would like to find some way to cluster $$C_i$$ based on the data points inside them. This means I would like some way of comparing the $$C_i$$'s.

My original thought to solve this was to have some way to convert each of the $$C_i$$ to a vector given the points inside them. This would be easier to do if the $$x$$ were discrete datapoints but this is not the case; therefore I have reached a roadblock. It should also be noted that the clustering of the $$C_i$$ is not my problem; I know many techniques to do this and am mostly just stuck on how to vectorize the $$C_i$$.

UPDATE: My second thought was that maybe instead of vectorizing each $$C_i$$, we could instead form a probability distribution over the space $$\mathcal{X}$$ for each of the $$C_i$$ and then to compare them, use something like KL-divergence to find the similarity. This seems like it would be relatively effective, and I know of techniques of how to form the probability distributions, so it seems tractable as well.

Problem 2 (a more advanced version of Problem 1):

This problem is very similar to Problem 1, however there is extra structure imposed on the $$C_i$$. For this problem, we define the $$G_i = (C_i, w)$$, where $$w : \mathcal{X} \times \mathcal{X} \mapsto \mathbb{R}$$ is a distance metric imposed on the $$x$$'s in a given $$C_i$$. Basically, $$G_i$$ is a weighted graph with the data points as vertices. In this problem, similar as to problem 1, I would like to see if there is some way to compare the $$G_i$$ so that I can eventually cluster them.

If there are any clarifications I can make please let me know in the comments; otherwise as I said, I would be sincerely grateful for any suggestions as to how to go about these problems. Thanks in advance!

• What about Jaccard similarity to compare Ci? – Has QUIT--Anony-Mousse May 11 '19 at 19:44
• @Anony-Mousse I think this would be a good similarity metric to use if 1) the data was discrete, and 2) the $C_i$'s were the same size. In theory I could discretize my data to solve 1). But for 2), it seems like if we have one $C_i$ with 50 elements and another with 5 elements all contained in the first, the Jaccard index would be .1, which would be relatively low despite one $C_i$ being a subset of the other. I have given the first problem more thought and updated my question with another potential solution. Still quite stuck on the second problem though. – Alerra May 11 '19 at 21:32
• Usually it is very sensible to have small subsets score low compared to a big set. Otherwise everything is highly similar to the empty set and trivial one-element sets. But apparently you need to design your own similarity then. – Has QUIT--Anony-Mousse May 11 '19 at 22:11
• @Anony-Mousse you make a good point. It is certainly something to try. But the discretization of my data may be quite lossy for large $n$ to make the $x$'s match up. We shall see. – Alerra May 12 '19 at 0:56
• So they aren't subsets, but independent samples? That was all but clear from your question, which seemed to have Ci subset X subset other X – Has QUIT--Anony-Mousse May 12 '19 at 5:55