0
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ What about Jaccard similarity to compare Ci? $\endgroup$ – Has QUIT--Anony-Mousse May 11 '19 at 19:44
  • $\begingroup$ @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. $\endgroup$ – Alerra May 11 '19 at 21:32
  • $\begingroup$ 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. $\endgroup$ – Has QUIT--Anony-Mousse May 11 '19 at 22:11
  • $\begingroup$ @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. $\endgroup$ – Alerra May 12 '19 at 0:56
  • $\begingroup$ 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 $\endgroup$ – Has QUIT--Anony-Mousse May 12 '19 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.