I have two datasets, which are lists of multidimensional real-valued vectors. One dataset (call it $A=\{x_1, x_2, x_3, ..., x_n\}$ is of a big size, the other (call it $B=\{x_1, x_2, x_3, ..., x_m\}$). Furthermore, the other is far smaller and is a subset of the bigger one ($B \subset A$). The smaller one $B$, comes from some sampling process and what I want to do is to calculate, what fraction of the smaller (obtained from sampling) is in the bigger. Additionally, since those are real-valued vectors, I can't compare them directly one by one, so a clustering algorithm may be employed. Also the size of one dataset is bigger than the other $|A| >> |B|$.
$\begingroup$
$\endgroup$
2
Naive approach: define a similarity or distance function, say for instance cosine similarity.
- Calculate the similarity score between any pair $(x_i\in A, y_j\in B)$
- Define a precision level, say $\epsilon=0.000001$. The assumption is that it's extremely unlikely that two vectors would be this close by chance in $A$.
- For every $y_j\in B$, find the set $c(y_j) = \{ x_i\in A\ |\ sim(x_i,y_j)\geq 1-\epsilon \}$
- Obtain the union: $C(B)=\{x_i\in A\ |\ \exists y_j\in B: x_i\in c(y_j) \}$
The proportion of elements of $A$ which are "equal" to an element in $B$ is:
$$\frac{|C(B)|}{|A|}$$
-
$\begingroup$ Great ! Thank you Erwan. The only problem I see is that, when $|A|$ are not equal $|B|$, then the score tends to differ, even if they contain the same data. I think I've to underline it in my question. But anyway thanks for your answer. $\endgroup$ – Daniel Wiczew Jan 13 at 9:05
-
$\begingroup$ @DanielWiczew maybe I misunderstood something, but I think it simply depends on the distribution in A. For example if $|A|=1000$, B contains a single vector x and x appears 10 times in A, then the proportion is 1%. Now if $|A|=10000$ and x appears 100 times in A (same distribution), then the proportion is still 1%. But if $|A|=10000$ and x appears 10 times in A (different distribution) then the proportion becomes 0.1%. However all of this depends how vectors are generated, it's more complex if increasing $|A|$ means that the new vectors are close but not identical. $\endgroup$ – Erwan Jan 13 at 10:07