Saturday, February 16, 2013

Algorithm Analysis: The Basic K-means Clustering Algorithm


The basic k-means clustering algorithm is a simple algorithm that separates the given data space into different clusters based on centroids calculation using some proximity function. Using this algorithm, we first choose the k- points as initial centroids and then each point is assigned to a cluster with the closest centroid. The algorithm is formally described as follows:
Input: A data set D containing m objects (points) with n attributes in an              Euclidean space
Output: Partitioning of m objects into k-clusters C1, C2, C3, …, Ck, i.e. Ci D and Ci ∩ Cj = ᶲ  (for 1 ≤ i, j ≤ k)


Procedure:

  1. Select k points as initial centroid
  2. Repeat
  3. Form k clusters by assigning each point to its closest centroid
  4.  Re-compute the centroid of each cluster
  5. Until the centroids don’t change

Time Complexity of the algorithm:

 To analyze the complexity of the algorithm in terms of time required, we need to identify the operations required in each step and in each iteration of the algorithm. Here, for k-means algorithm, the operations for each iteration are:
  • Calculation of distances: To calculate the distance from a point to the centroid, we can use the squared Euclidean proximity function. For this, we need two subtractions, one summation, two multiplications and one square - root operations, i.e., 6-operations.
  • Comparisons between distances
  • Calculation of centroids

So, the total number of operations for an iteration
= distance calculation operations + comparison operations + centroids calculation operations
= 6*[k*m*n] operations + [(k-1)*m*n] operations + [k*((m-1) + 1)*n] operations

Assume that the algorithm converges after I iterations, then total number of operations for the algorithm
= 6*[I*k*m*n] operations + [I*(k-1)*m*n] operations + [I*k*((m-1) + 1)*n] operations
= [6Ikmn + I(k-1)mn + Ikmn] operations
≈ O (I*k*m*n)

Here, we’ve applied the basic assumption of each operation requiring the same amount of time. Since, normally, k << m & n << m, the analysis shows that the k-means is linear in m, the number of points, and is scalable and efficient in processing large data sets.

Space Complexity of the Algorithm:

The space requirement for k-means are modest because only the data points and centroids are needed to be stored. Specifically, the storage required is O((m+k)n), where m is the number of objects (points) & n is the number of attributes considering n-dimensional objects.

References
[1] Vipin Kumar, Pang-Ning Tan & Michael Steinbach.(2005). "Introduction to Data Mining." Pearson/Addison Wesley, ISBN 0-321-32136-7.

181 comments:

  1. I believe there are many more pleasurable opportunities ahead for individuals that looked at your site.

    big data training in chennai

    ReplyDelete
  2. Very interesting blog post.Quite informative and very helpful.This indeed is one of the recommended blog for learners.Thank you for providing such nice piece of article. I'm glad to leave a comment. Expect more articles in future. You too can check this R Programming tutorial for updated knowledge on R Programming.
    https://www.youtube.com/watch?v=gXb9ZKwx29U

    ReplyDelete
  3. Thank you for sharing such valuable information and tips. This can give insights and inspirations for us; very helpful and informative! Would love to see more updates from you in the future.
    Big Data Training in Chennai
    Big Data Training
    Loadrunner Training in Chennai
    iOS Training in Chennai
    Selenium Training in Chennai
    Selenium Training

    ReplyDelete
  4. I am really enjoying reading your well written articles.
    It looks like you spend a lot of effort and time on your blog.
    I have bookmarked it and I am looking forward to reading new articles. Keep up the good work..
    IELTS Coaching in Chennai
    IELTS Classes in Mumbai
    IELTS Training in Chennai
    IELTS Coaching Centre in Chennai
    IELTS Center in Mumbai
    Best IELTS Coaching in Chennai

    ReplyDelete
  5. Thank you for sharing such great information with us. I really appreciate everything that you’ve done here and am glad to know that you really care about the world that we live in.
    Big Data Course in Chennai
    Big Data Hadoop Training in Chennai
    Hadoop Course in Chennai
    best big data training in chennai
    Big Data Hadoop Training
    Hadoop Training in Chennai

    ReplyDelete
  6. Awwsome informative blog ,Very good information thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.
    Aviation Academy in Chennai | Aviation Courses in Chennai | Best Aviation Academy in Chennai | Aviation Institute in Chennai | Aviation Training in Chennai

    ReplyDelete
  7. Awwsome informative blog ,Very good information thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.
    Airport Ground Staff Training Courses in Chennai | Airport Ground Staff Training in Chennai | Ground Staff Training in Chennai

    ReplyDelete
  8. Nice idea,keep sharing your ideas with us.i hope this information's will be helpful for the new learners.
    Best AWS Training in Bangalore
    AWS Training in Nolambur
    AWS Training in Ashok Nagar

    ReplyDelete
  9. Outstanding blog thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.
    Air Hostess Training in Chennai | Air Hostess Training Institute in Chennai | Air Hostess Academy in Chennai
    Air Hostess Courses in Chennai |Best Air Hostess Training Institute in Chennai | Cabin Crew Course in Chennai

    ReplyDelete
  10. More informative,thanks for sharing with us.
    this blog makes the readers more enjoyable.keep add more info on your page.
    angularjs classes in bangalore
    angularjs tutorial in bangalore
    AngularJS Training in Mogappair
    AngularJS Training in Nungambakkam

    ReplyDelete
  11. Your blog is so inspiring for the young generations.thanks for sharing your information with us and please update more new ideas.
    Cloud Computing Training in Kelambakkam
    Cloud Computing Training in Amjikarai
    cloud computing courses near me
    Cloud computing institutes in Bangalore

    ReplyDelete
  12. Only here are good game slots the casino best Come to us and get your winnings.

    ReplyDelete
  13. Качественный декоративный алюминиевый led профиль я обычно беру в компании Ekodio, советую.

    ReplyDelete
  14. There was a time when it was difficult with money. I decided to turn to gambling for all kinds of slot machines and the like. Now knowing this site splendid casino games online for money across and opposite to me is no longer scary

    ReplyDelete
  15. Great Article ,Great blog! lot of valid information.
    Keep sharing more.
    www.apponix.com

    ReplyDelete
  16. Great Article ,Great blog! lot of valid information.
    Keep sharing more.
    JAVA Tutorials

    ReplyDelete
  17. This is really too useful and have more ideas and keep sharing many techniques. Eagerly waiting for your new blog keep doing more.
    Regards,
    Tableau training in Chennai | Tableau Courses Training in Chennai | Tableau training Institute in Chennai

    ReplyDelete
  18. This comment has been removed by the author.

    ReplyDelete
  19. This comment has been removed by the author.

    ReplyDelete
  20. Great blog thanks for sharing Looking for the best creative agency to fuel new brand ideas? Adhuntt Media is not just a digital marketing company in chennai. We specialize in revamping your brand identity to drive in best traffic that converts.

    ReplyDelete
  21. Nice blog thanks for sharing Set up a aesthetic work environment that employees love to spend time in and relieve their stress. Your company needs the best corporate gardening service in Chennai and Karuna Nursery Gardens in happy to oblige you in the endeavour to make your infrastructure something worth flaunting about.

    ReplyDelete
  22. Excellent blog thanks for sharing Run your salon business successfully by tying up with the best beauty shop in Chennai - The Pixies Beauty Shop. With tons of prestigious brands to choose from, and amazing offers we’ll have you amazed.

    ReplyDelete
  23. Awesome blog thanks for sharing While choosing your perfect ride for driving, Accord Cars comes with and the best packages for you to pick from. Car rentals for self drive in Chennai are done the easier. Just pick out your plan from hourly, daily, weekly and even monthly plans available.

    ReplyDelete
  24. Very useful blog thanks for sharing With over a three decade of beauty expertise at our fingertips, we believed that everyone has the right to be beautiful. And so began the journey of our very own Pearl’s Beautician course in Chennai.

    ReplyDelete
  25. Awesome blog thankks for sharing 100% virgin Remy Hair Extension in USA, importing from India. Premium and original human hair without joints and bondings. Available in Wigs, Frontal, Wavy, Closure, Bundle, Curly, straight and customized color hairstyles Extensions.

    ReplyDelete
  26. Very useful blog thanks for sharing IndPac India the German technology Packaging and sealing machines in India is the leading manufacturer and exporter of Packing Machines in India.

    ReplyDelete
  27. A IEEE project is an interrelated arrangement of exercises, having a positive beginning and end point and bringing about an interesting result in Engineering Colleges for a particular asset assignment working under a triple limitation - time, cost and execution. Final Year Project Domains for CSE In Engineering Colleges, final year IEEE Project Management requires the utilization of abilities and information to arrange, plan, plan, direct, control, screen, and assess a final year project for cse. The utilization of Project Management to accomplish authoritative objectives has expanded quickly and many engineering colleges have reacted with final year IEEE projects Project Centers in Chennai for CSE to help students in learning these remarkable abilities.



    Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining the authors explore the idea of using Java in Big Data platforms.
    Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai

    ReplyDelete
  28. Great information to say the least. I really do appreciate everything so much from this great article.
    qr code generator

    ReplyDelete
  29. keep up the good work. this is an Assam post. this to helpful, i have reading here all post. i am impressed. thank you. this is our digital marketing training center. This is an online certificate course
    digital marketing training in bangalore / https://www.excelr.com/digital-marketing-training-in-bangalore

    ReplyDelete
  30. We as a team of real-time industrial experience with a lot of knowledge in developing applications in python programming (7+ years) will ensure that we will deliver our best in python training in vijayawada. , and we believe that no one matches us in this context.

    ReplyDelete
  31. Really impressed! Everything is very open and very clear clarification of issues. It contains truly facts. Your website is very valuable. Thanks for sharing.
    Please check this ExcelR Pune Digital Marketing Course

    ReplyDelete
  32. Data Science Courses
    It's really nice and meaningful. it's really cool blog. Linking is very useful thing. You have really helped lots of people who visit blog and provide them useful information.

    ReplyDelete
  33. Thanks for sharing this informations.
    data science course in coimbatore

    data science training in coimbatore

    android training institutes in coimbatore

    ios training in coimbatore

    aws training in coimbatore

    amazon web services training in coimbatore

    big data training in coimbatore

    ReplyDelete
  34. This was really one of my favorite website. Please keep on posting. ExcelR Digital Marketing Course Pune

    ReplyDelete
  35. I personally think your article is fascinating, interesting and amazing. I share some of your same beliefs on this topic. I like your writing style and will revisit your site.
    Best Data Science training in Mumbai

    Data Science training in Mumbai

    ReplyDelete
  36. I really enjoyed your blog Thanks for sharing such an informative post.

    digital marketing course in hubli

    ReplyDelete
  37. I'm not one of those readers that comments on articles often, but yours really compelled me. There's a lot of interesting content in this article that is interesting and bold.
    SAP training in Kolkata
    SAP training Kolkata
    Best SAP training in Kolkata
    SAP course in Kolkata
    SAP training institute Kolkata

    ReplyDelete
  38. Such a very useful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.

    Big Data Online Training

    Big Data Classes Online

    Big Data Training Online

    Online Big Data Course

    Big Data Course Online

    ReplyDelete
  39. Very interesting blog Thank you for sharing such a nice and interesting blog and really very helpful article.

    Sap Ariba Online Training

    Sap Ariba Classes Online

    Sap Ariba Training Online

    Online Sap Ariba Course

    Sap Ariba Course Online

    ReplyDelete
  40. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Correlation vs Covariance
    Simple linear regression
    data science interview questions

    ReplyDelete
  41. Excellent Blog! I would like to thank for the efforts you have made in writing this post. I am hoping the same best work from you in the future as well. I wanted to thank you for this websites! Thanks for sharing. Great websites!

    Simple Linear Regression

    Correlation vs Covariance

    ReplyDelete
  42. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Correlation vs Covariance
    Simple linear regression
    data science interview questions

    ReplyDelete
  43. Nice information, valuable and excellent design, as share good stuff with good ideas and concepts, lots of great information and inspiration, both of which I need, thanks to offer such a helpful information here....
    hardware and networking training in chennai

    hardware and networking training in tambaram

    xamarin training in chennai

    xamarin training in tambaram

    ios training in chennai

    ios training in tambaram

    iot training in chennai

    iot training in tambaram

    ReplyDelete
  44.  Being a travel blogger and lover, it was appealing and helpful for me. It is a strong article to portray this topic limits the readers to widen their horizon of accepted wisdom and power as they go through the article.
    SAP training in Kolkata
    SAP training Kolkata
    Best SAP training in Kolkata
    SAP course in Kolkata

    ReplyDelete
  45. The content is well acknowledged, so no one could allege that it is just one person's opinion yet it covers and justifies all the applicable points. I have read such a startling work after a long time!
    Data Science training in Mumbai
    Data Science course in Mumbai
    SAP training in Mumbai

    ReplyDelete
  46. Thank you for excellent article.You made an article that is interesting.
    Rajasthan Budget Tours

    ReplyDelete

  47. Firstly talking about the Blog it is providing the great information providing by you . Thanks for that .Hope More articles from you . Next i want to share some information about Salesforce training in Banglore .

    ReplyDelete
  48. This article is well formulated. I particularly like the way how you have delivered all the major points about the topic of the content in petite and crisp points.
    Data Science training in Mumbai
    Data Science course in Mumbai
    SAP training in Mumbai

    ReplyDelete
  49. Amazing Post. The content is very interesting. Waiting for your future updates.
    DevOps Training in Chennai

    DevOps Course in Chennai

    ReplyDelete
  50. SAP stands for Systems Applications and Products in Data Processing. SAP, by definition, is also the name of the ERP (Enterprise Resource Planning) software as well as the name of the company.
    tally training in chennai

    hadoop training in chennai

    sap training in chennai

    oracle training in chennai

    angular js training in chennai

    ReplyDelete
  51. wonderful article contains lot of valuable information. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.
    This article resolved my all queries.good luck an best wishes to the team members.continue posting.learn digital marketing use these following link
    Digital Marketing Course in Chennai

    ReplyDelete
  52. Thanks For Sharing The Information The Information Shared Is Very Valuable Please Keep Updating Us Time Just Went On Reading The article
    by cognex is the AWS Training in Chennai. cognex offer so many courses they are microsoft azure, prince2 foundation, ITI V4 foundation,etc,

    ReplyDelete
  53. Really Nice Information It's Very Helpful All courses Checkout Here.
    data science course noida

    ReplyDelete
  54. I pay a visit every day a few blogs and sites to read articles, but this weblog offers feature based writing.
    leather sofa set

    ReplyDelete
  55. I read this article fully on the topic of the resemblance of most recent and
    preceding technologies, it’s remarkable article.

    Study in Ireland Consultants

    ReplyDelete
  56. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such an amazing content for all the curious readers who are very keen of being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in future too.

    Digital Marketing training in Bhilai

    ReplyDelete
  57. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such an amazing content for all the curious readers who are very keen of being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in future too.

    Digital Marketing training in Bhilai

    ReplyDelete
  58. Fantastic blog extremely good well enjoyed with the incredible informative content which surely activates the learners to gain the enough knowledge. Which in turn makes the readers to explore themselves and involve deeply in to the subject. Wish you to dispatch the similar content successively in future as well.

    Data Science Training in Raipur

    ReplyDelete
  59. Truly incredible blog found to be very impressive due to which the learners who ever go through it will try to explore themselves with the content to develop the skills to an extreme level. Eventually, thanking the blogger to come up with such an phenomenal content. Hope you arrive with the similar content in future as well.
    Digital Marketing Course in Raipur

    ReplyDelete
  60. Honestly speaking this blog is absolutely amazing in learning the subject that is building up the knowledge of every individual and enlarging to develop the skills which can be applied in to practical one. Finally, thanking the blogger to launch more further too.
    Data Analytics online course

    ReplyDelete
  61. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such an amazing content for all the curious readers who are very keen of being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in future too.
    Digital Marketing Training

    ReplyDelete
  62. Very nice blogs!!! i have to learning for lot of information for this site…Sharing for wonderful information. Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing,
    Data Science Training in Hyderabad
    Data Science Course in Hyderabad

    ReplyDelete
  63. Really good blog. Well-written and knowledgeable blog. Thanks for sharing such a wonderful blog. Keep sharing!
    Data Science Course in Hyderabad

    ReplyDelete
  64. Thanks for Sharing a Very Informative Post & I read Your Article & I must say that is very helpful post for us.

    RPA Training in Pune
    Best RPA Training in Pune

    ReplyDelete
  65. very interesting to read.thanks for sharing .Angular training in Chennai

    ReplyDelete

  66. I am really happy to say it’s an interesting post to read . I learn new information from your article , you are doing a great job . Keep it up

    Devops Training in Hyderabad

    Hadoop Training in Hyderabad

    Python Training in Hyderabad

    Tableau Training in Hyderabad

    Selenium Training in Hyderabad

    ReplyDelete
  67. These are truly fantastic ideas regarding blogging. You have touched on some pleasant points here. Any way keep up writing. Bada Business

    ReplyDelete
  68. Admiring the dedication you put into your blog and in depth information you provide. It’s awesome to come across a blog every once in a while that
    isn’t the same old rehashed information. Fantastic read!

    Software Security Solutions

    ReplyDelete

  69. I was just examining through the web looking for certain information and ran over your blog.It shows how well you understand this subject. Bookmarked this page, will return for extra. data science course in vadodara

    ReplyDelete
  70. Excellent website. I was always checking this article, and I’m impressed! Extremely useful and valuable info specially the last part, I care for such information a lot. Thanks buddy.
    Data Science Training in Hyderabad
    Data Science Course in Hyderabad

    ReplyDelete
  71. Hi there, yeah this post is genuinely nice and I have learned a lot of things from it concerning blogging. thanks. Bathroom Mirrors

    ReplyDelete
  72. Excellent post. I want to thank you for this informative read, I really appreciate sharing this great post. Keep up your work.
    DevOps Training in Hyderabad
    DevOps Course in Hyderabad

    ReplyDelete
  73. Stupendous blog huge applause to the blogger and hoping you to come up with such an extraordinary content in future. Surely, this post will inspire many aspirants who are very keen in gaining the knowledge. Expecting many more contents with lot more curiosity further.

    Data Science Certification in Bhilai

    ReplyDelete
  74. Extraordinary blog went amazed with the content that they have developed in a very descriptive manner. This type of content surely ensures the participants to explore themselves. Hope you deliver the same near the future as well. Gratitude to the blogger for the efforts.

    ReplyDelete
  75. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such an amazing content for all the curious readers who are very keen of being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in future too.

    Data Science Course in Bhilai

    ReplyDelete
  76. Impressive blog to be honest definitely this post will inspire many more upcoming aspirants. Eventually, this makes the participants to experience and innovate themselves through knowledge wise by visiting this kind of a blog. Once again excellent job keep inspiring with your cool stuff.

    Data Science Training in Bhilai

    ReplyDelete
  77. Seo services in Varanasi : Best SEO Companies in Varanasi: Hire Digital Marketing Agency, best SEO Agency in Varanasi who Can Boost Your SEO Ranking, guaranteed SEO Services; SEO Company In Varanasi.

    Digital Marketing Company In India : Kashi Digital Agency is one of the Best Digital Marketing companies in Varanasi, India . Ranked among the Top digital marketing agencies in India. SEO Company In India.

    Cheap Website Design Company In Bangalore : Best Website Design Company in Bangalore : Kashi Digital Agency is one of the Best Social Media Marketing agency in Bangalore which provides you the right services.

    E-commerce Website design company India : e-commerce Company in India : Kashi Digital Agency is one of the best e-commerce development services provider in Varanasi, India. This one of the best service if you want quick ROI.

    ReplyDelete
  78. Extremely overall quite fascinating post. I was searching for this sort of data and delighted in perusing this one. Continue posting. A debt of gratitude is in order for sharing. python course in delhi

    ReplyDelete
  79. Extremely overall quite fascinating post. I was searching for this sort of data and delighted in perusing this one. Continue posting. A debt of gratitude is in order for sharing. data scientist course in delhi

    ReplyDelete
  80. Thanks for your marvelous posting! I really enjoyed reading it, you could be a great author. I will be sure to bookmark your blog and definitely will come back in the foreseeable future. I want to encourage you to continue your great posts, have a nice afternoon! Best Digital Marketing Courses in Bangalore



    ReplyDelete
  81. Nice article. I liked very much. All the information given by you are really helpful for my research. keep on posting your views.
    data scientist course aurangabad

    ReplyDelete
  82. Thanks for sharing Let explore the world with us, to make an unbounded view on your product in the market with our android application development company in Chennai. We mainly work in this platform to publicize, sell and distribute Android applications to users around the world via google play. Let everyone play us via google play.

    ReplyDelete