29
$\begingroup$

I have a matrix where a(i,j) tells me how many times individual i viewed page j. There are 27K individuals and 95K pages. I would like to have a handful of "dimensions" or "aspects" in the space of pages which would correspond to sets of pages which are often viewed together. My ultimate goal is to then be able to compute how often individual i has viewed pages that fall in dimension 1, dimension 2, etc.

I have read the R documentation on principal component analysis and single value decomposition and have executed these commands, but I am unsure how to proceed.

How can I use dimensionality reduction to do this? Or is this really a clustering problem and I should instead look into clustering algorithms?

Many thanks for any insight ~l

$\endgroup$

4 Answers 4

12
$\begingroup$

Lets assume mat_pages[] contains pages in the columns (which you want to cluster) and individuals in the rows. You can cluster pages based on individual data in Rby using the following command:

  pc <- prcomp(x=mat_pages,center=TRUE,scale=TRUE)

The loadings matrix is the matrix of eigenvectors of the SVD decomposition of the data. They give the relative weight of each PAGE in the calculation of scores. Loadings with larger absolute values have more influence in determining the score of the corresponding principle component.

However, I should also point out the short coming of using PCA to cluster pages. The reason for this is that loadings give larger weights to the PAGES with higher variation, regardless of whether this variation is actually because of the PAGE content or some other reason (may be technical or individual variation). The loadings do not necessarily reflect the true differences between groups, which (maybe) your main interest. BUT, this clustering truly reflects the differences in the group under the assumption that all the pages have same variance (I don't know if this is a valid assumption).

If you have a powerful computing facilities (which may be possible given your data size) - using hierarchical models may be a good idea. In R, it can be done using lme4 package.


What do do after you have the scores?

This is a crude suggestion and the analysis depends greatly on how the data looks like. Also, I would guess this process would be highly infeasible to group the data of magnitude that you have.

pc.col <- paste("page", 1:27000, sep=".")

pdf("principle-components.pdf")
plot(pc$x[,1:2]) ## Just look at the 1st two loadings (as you can see the groupings in a plane)
dev.off()

Hopefully, this can give you a picture of how the data is grouped into.

Warning: this is not what I would recommend.


My recommendation:

Problems like these arise frequently in genomics.In your case pages corresponds to genes and individuals corresponds to patients (basically individuals is has the same meaning as in genomics)

You want to cluster the pages based on data.

You can use a lot of clustering packages in R and have been pointed in other answers. A fundamental problem with packages is like hclust is how to determine the number of clusters. A few of my favorite ones are:

  • pvclust (Gives you clusters and also gives a p-value for each cluster. Using the p-value you can determine the statistically significant clusters. Problem: requires a lot of computational power and I am not sure if it will work with data of your size)
  • hopach (Gives you the estimated number of clusters, and the clusters)
  • there are other packages available in Bioconductor, please check them out in the task view.

You can also use clustering algos like k-means etc. I am sure I saw a thread in this forum about clustering. The answers were very detailed. It was asked by Tal Galili if I remember correctly.

$\endgroup$
11
  • $\begingroup$ @suncoolsu: many thanks! I have just followed your advice and ran prcomp. I also stored the loadings matrix it produced. But how can I use this matrix to group together the pages? $\endgroup$ Sep 26, 2010 at 23:00
  • $\begingroup$ Hello Laramichaels, please find my answer below. $\endgroup$
    – suncoolsu
    Sep 28, 2010 at 4:05
  • $\begingroup$ @suncoolsu: I am dealing with a similar problem, but I want to "cluster" the individuals that have the same "dynamics" (actually I have a huge number of timeseries per regions and I want to model them). I was thinking to use pam with the correlation distance (1-rho). Is this a recommended way? Could you please suggest some paths to explore? $\endgroup$
    – teucer
    Sep 28, 2010 at 19:59
  • $\begingroup$ @Musa .. Can you be bit clearer. I don't think I understand the "dynamics" mentioned by you. Definitely pam is OK for clustering. But you can also try the R packages pvclust and hopach as mentioned by me. Also, SOM (self organizing maps) are a different way of looking at clustering. Please see Ripley and Venable (2002) book - MASS for further details. The book offers a thorough treatment of clustering. $\endgroup$
    – suncoolsu
    Sep 29, 2010 at 0:26
  • $\begingroup$ @suncoolsu: Sorry for the poor formulation! I have 200 timeseries that I want to model (i.e. to simulate). I think that I can cluster "similar" (i.e. having the same behavior over time: the straight forward approach is to use the correlation) timeseries and simulate only the cluster timeseries... $\endgroup$
    – teucer
    Sep 29, 2010 at 6:57
4
$\begingroup$

It is certainly a clustering problem. Check out Rs cluster package to get an overview of algorithm options (pam and agnes are the best options to start; they represent two main streams in clustering -- centroids and hierarchical).
The main problem to use clustering on your data is to define a good similarity measure between pages; simple one is to use Manhattan distance; a bit more complex to count the number of common viewers and normalize it with, let's say, mean of number of viewers of the first and second page -- this should silence popularity effects.

EDIT: Ok, now I've saw the data size... it will probably make R explode, since it needs one triangle of $(\text{number of pages})\times(\text{number of pages})$ matrix to store distances. Check out this report for possible solutions.

$\endgroup$
2
  • $\begingroup$ I upvoted your answer. However, could you please provide the new links for the report in the last sentence. The old one is dead. $\endgroup$
    – discipulus
    Apr 15, 2015 at 8:56
  • 1
    $\begingroup$ I'm afraid its lost forever... Generally it was about implementations of clustering methods which does not explicitly build each-to-each similarity matrix but investigate objects on demand. $\endgroup$
    – user88
    Apr 15, 2015 at 16:22
1
$\begingroup$

Dimensionality reduction is basically applying clustering algorithm to the attributes (columns). Because of the fairly large dimensionality of your dataset, you might try to use SOM (self-organizing map/Kohonen net) to create a map for individuals or pages. You can then seen whether the are meaningful (interpretable) patterns.

$\endgroup$
1
$\begingroup$

If you do PCA, my advice would be to briefly screen other components than only the first two. Once you have the prcomp object pc (see suncoolsu's post), you can plot(pc) to see the amount of variance attributed to the different principal components. You can also easily visualise several (usually three or four) of them with pairs(pc$x[,1:3]) or, using lattice, splom(pc$x[,1:3]).

$\endgroup$

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.