Improvements in K-means algorithm to execute on large amounts of data

Abstract

Günümüzün büyük saklama kapasiteli bilgisayar sistemlerinin desteğiyle şirketlerin veritabanı boyutları yakın tarihte ciddi bir şekilde artmıştır. Zaman şirketler açısından büyük önem taşıdığı için, günümüz şirketlerinin hızla büyümüş olan veritabanları daha hızlı veri madenciliği algoritmaları ihtiyacını da birlikte getirmiştir. Şirketlerin tarihsel hareketlerini tutan büyük boyutlardaki veritabanları şirketlere rekabet avantajı sağlayacak olan değerli gizli bilgiler içermektedir. Ayrıca zaman da şirketler açısından çok önemli olduğu için bu şirketler yüklü miktarlardaki veritabanlarını kısa sürede veri madenciliği ile inceleyip kısa sürede kendilerine rekabet avantajı sağlayacak doğru kararları almaları gerekmektedir. Bu nedenle, klasik veri madenciliği algoritmalarının gözden geçirilerek iyileştirilmesi ve daha kısa sürede veritabanlarındaki gizli bilgileri ortaya çıkaracak hale getirilmeleri gerekmektedir. Bu projede K-means veri madenciliği algoritmasının büyük veri tabanlarını kısa sürede gruplandıracak şekilde geliştirileceği öne sürülmüştür. Algoritmanın, paralelleştirme yöntemi ile geliştirilmesine karar verilmiştir. Günümüzde, işleme gücünün artırılmasının en popüler yolunun bilgisayarların birbirine bağlanması ve algoritmaların bilgisayar ağları üzerinde eş zamanlı olarak çalıştırılması olduğu için paralelleştirme yöntemi bu geliştirme çalışması için uygun görülmüştür. Ayrıca bu popülarite, paralel bilgisayar laboratuarlarının bulunulabilirliğini de günden güne artırmaktadır. K-means algoritmasının paralel versiyonu C Programlama Dili kullanılarak geliştirildi. Paralelleştirme işlemi için ise MPI (Message Passing Interface) kütüphanesi kullanıldı. Zaman açısından bir karşılaştırma yapılabilmesi için klasik (seri versiyon) algoritma da C Programlama Dili kullanılarak geliştirildi. Daha sonra, algoritmalar aynı şartlar altında birden fazla kez çalıştırılarak sonuçları tartışıldı. Tablolar ve grafikler kullanılarak özet haline getirilen çalıştırma sonuçları göstermiştir ki K-means algorithmasının paralelleştirilmesi sonucunda hemen hemen paralel çalıştırmada kullanılan bilgisayar sayısı kadar performans kazanımı elde edilmiştir.

By the help of large storage capacities of current computer systems, datasets of companies has expanded dramatically in recent years. Rapid growth of current companies' databases has raised the need of faster data mining algorithms as time is very critical for those companies. Large amounts of datasets have historical data about the transactions of companies which hold valuable hidden patterns which can provide competitive advantage to them. As time is also very important for these companies, they need to mine these huge databases and make accurate decisions in short durations in order to gain marketing advantage. Therefore, classical data mining algorithms need to be revised such that they discover hidden patterns and relationships in databases in shorter durations. In this project, K-means data mining algorithm has been proposed to be improved in performance in order to cluster large datasets in shorter time. Algorithm is decided to be improved by using parallelization. Parallelization of the algorithm has been considered to be a suitable solution as the popular way of increasing computation power is to connect computers and execute algorithms simultaneously on network of computers. This popularity also increases the availability of parallel computation clusters day by day. Parallel version of the K-means algorithm has been designed and implemented by using C language. For the parallelisation, MPI (Message Passing Interface) library has been used. Serial algorithm has also been implemented by using C language for the purpose of comparison. And then, algorithms have been run for several times under same conditions and results have been discussed. Summarized results of these executions by using tables and graphics has showed that parallelization of the K-means algorithm has provied a performance gain almost proportional by the count of computers used for parallel execution.