CS版 - About testing of uniform distribution |
|
|
|
|
|
t******t 发帖数: 51 | 1 My problem is to test if a set of point in 3D space are uniformly
distributed in a spatial region. I did a google
search and found something like Kolmogorov-Smirnov goodness-of-fit test. My
question is: what is the
computational complexity of running this test in terms of the number of
points N? Are there any C libraries
that implemented this? Links to a tutorial of such tests will also be
appreciated. Thanks. | s*****g 发帖数: 5159 | 2 I do not know this test but I know another test that works nicely.
Supposed you have N points in the 3D unit cube. Make a sqrt(N,3)x sqrt(N,3)x
sqrt(N,3) grid in the unit cube. Test how many grid cube contains more than
1 points and how many contains no point, if this number is higher than some
thresh hold (very low but I forget - can be done through a learning using
Bayesian decision rule), you will see the uniformity of the points by making
use of the geometry information.
This can extend to n
【在 t******t 的大作中提到】 : My problem is to test if a set of point in 3D space are uniformly : distributed in a spatial region. I did a google : search and found something like Kolmogorov-Smirnov goodness-of-fit test. My : question is: what is the : computational complexity of running this test in terms of the number of : points N? Are there any C libraries : that implemented this? Links to a tutorial of such tests will also be : appreciated. Thanks.
| l******e 发帖数: 470 | 3 I don't think this is a good test.
just by a similar argument of coupon collector problem, only 1-1/e grid will
be nonempty if the distr is truly uniform. One the other hand a lot of other
weird distr will behave the same way.
One way is to throw NlogN point and test whether each grid has (1+-\epsilon)
logN
points, If it is uniform ,then this should happen w.h.p.
However, I don't this is standing on a solid ground neither. you need
Goodness-of-Fit Test type of stuff.
)x
than
some
making
【在 s*****g 的大作中提到】 : I do not know this test but I know another test that works nicely. : Supposed you have N points in the 3D unit cube. Make a sqrt(N,3)x sqrt(N,3)x : sqrt(N,3) grid in the unit cube. Test how many grid cube contains more than : 1 points and how many contains no point, if this number is higher than some : thresh hold (very low but I forget - can be done through a learning using : Bayesian decision rule), you will see the uniformity of the points by making : use of the geometry information. : This can extend to n
| s*****g 发帖数: 5159 | 4 You are right. My algorithm needs further refinement. It was a small course
project I did years ago and I could only remember a framework.
The reason we introduce a grid metric is that we need to use the geometry
information, rather than vectors with independent dimensional components.
will
other
epsilon)
【在 l******e 的大作中提到】 : I don't think this is a good test. : just by a similar argument of coupon collector problem, only 1-1/e grid will : be nonempty if the distr is truly uniform. One the other hand a lot of other : weird distr will behave the same way. : One way is to throw NlogN point and test whether each grid has (1+-\epsilon) : logN : points, If it is uniform ,then this should happen w.h.p. : However, I don't this is standing on a solid ground neither. you need : Goodness-of-Fit Test type of stuff. :
|
|
|
|
|
|
|