<div dir="ltr"><div class="gmail_default" style="color:rgb(11,83,148)">Hi Richhiey<br><br></div><div class="gmail_default" style="color:rgb(11,83,148)">Usually, a corpus easily would have around a few hundred thousands of terms. As you have already identified the vectors are sparse i.e. a few tens or hundred entries would be non-zero. One common optimisation is to store only non-zero entries. You can use, for example, an unorderd set to store those entries. In order to store more information for each entry e.g. frequency of the term, you can store a custom object in the unordered set and use it while computing the distance.<br><br></div><div class="gmail_default" style="color:rgb(11,83,148)">Now, centroids are usually initialised by some algorithm or randomly and they can be dense. Let's calculate the in-memory storage for our clustering project. Let's say our k=10 (in practice it can be smaller) and our vocabulary size is 1M. To host these centroids into main memory, we would need 10*10^6*8 bytes which is around 80MB. If you compromise on precision and choose single-precision float then you can store them with 40MB.<br><br></div><div class="gmail_default" style="color:rgb(11,83,148)">Now let's consider you want to perform one iteration of k-means with 30 documents. If you store them in dense format you need 240 MB which is still not bad but can be worse if you want to cluster 50 documents and also the collection is huge (a few millions vocabulary size). In this case, if you consider standard k-means where your distance metric is euclidean, it is very risky because centroid entries in the zero positions of the vectors also contribute to the distance. Moreover, the vectors are sparse which can highly influence the score. Hence, you should consider to use spherical k-means which uses cosine distance. Now you can store document vectors in sparse format because zero entries do not contribute to the distance metric. <br><br></div><div class="gmail_default" style="color:rgb(11,83,148)">In case you choose dense format, there are BLAS libraries which have optimised implementation of L2 norm.<br><br></div><div class="gmail_default" style="color:rgb(11,83,148)">Cheers<br></div><div class="gmail_default" style="color:rgb(11,83,148)">Parth<br></div><div class="gmail_default" style="color:rgb(11,83,148)"><br></div><div class="gmail_default" style="color:rgb(11,83,148)"><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 26, 2016 at 10:18 AM, Richhiey Thomas <span dir="ltr"><<a href="mailto:richhiey.thomas@gmail.com" target="_blank">richhiey.thomas@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">Hello,</p>
<p dir="ltr">I've been working on the KMeans clustering algorithm recently and since the past week, I have been stuck on a problem which I'm not able to find a solution to.</p>
<p dir="ltr">Since we are representing documents as Tf-idf vectors, they are really sparse vectors (a usual corpus can have around 5000 terms). So it gets really difficult to represent these sparse vectors in a way that would be computationally efficient to calculate euclidian distances. I had implemented a K-Medioids algorithm using PAM just to try it out, after modifying the API for whatever more was required, and that seems fine, since we are dealing with document vectors and not arbitrary vectors. But with KMeans, I am not able to figure out how to represent these centroids during each iteration when the average of a cluster is to be computed. <br>
So my confusion is, how could i represent an arbitrary sparse vector to be used as the centroid in k means?<br>
Can anyone please guide me on this?<br>
Will using boost C++ be a solution?</p>
<p dir="ltr">Thanks<br>
</p>
</blockquote></div><br></div>