2
$\begingroup$

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|$.

$\endgroup$
1
$\begingroup$

Naive approach: define a similarity or distance function, say for instance cosine similarity.

  1. Calculate the similarity score between any pair $(x_i\in A, y_j\in B)$
  2. 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$.
  3. For every $y_j\in B$, find the set $c(y_j) = \{ x_i\in A\ |\ sim(x_i,y_j)\geq 1-\epsilon \}$
  4. 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|}$$

$\endgroup$
2
  • $\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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.