1
$\begingroup$

I want to partition some 2d points into 2 groups (clustering). The way that I need to do it is by using PCA to find the first principle component. Then I project the data to find 1d projections. Then I find the middle point on the principal component and partition the 2d points based on the indexes of point on each side of the middle point.

How can I find the line which separates the data into 2 partitions in 2D space? in 1d projected space the partition line is the one perpendicular to the first principal component that passes through the middle point.

Is the line in 2d space unique? Is it possible to compute the best line if it is not unique?

Note: I am actually doing hierarchical clustering with first component of PCA. I want to check the performance of this method against k-d tree.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

PCA is not always unique. Implementations may be stable though in returning the same result.

Consider a data set that is perfectly i.i.d. - this will yield a covariance matrix that is a multiple of the identity matrix. Any vector of unit length is an eigenvector there - thus, not unique.

The orthogonal space of a vector is easy to describe. In 2d it is also easy to explain as line.

I do not think it makes sense to reduce 2d to 1d for HAC.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is just for an experiment to see how the results differ from that of a k-d tree. $\endgroup$
    – Ash
    Commented Apr 21, 2015 at 23:51
0
$\begingroup$

I used PCA to represent 2d in 1d then I found the median of the points and partitioned the data based on that point in 1d (if the median was like 0.5 all the points less than 0.5 are in partition1 and all the points more than or equal to 0.5 are in partition2).

To find the line I use the scikit-learn's pca.component_ property and set the slope of the partitioning line to slope = -pca_component[0,1] / pca_component[0,0]

We have the slope and a point (median point's index) so we can pass a partitioning line between points in 2d.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It would probably make more sense to use the mean instead of the median with PCA - because PCA centers your data on the mean. But if you cluster on the reduced 1d data set eith hierarchical clustering, it does not make a difference (except you don't need to find the median - the mean is at 0 after PCA) $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Apr 22, 2015 at 1:06
  • $\begingroup$ Yes but my goal is to have equal number of points in each partition. The final goal is to have several partitions with equal sizes. $\endgroup$
    – Ash
    Commented Apr 22, 2015 at 1:22

Your Answer

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

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