Let $t$ be a distance threshold (user-defined parameter). $X$ is a dataset containing some $p$-dimensional data-points. $L$ is a list of representative-data collected from $X$. Given the following simple algorithm (in pseudocode):

L = []
for each x in X:
   d = min dist(x, c), for c in L
   if d > t:
      add x to L

What is the weakest thing we can assume on the data, so that we would be able to determine the complexity in terms of the final size of $L$ (i.e. $|L|$)?

  • $\begingroup$ Is $x$ a data point, variable, dimension, or...? What about $c$? I get that both ultimately come from $X$, but...you're not trying to avoid defining them so that the answer can be more general, are you? As for $X$, it seems like the data type (e.g., ordinal vs. interval) would become important in distance estimation. Are you willing to define $X$'s data type, or would continuous data be one of those minimal assumptions you'd rather not incorporate unless absolutely necessary? $\endgroup$ – Nick Stauner Jan 4 '14 at 22:31
  • $\begingroup$ I might rephrase is to the $p(||x - l||^2 > t) \forall x \in X, \forall l \in L$, to mitigate the dependence on $|X|$ and $|L|$. I have no clue how to go about solving it, except through simulation which would be highly dependency on the distribution. It seems like it relates to entropy of the distribution. It also looks significantly like Gaussian Processes and associated kernel methods. $\endgroup$ – Jessica Mick Jan 6 '14 at 19:38
  • 1
    $\begingroup$ @NickStauner $x$ is a data point. $c$ is another data point from the list L (just used in the pseudo code to show that d is the distance from x to its nearest point from L). I just want to know if there is assumptions to make on the data (e.g. there distribution) in order to be able to determine the complexity (a function of $t$) in terms of the final size of L. And what is this complexity ? $\endgroup$ – shn Jan 10 '14 at 9:40
  • $\begingroup$ @JacobMick do you mean that we should find the probability p( dist(x,l) > t ) for each x in X and l in L, And that this can only be done through simulation ? $\endgroup$ – shn Jan 10 '14 at 9:44
  • $\begingroup$ @shn Yes. I'm not sure about finding the closed form. It'd be pretty easy to find $p(||x - \mu||^2 > t) \forall x \in X$, where $X \sim \mathbb N(\mu,\sigma^2)$. This is just probability contours. From here you'd generalize it for all distributions, which is probably dependent on the entropy of the distribution or something related. See: courses.education.illinois.edu/EdPsy584/lectures/… $\endgroup$ – Jessica Mick Jan 10 '14 at 23:25

Here's just one of possibly many assumptions I suspect is necessary: your data are continuous. data sometimes have uneven distances between values (ranks) when they represent limited information about an underlying, continuous distribution. Therefore you wouldn't want to assume that $d>t$ if $t$ is meant to represent a threshold distance on that underlying, continuous distribution. For example, if $x=1$ and $c=3$, the $d=2$ (if this does happen to be the min dist in $L$) can represent a very different distance than if $x=12$ and $c=14$ in terms of the underlying continuous distribution. Say that underlying distribution is finishing time for a footrace, and the values of $x$ and $c$ represent the order in which the runners cross the finish line. It's not at all uncommon for one person to cross the finish line far ahead of the competition, or vice versa.

Again, this is just one of probably many assumptions that may be necessary, depending largely on what you want the threshold to mean.


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.