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