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

How to construct a File System that lives in Shared Memory.

Shared Memory File System Goals 1. MOUNTED IN SHARED MEMORY The result is a very fast, real time file system. We use Shared Memory so that the file system is public and not private. 2. PERSISTS TO DISK When the file system is unmounted, what happens to it? We need to be able to save the file system so that a system reboot does not destroy it. A great way to achieve this is to save the file system to disk. 3. EXTENSIBLE IN PLACE We want to be able to grow the file system in place. 4. SUPPORTS CONCURRENCY We want multiple users to be able to access the file system at the same time. In fact, we want multiple users to be able to access the same file at the same time. With the goals now in mind we can now talk about the major design issues: FAT File System & Design Issues The  FAT File System  has been around for quite some time. Basically it provides a pretty good file structure. But I have two problems with it: 1. FAT IS NOT EXTENSIBLE IN PLAC...
Post a Comment
Read more

Common Sense Identification of the Security Problems

Organizations make key information security mistakes, which leads to inefficient and ineffective control environment. High profile data breaches and cyber-attacks drive the industry to look for more comprehensive protection measures since many organizations feel that their capability to withstand persistent targeted attacks is minimal. But at the same time, these organizations make some key information security mistakes, that jeopardize their efforts towards control robustness. Although many firms invest in security technologies and people, no one has the confidence that the measures taken are good enough to protect their data from compromises. Below are the 10 worst mistakes which are common to find, and important to address in the path of mature information security posture. If you analyze the cyber security scenarios, and organizational capabilities, the prevailing trend is a vendor-driven approach. In many cases, security professionals adopt the attitude of procuring...
Post a Comment
Read more