1

I'm trying to implement K-means clustering algorithm on 600 data points, all with 60 dimensions. A line of input would be something like:

28.7812 34.4632 31.3381 31.2834 28.9207 33.7596 25.3969 27.7849 35.2479 27.1159 32.8717 29.2171 36.0253 32.337  34.5249 32.8717 34.1173 26.5235 27.6623 26.3693 25.7744 29.27   30.7326 29.5054 33.0292 25.04   28.9167 24.3437 26.1203 34.9424 25.0293 26.6311 35.6541 28.4353 29.1495 28.1584 26.1927 33.3182 30.9772 27.0443 35.5344 26.2353 28.9964 32.0036 31.0558 34.2553 28.0721 28.9402 35.4973 29.747  31.4333 24.5556 33.7431 25.0466 34.9318 34.9879 32.4721 33.3759 25.4652 25.8717

I'm thinking have a struct of data points, where it has a vector of attributes, like

struct Point{
    std::vector<double> attributes;
};

and I guess when iterating through all the points, add up the attributes with i as an iterator in a for loop? Is this the best way to go about this?

8
  • 5
    2 power 60 is already a lot. Are you sure to have 60 dimensions, or do you just have a one-dimensional vector of about 60 elements?, or a reasonable vector of 60-tuples? Nov 30, 2015 at 15:04
  • 1
    You may have std::array<double, 60> instead of vector. But vector is fine too.
    – Jarod42
    Nov 30, 2015 at 15:06
  • 1
    This isn't really 60 dimensions so much as 2 dimensions, 600x60. The answer sort of depends on how arbitrary the data is. If you can, you should make it a vector of structs (with proper named elements). If it's arbitrary, just make a vector of vectors of doubles.
    – user3995702
    Nov 30, 2015 at 15:09
  • 1
    @BasileStarynkevitch (and all those apparently agreeing with that flawed comment): The word "dimension" has more shades of meaning than your comment allows. In this question, 60 dimensions obviously does not mean anything like a C++ many dimensional data structure. Imagine the word "dimension" in the original had been some other word ("coordinate" or "direction" or "attribute" or whatever). Then you would easily understand this request for 600x60 values.
    – JSF
    Nov 30, 2015 at 15:14
  • 1
    @JSF: Just storing it is easy. However, that means that finding is an O(N) operation. If you want a better than O(N) lookup, you need lots of associated data.
    – MSalters
    Nov 30, 2015 at 15:35

2 Answers 2

5

Not sure about what you are asking, but with C++11 you could use std::array so you might have some

 std::vector<std::array<double,60>> myvec;

Then myvec[2] and myvec[10] (assuming myvec.size() > 10) are both elements of type std::array<double,60> so you can of course use myvec[2][7] and myvec[10][59]

1

600 data points is a small enough number. Looking up distances in 60 dimensional space, for 600 points is about 36.000 operations. That's manageable.

Keep in mind that your data is very, very sparse though. A more realistic data set for 60 dimensions would have far, far more points. In that case you might need to think about pre-partioning space. That would complicate your data structure.

One intermediate-level technique is to realize that distances only add up. When looking for a neighbor of point P, you need to calculate the distance to the first point in 60 dimensions. This establishes a lower bound D. But when you calculate the distance to the second point, you may find that you exceed D already after 59 dimensions. Now the tricky bit is that you cannot check this for every point after adding every dimension; that would be excessive. You may need to manually unroll loops, and exactly how depends on your data distribution.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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