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.

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ It is just for an experiment to see how the results differ from that of a k-d tree. $\endgroup$ – Ash Apr 21 '15 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.

$\endgroup$
  • $\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$ – Anony-Mousse Apr 22 '15 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 Apr 22 '15 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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