Skip to main content

K-means Clustering

K-means: widely used clustering technique! ,Initialization: blind random on input data!
Drawback: very sensitive to choice of initial clustercenters (seeds)!
Local optimal can be arbitrarily bad wrt. objective function, compared to global optimal clustering

Idea: spread the k initial cluster centers away from each other.!
O(log k)-competitive with the optimal clustering" substantial convergence time speedups (empirical)!

C - Sample a point uniformly at random from X
    While `C´ < k do
    Sample x € X with probability prop, to DSquare (x)
    c <- C U {x}
end while

c € c: Cluster Center
x € X: Data Point'D(x) distance between x and nearest Ck that has already chosen

Test dataset
200 Clustering runs, each with and without k-means initialization
Measure RSS (Intra-Class variance)

K.Means optimal clustering 115 times (57.5%)

 Implementation Test Dataset: 4 Square (n=16)



Expected: 4 nice Cluster














Evaluation on Test Dataset!
• 200 clustering runs, each with and without kmeans++ initialization!
• Measure RSS (intra-class variance)!
• K-means! optimal clustering 115 times (57.5%) !
• K-means++ ! optimal clustering 182 times (91%)!

Comparison of the frequency distribution of RSS values between k-means and k-means
++ on the evaluation dataset (n=200)!



 Comparison of the frequency distribution of RSS values between k-means and k-means
++ on the UCI real world dataset (n=500)!









Comments

Post a Comment

Popular posts from this blog

Python and Parquet Performance

In Pandas, PyArrow, fastparquet, AWS Data Wrangler, PySpark and Dask. This post outlines how to use all common Python libraries to read and write Parquet format while taking advantage of  columnar storage ,  columnar compression  and  data partitioning . Used together, these three optimizations can dramatically accelerate I/O for your Python applications compared to CSV, JSON, HDF or other row-based formats. Parquet makes applications possible that are simply impossible using a text format like JSON or CSV. Introduction I have recently gotten more familiar with how to work with  Parquet  datasets across the six major tools used to read and write from Parquet in the Python ecosystem:  Pandas ,  PyArrow ,  fastparquet ,  AWS Data Wrangler ,  PySpark  and  Dask . My work of late in algorithmic trading involves switching between these tools a lot and as I said I often mix up the APIs. I use Pandas and PyArrow for in-RAM comput...
Post a Comment
Read more

Real-Time Talk: Windows 10 IoT Core Background Tasks and ASP.NET Core Web Apps

Display useful information from your Windows 10 IoT Core application in an ASP.NET Core web app, essential for integrating IoT data into a solution. Windows 10 IoT background task talk with a web application using WebSockets. Problems As my path to this solution has been troublesome, I am listing here the main problems I faced so my dear readers have a better idea of dead-end streets along the way: I was not able to make the ASP.NET Core web application run under a Windows 10 IoT background service. I found no information about when or if it will be supported in the near future. ASP.NET MVC and ASP.NET Core have different SignalR implementations. I was not able to make a SignalR client for .NET Core work with SignalR hosted on a web application. I was able to make things work by directly using a WebSocket. It’s not as nice a solution as I had in my mind, but it works until things get better. Making the Background Task and Web Application Talk I worked out sim...
Post a Comment
Read more

DANGER (STILL) LURKS IN THE INTERNET OF THINGS (IOT)

All of the media, both “mainstream” and “tech”, has gushed over all of the new appliances and devices that are now in the category of what we would call the Internet of Things.  Items like home security,  home lighting, and refrigerators, to name a few. There are many advantages to having connected appliances and devices, Threats that can and will be exploited if unsuspecting users don’t secure them.   Two “layers” of security : The first layer of offering  is a security API that will provide [a way] to easily do a virtual patch, to prevent a remote attack, for example . . . the third layer is cloud: IoT cannot do anything without the cloud.  Most data is sent to the cloud and you will need to have proper protection and make sure the cloud is always available. In both situation Users are vulnerable, mostly due to their own apathy.  Users often either don’t know how to patch their own machines (and in this case, devices) or have glanced...
Post a Comment
Read more