3
$\begingroup$

I am looking for an incremental clustering algorithm. By incremental I mean an algorithm that builds clusters starting from an initial dataset and that is able to progressively ingest new items/observations adding them to existing or new clusters.

The maximum number of clusters is a priori unknow and is expected to grow over time, meaning that, after the algorithm have been run on the initial dataset, I expect to receive observations that belongs to never before seen clusters.

I am quite new to this kind of problem and all the clustering algorithms in the Scipy's clustering library only provide methods for one-shot clustering.

The only incremental clustering algorithm offered by Scikit-learn library is the MiniBatchKMeans that requires a fixed number of clusters and does not fit for my use case.

Are there incremental clustering algorithms that handle an unknown number of clusters? Are they already implemented somewhere?

Thank you a lot!

$\endgroup$

1 Answer 1

2
$\begingroup$

One option is incremental hierarchical clustering.

Hierarchical clustering either uses agglomerative or divisive approaches to divide the data into stratified groups. In hierarchical clustering, the number of clusters can be chosen during the process of building the clusters. Incremental hierarchical clustering allows data points to be added throughout the process. The paper "Incremental Clustering for Hierarchical Clustering" by Narita, Hochin, and Nomiya goes into greater detail.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. I have read the linked article and I have a couple of questions (as I am new to hierarchical clustering). First, at the end of the first column on page 2 it says "clusters that are subsets of cluster sets are called partial clusters". What is the precise definition of "cluster" in this context? Is it a partition of the initial set of objects? Also, on page 2 in section III.B it says "update the radius and the center of the partial cluster by using (4) and (5) until it does not satisfy (3) from the root of the cluster to leaves": this statement is not clear to me. $\endgroup$
    – Sirion
    Dec 9, 2022 at 7:50
  • $\begingroup$ I feel like I am missing some basic definitions in the context of hierarchical clustering. (a) What is exactly a "cluster" (is it the whole dendrogram or a partition of the initial set)? (b) If "clustering" means building a "dendrogram", I do not understand how the article above defines the related tree structure. (c) If "clustering" means building a "dendrogram", how do I obtain a flat partition of the initial set? One way would be to look only at a certain level of the dendrogram tree, but which one? (d) Does the leaves of the dendrogram contain single items or the clusters I am looking for? $\endgroup$
    – Sirion
    Dec 9, 2022 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.