<p>What you can do, you can leverage results of <a href="https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma" rel="nofollow noreferrer">Johnson-Lindenstrauss lemma</a> where you embed you dataset into lower dimension space and when doing the kmeans computation on smaller dataset. For instance if you data matrix is A you can do:</p>

<pre><code>% N is the number of data points and s is the reduced dimension
S  =  randn (N, s)/s q r t (s) ;
C  =  A ∗ S ;

% now you can do you kmeans computation on C
[idx, ctr] = kmeans(MeansOfK , k, 'Distance', 'sqEuclidean');
</code></pre>

<p>Basically you can use <code>idx</code> and <code>ctr</code> results for original dataset which will give you (1+epsilon) approximation. Also you can reach better results based on work by <a href="https://pdfs.semanticscholar.org/1e76/727be351d6289311d9d1d65c494a683ace0f.pdf" rel="nofollow noreferrer">Dan Feldman</a> which basically says that you can compute and SVD on your data and project on k/epsilon engine values to compute the kmeans value and get (1+epsilon) approximation.</p>

<p><hr />
<strong>UPDATE</strong></p>

<p>Based on comment I'd like to suggest to leverage coresets approach, again based on the paper of Dan Feldman at el, <a href="https://pdfs.semanticscholar.org/1e76/727be351d6289311d9d1d65c494a683ace0f.pdf" rel="nofollow noreferrer">Turning Big Data Into Tiny Data</a>. The techniques provides with capability to reduce large volume of data into smaller with provable guarantee to provide (1+epsilon) approximation to the optimal kmeans solution. Moreover you can proceed with streaming coreset construction which will allow you to maintain <code>O(logn * epsilon)</code> approximation while streaming you data (section 10, figure 3), e.g. in your case partition into smaller chunks. When eventually you can run kmeans computation on the resulted coreset. </p>

<p>Also you probably might consider to take a look into my recent <a href="https://arxiv.org/pdf/1511.08990.pdf" rel="nofollow noreferrer">publication</a> to get more details on how to handle your case. Here you can find also a reference in my <a href="https://github.com/C0rWin/KMeanCoreset" rel="nofollow noreferrer">github account</a> if you'd like to use it.</p>
K-Means Clustering Paritioning
<p>I am using matlab and i have this very very big .mat file named MeansOfK that contains almost 5,000,000 x N. My test data consists of Car and Non-car. My problem is that when i try to use k-means to the MeansofK. It always runs out of memory. </p>

<pre><code>[idx, ctr] = kmeans(MeansOfK , k, 'Distance', 'sqEuclidean');
</code></pre>

<p>My Options are</p>

<p>1.i use the divide and conquer technique wherein i partition the car and non-car to smaller partitions and put it into k-means. </p>

<p>2.I separate the car and non-car classes and try to use k-means to both classes. </p>

<p>the final output would be the combined classes of car or non-car. from the k-means process. </p>

<p>so my question is?</p>

<p>Is what i will be doing feasible? 
Will it affect the output of my k-means if i partition the file rather than doing it as a whole? </p>

<p>Suggestions and answers are always appreciated :) 
Thanks</p>