# Defining an n-dimensional orthogonal basis set

I have a set of n-dimensional points. I am performing clustering analysis on them to partition them into groups. Now, I would like to find a basis set to be able to describe the layout of the groups' borders.

For example, if my points were only three dimensional, then I could easily use spherical harmonics to describe the groups. If there are, say, five groups then each group can be written as a linear combination of spherical harmonics, and I can easily define the borders of each group.

I cannot, however, use spherical harmonics on, for example, a five dimensional set of points, can I? If not, is there a family of basis sets that can define shapes in n-dimensions?

• Note that even in three dimensions spherical harmonics would only constrain your groups in the two angular coordinates...you would still need to constrain the radial coordinate (unless you data is confined to lie on a shell of some kind). – dmckee --- ex-moderator kitten Mar 24 '12 at 18:13
• Maybe you can use a spherical equivalent of a k-d tree... Actually, it's called a v-p tree. – Paul Mar 24 '12 at 19:21
• What's wrong with the convex hull of your groups? – Deathbreath Mar 27 '12 at 16:14
• @Deathbreath huh? – Laurbert515 Mar 28 '12 at 17:55
• What clustering algorithm are you using? – Emre May 10 '12 at 23:08

I am sorry to answer with a question here, but it seems I cannot comment your question as others did.

I am not fully understanding what you mean by "borders" of the groups. What exactly do you mean? As I understand it, if each cluster is a cloud of points, then you could get the principal axis of that cloud (SVD, PCA, moment of inertia, you name it) and build the smallest ellipsoid (this may not enclose the points but it will be a more or less nice description of their size).

If you really want something enclosing the clouds then you can use the convex-hull as somebody suggested above or if you want non-convex borders you can get the alpha-shape of the clouds. I do not know many implementations of alpha-shapes: CGAL or the equivalent in MATLAB (it is using CGAL code, but I do not know since which version). I wouldn't know any implementation of alpha-shapes for more than 3 dimensions, not even know whether that is possible, but I guess it should. A link is in order, here is the 2D alpha-shape in CGAL

• my shapes have incredibly strange shapes. imagine a cloud looking like mickey mouse, a cloud looking like various tetris objects, a shape looking like a hand (these shapes are not necessarily seen, but they explain the strange shapes which cannot remotely be described by an ellipsoid or any other simple shape) – Laurbert515 Apr 29 '12 at 19:29
• @JuanPi: If you have questions about the OP's post, you need to ask on the comment section above; not as part of your answer. – Paul May 12 '12 at 14:05
• @Paul: now I know thank you. I also think that at the time of that answer I couldn't comment. Can that be possible? – JuanPi May 16 '12 at 10:59
• @Laubert515: Did you check alpha shapes in CGAL? They are for "weird" shapes as th eone you are mentioning. Also, maybe the scale axis transform may help you, but again, I do not know if it is already extended for more dimensions. – JuanPi May 16 '12 at 11:02

Well, spheres exist in arbitrary dimensions.

In 1d, they are intervals. In 2D they're circles. In 3D they're the obvious sphere. But there exist hyperspheres in arbitrary dimensions.

They also exist for other distance functions. Consider a sphere to be defined as the set of points $x$ with $d(o,x) \{<,=,\leq\} r$ depending on which kind of sphere you want (hollow, etc).

Quoting Wikipedia:

The classical spherical harmonics are defined as functions on the unit sphere $S_2$ inside three-dimensional Euclidean space. Spherical harmonics can be generalized to higher dimensional Euclidean space $R^n$ as follows. [...]

• It may help to know that spherical harmonics are just another orthogonal basis for the Hilbert space of $L^2$ functions. (They are adapted to conform to irreducible representations of the orthogonal group.) One could just as easily (and effectively) choose Fourier series, orthogonal polynomials, etc. What this shows is that the question really isn't well-posed: precisely what kind of "description" of the clusters is being sought here? – whuber Jun 11 '12 at 19:53