Le clustering agglomératif hiérarchique est déterministe, sauf pour les distances liées lorsque n'utilise pas de liaison simple.

DBSCAN est déterministe, sauf pour la permutation de l'ensemble de données dans de rares cas.

k-means est déterministe sauf pour l'initialisation. Vous pouvez initialiser avec les k premiers objets, alors c'est aussi déterministe.

PAM comme k-means.

... mais il y a probablement 100 algorithmes de clustering supplémentaires!

Je peux vous orienter vers un algorithme et une famille d'algorithmes:

• L'algorithme s'appelle IGMM (Incremental Gaussian Mixture Model). Il est robuste (mais pas insensible) à la commande. Mais lorsque les données arrivent dans le même ordre, elles donnent toujours le même résultat.
• Une famille d'algorithmes de clustering qui satisfait vos conditions est le clustering spectral. Ce sont des algorithmes par lots et vous donneront les mêmes résultats pour les mêmes ensembles de données, même avec un ordre différent.

EDIT: aussi, il existe des méthodes d'initialisation déterministe des clusters K-Means, comme comme celui-ci.

Tous les algorithmes, par définition, sont déterministes compte tenu de leurs entrées. Tout algorithme qui utilise des nombres pseudo-aléatoires est déterministe étant donné la valeur de départ.

K-signifie, que vous avez utilisé comme exemple, commence par des centres de gravité de cluster choisis au hasard afin de trouver les meilleurs. Outre l'initialisation, l'algorithme est totalement déterministe, car vous pouvez vous assurer de regarder son pseudo-code:

Rien ne vous interdit de commencer avec des centres de gravité non aléatoires. Nous utilisons des centres de gravité aléatoires afin de nous assurer que des points de départ mal choisis ne nous conduiront pas à de mauvais résultats. La même chose avec d'autres algorithmes "aléatoires": vous pouvez les utiliser de manière "déterministe", mais dans la plupart des cas, ce n'est pas une bonne chose à faire.

Dans le cas de k-means, l'algorithme minimise de manière déterministe la somme des carrés intra-cluster pour trouver la solution de clustering optimale. Malheureusement, il est sensible à la façon dont l'algorithme a été initialisé. Dans la plupart des cas, les problèmes de clustering n'ont pas de solutions claires, à cause de cela, nous voulons souvent utiliser des procédures aléatoires pour les renforcer.

Imaginez que vous ayez utilisé un algorithme de clustering hiérarchique déterministe . Imaginez qu'il parcourt vos données de manière séquentielle, à partir de la première observation. Que se passerait-il si le premier cas était une valeur aberrante? D'un autre côté, si vous l'initialisez plusieurs fois à des points aléatoires, la procédure sera moins sujette à des problèmes de données.

De plus, si vous exécutez plusieurs fois un algorithme non "déterministe" puis utilisez la majorité voter pour choisir pour chaque cas la classe qui apparaît le plus souvent parmi les résultats, puis la sortie finale sera également très déterministe.

Si je devais réinterpréter votre description de «déterministe», cela me paraîtrait plus comme une analyse de cluster longitudinale et «confirmatoire» - à l'exception importante que vous n'avez pas explicitement intégré les considérations de séries chronologiques dans votre modèle. Les méthodes de regroupement de confirmation sont déployées une fois que l'on estime que «l'espace» qu'elles sont censées décrire a été suffisamment bien compris pour éviter le besoin d'approches exploratoires. La cladistique basée sur la spéciation en est un exemple.

Les solutions de cluster longitudinal reçoivent enfin l'attention qu'elles méritent dans la littérature. À ma connaissance, les premiers travaux remontent aux années 80 avec les algorithmes à trois modes de Pieter Kroonenberg. Mais il y a beaucoup de recherches récentes intéressantes qui impliquent des chaînes de markov cachées, par exemple, les articles de Steve Scott ou l'article de thèse d'Oded Netzer utilisant tous deux des HMM, des approches théoriques de l'information hiérarchiques et non basées sur le moment telles que le clustering de distribution de permutation d'Andreas Brandmaier ainsi que les chapitres. consacré aux algorithmes de clustering longitudinal dans le livre Data Clustering d'Aggarwal et Reddy.

L'élément clé à garder à l'esprit avec toutes ces approches emprunte à la conceptualisation par Kroonenborg d'une matrice multimode dans la mesure où vous ne pouvez pas faire bouger tous les modes en même temps. Cela signifie que la dernière chose à faire est de réinitialiser l'algorithme avec chaque nouvel ensemble de données. Vous voulez plutôt "corriger", par exemple, deux des trois modes, permettant au troisième mode de varier dans une sorte de "conception" expérimentale. De cette manière, vous pouvez étudier plus attentivement l'impact de la dynamique du changement sur un créneau donné dans vos données.

Cette approche est recommandée quel que soit l'algorithme utilisé.

* EDIT * En fait, je me trompe sur le fait que le travail de Kroonenberg est le plus ancien en mode 3 une analyse. Ledyard Tucker a probablement écrit l'article original en 1966, Quelques notes mathématiques sur l'analyse factorielle à trois modes .