Hi Ahmed,

If performances are important for you, then you can check clustering algorithms that are dedicated to data streams: CluStream, DenStream, etc. (http://rd.springer.com/article/10.1007/s10115-014-0808-1).

Kind regards,

Olivier PARISOT

Dear Olivier

Thank you for your interest and the important article.

Regards

.

maybe you could clarify what you mean by fast :

fast training (ie buiding the clusters) or fast deployment (ie giving a cluster label to new incoming data once the cluster has been built)

for instance, k-means is not too fast for training but reasonnably fast for deployment

.

and well yes of course you can perform clustering in a single dimensional feature space

.

I am not so sure about our time constraint; however, you should test several clustering algorithms on your dataset. This is because some algorithms are efficient for these dataset, but they are inefficient for other ones. I think this is the good way to start.

Hi Ahmed,

clustering one feature does not require a fast algorithm. I think K-means is good enough for your goals, PAM (Partioning around medoid) is a good implementation.

K-means is relatively fast, and is indeed widely-used in many applications. But if you should do the clustering task many times or search for the best K value you should consider using some adaptive methods based on k-means, which are very easy to find just by searching "adaptive k-means".

Evolutionary algorithms such as particle swarm optimization, genetic algorithm etc. can be used in clustering. Represent the clustering problem as a search problem where the search is for finding best  (near optimal ) cluster center points in the d-dimensional input space (d being the number of features used in clustering). The parameter selection is domain specific and careful selection of parameters can lead to fast convergence to near optimal solution i.e. the best centers of likely clusters.

 Dear all

Thank you for your valuable and important suggestion

As a result that I get from the discussion, I will start by using K-mean because I have one feature and check it as you proposed to me. Actually, I need this technique just as a support method in block classification process to speed up the fractal coding process and restrict the huge domain pool. 

Thanks for all and I hope the best for you.

Regards

From copious literature on the said topic, researchers are of the opinion that k-means and some extended k-means algorithm is simple and hence fast. You may kindly go through following specific references, available through the links provided.

1.Z.Huang , A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in

Data mining.

 http://www.ict.griffith.edu.au/~vlad/teaching/kdd.d/readings.d/huang97fast.pdf

2. Q.Song et al., A Fast Clustering-Based Feature Subset Selection Algorithm for High Dimensional Data

http://gr.xjtu.edu.cn/c/document_library/get_file?folderId=217607&name=DLFE-4105.pdf

3. Rui Ding et al., YADING: Fast Clustering of Large-Scale Time Series Data

http://www.vldb.org/pvldb/vol8/p473-ding.pdf

Dear Jayaram

Thank you for the links.

I will check them.

Regards

Hi

Birch is very fast, Leader too, but both are order-dependant and may need a post-processing to improve the quality of the results.

Frank

DBSCAN in proper implementation has complexity O(n) so maybe it is one of the fastest, but it works only for numeric data 

Another set of approaches that you can use

1) Lot of data and need to perform clustering in single batch

I 'll suggest use sampling to create multiple partitions of data. Then use a similar approach  used in Cure. This paper gives bound on sampling and partitions also. Tune these to get best theoretical results

2) If data is coming in stream like twitter stream

Try using stream clustering algorithms. Some details are attached. 

http://www.cs.bu.edu/fac/gkollios/ada05/LectNotes/guha98cure.pdf

http://infolab.stanford.edu/~loc/tkdepaper.pdf

http://cci.drexel.edu/bigdata/bigdata2014/big-data-stream-mining-tutorial.pdf

You may try Subtractive Clustering, which is a one-pass algorithm and not an iterative one like Fuzzy C Means Clustering.

Regards

Ashu

Incremental clustering can also be a good alternative.

The k-means as the simplest method can be considered as the fast one, as it requires less computational efforts during clustering process.

In place of K means clustering Fuzzy C-means clustering will give good performance.

Ahmed Hussain Ali It depends on dataset complexity level. If it is well-separated clusters, then k-means is the fastest. If it is overlapping dataset, then efficiency and effectiveness are both important, thus fuzzy clustering methods are recommended solutions.

Hi Ahmed Hussain Ali, K-means is the fastest method compared to fuzzy c-means because k-means does not have membership degree assignments. Single-solution-based crisp clustering methods are generally more rapid than population-based crisp clustering models.