computing complexity of kmeans algorithm -


i want compute complexity of kmeans algorithm based on complexity theory.

i have read standard algorithm of kmeans wikipedia: link

if (you haven't understood k-means) http://home.deib.polimi.it/matteucc/clustering/tutorial_html/kmeans.html

else

initialize means (e.g. picking k samples @ random)

• iterate: (i times)

(1) assign each point nearest mean

(2) move “mean” center of cluster.

(3) finally, algorithm aims @ minimizing objective function, in case squared error function. objective function has complexity of kn see definition.if there m attributes (in place of normal euclidean function time in calculating objective function proportional m)

time complexity of k-means

• let tdist time calculate distance between 2 objects

• each iteration time complexity: o(kntdist)

k = number of clusters (centroids)  n = number of objects

• bound number of iterations giving o(ikntdist)

• m-dimensional vectors: o(iknm) ----------------> answer

( m large , centroids not sparse )

space complexity of k-means

• store points , centroids

– vector model: o((n + k)m)---------------------->space complexity


Comments

Post a Comment

Popular posts from this blog

javascript - Jquery show_hide, what to add in order to make the page scroll to the bottom of the hidden field once button is clicked -

i have button on website when clicked, reveals map. button can seen when page first loads up, when clicked, section holding map slides open , goes out of screen since page loads @ top (normal). want page scroll down bottom of div select when button pushed, if map out of screen. if page scrolled down, , clicks show map button, don't want page jump bottom of map. i tried figure out myself, no luck. seasoned jquery coders able give me guidance? many thanks! map = mapdiv.gmap3("get"); infobox = new infobox({ pixeloffset: new google.maps.size(-220, -310), closeboxurl: '', enableeventpropagation: true }); mapdiv.delegate('.infobox .close','click',function () { infobox.close(); }); jquery(".slidingdiv").hide(); jquery(".show_hide").show(); jquery('.show_hide').click(function(){ lastcenter=map.getcenter(); jquery(".slidingdiv&quo
Read more

javascript - Highcharts multi-color line -

Image
i looking create highchart multi-colored line. if goes down under value, become red, , when comes on value, become green . here picture example: or maybe highcharts have other charts models differentiate high or low level color? you can achieve coloring using lineargradient coloring: color: { lineargradient: { x1: 0, x2: 0, y1: 0, y2: 1 }, stops: [ [0, 'red'], [0.25, 'yellow'], [0.50, 'green'], [0.75, 'yellow'], [1, 'red'] ] } here 0 in stops relates minimum value of series , 1 maximum value, , in between percentages between values. if find percentages according values prior creating chart use correct stops values make relate specific values in data (at least approximately). see this jsfiddle example .
Read more

javascript - Enter key does not work in search box -

tried search guys sorry. input in search box doesnt work (or search) when hit enter when user clicks search button. doing wrong? here code. thanks. <script type="text/javascript"> $(document).ready(function() { $("#submit").click(function() { var url = "http://asla.org/awardssearch.html"; url += "?s=" + $('#googlecse').val(); window.location = url; }); $('#googlecse').keydown(function(event) { if (event.keycode == '13') { $("#submit").click(); } else { //do nothing :) } }); }); </script> <form class="navbar-form navbar-right" role="search"> <div class="search"> <input id="googlecse" type="text" onblur="if(this.value=='')this.value=this.defaultvalue;" onfocus="if(this.value==this.defaultvalue)t
Read more