004f81e48c88710c36ed22085921ddc4d876d22a
[ppam-mpi.git] / communication / short_paper / JDS2014_short.tex
1 \documentclass[12pt]{article}
2 %
3 %
4 % Retirez le caractere "%" au debut de la ligne ci--dessous si votre
5 % editeur de texte utilise des caracteres accentues
6 %\usepackage[latin1]{inputenc}
7 \usepackage[utf8]{inputenc}
8
9 %
10 % Retirez le caractere "%" au debut des lignes ci--dessous si vous
11 % utiisez les symboles et macros de l'AMS
12 \usepackage{amsmath}
13 \usepackage{amsfonts}
14 %
15 %
16 \setlength{\textwidth}{16cm}
17 \setlength{\textheight}{21cm}
18 \setlength{\hoffset}{-1.4cm}
19
20 % for figures and tables
21 \usepackage{float}
22 \usepackage{graphicx}
23 \usepackage{wrapfig}
24 \usepackage{xcolor}
25 \usepackage{hyperref}
26 \hypersetup{
27 colorlinks,
28 linkcolor=black,
29 urlcolor=violet
30 }
31 \usepackage{scrextend}
32 %
33 %
34 \begin{document}
35
36 %--------------------------------------------------------------------------
37
38 \begin{center}
39 {\Large
40 {\sc Parallélisation de l'algorithme des $k$-médoïdes. Application au clustering de courbes.} %heuristique ?!
41 }
42 \bigskip
43
44 Benjamin Auder $^{1}$ \& Jairo Cugliari $^{2}$
45 \bigskip
46
47 {\it
48 $^{1}$ Laboratoire LMO. Université Paris-Sud. Bât 425. 91405 Orsay Cedex, France.\\benjamin.auder@math.u-psud.fr
49
50 $^{2}$ Laboratoire ERIC. Université Lumière Lyon 2. Bât K. 69676 Bron Cedex, France.\\jairo.cugliari@univ-lyon2.fr
51 }
52 \end{center}
53 \bigskip
54
55 %--------------------------------------------------------------------------
56
57 {\bf R\'esum\'e.}
58 Nous présentons une méthode de clustering adaptée à de grandes bases de données de courbes densément discrétisées, donc elle-mêmes en grande dimension.
59 La classification obtenue peut être utilisée afin de choisir de meilleurs modèles de prédiction de courbes, plus spécifiques, dans chacun des groupes.
60 La méthode consiste en deux principales étapes :
61 réduire la dimension des courbes via une base d'ondelettes, puis effectuer le clustering en parallèle.
62 Les ondelettes sont bien adaptées pour identifier des caractéristiques localisées en temps et échelle.
63 De plus, l'aspect multi-résolution de la transformée en ondelettes permet de regrouper les coefficients
64 selon leur contribution à l'énergie totale, fournissant ainsi des représentants compacts pour chaque courbe.
65 L'algorithme des $k$-médoïdes est appliqué à plusieurs sous-échantillons de l'ensemble des représentations réduites,
66 puis les centres finaux sont obtenus en recherchant la médiane (ou éventuellement la moyenne) des médoïdes des échantillons.
67 Des applications sont présentées sur deux jeux de données, dont les consommations électriques irlandaises journalières.
68 \smallskip
69
70 {\bf Mots-cl\'es.} réduction de dimension, ondelettes, $k$-médoïdes, parallèle
71 \bigskip\bigskip
72
73 {\bf Abstract.}
74 We present a clustering method adapted to large databases of densely sampled curves, hence themselves in high dimension.
75 The resulting classification can help to better tune models to predict new curves, each in every group.
76 The method consists of two main steps:
77 use a wavelet basis to reduce curves dimensionality, and then run a parallel clustering algorithm.
78 Wavelets are well suited to identify characteristics localized both in time and space.
79 Moreover, the multiresolution nature of the wavelets transform allows to group coefficients according to their
80 contribution to the total energy, thus providing compact representations for every curve.
81 The $k$-medoids algorithm is applied to several subsamples of all the reduced representations, and then the final
82 centers are obtained by computing the median (or mean) of the samples medoids.
83 Applications are shown on two databases, including Irish daily electrical consumptions.
84 \smallskip
85
86 {\bf Keywords.} dimensionality reduction, wavelets, $k$-medoids, parallel
87
88 %~ Nous présentons une méthode de clustering adaptée à de grandes bases de données de courbes densément discrétisées, donc elle-mêmes en grande dimension. La classification obtenue peut être utilisée afin de choisir de meilleurs modèles de prédiction de courbes, plus spécifiques, dans chacun des groupes. La méthode consiste en deux principales étapes : réduire la dimension des courbes via une base d'ondelettes, puis effectuer le clustering en parallèle. Les ondelettes sont bien adaptées pour identifier des caractéristiques localisées en temps et échelle. De plus, l'aspect multi-résolution de la transformée en ondelettes permet de regrouper les coefficients selon leur contribution à l'énergie totale, fournissant ainsi des représentants compacts pour chaque courbe. L'algorithme des k-médoïdes est appliqué à plusieurs sous-échantillons de l'ensemble des représentations réduites, puis les centres finaux sont obtenus en recherchant la médiane (ou éventuellement la moyenne) des médoïdes des échantillons. Des applications sont présentées sur deux jeux de données, dont les consommations électriques irlandaises journalières.
89
90 %--------------------------------------------------------------------------
91
92 \section{Introduction}
93
94 % * clustering
95 % * parallelisation of clustering
96 % * fda + wavelets
97 % * données individuelles de conso
98
99 Récemment, le contexte du \textit{Big Data} a rendu nécessaire le développement d'algorithmes spécifiques à de (très)
100 grands volumes de données, éventuellement aussi en grande dimension comme c'est le cas dans notre étude.
101 Ainsi ont vu le jour des algorithmes opérant sur de grands graphes (Kang et al.~2009) ou sur des flux de données haut débit (De Francisci Morales et Bifet~2013), entre entres.
102 Le livre de Bekkerman et al.~(2011) présente des algorithmes de Machine Learning s'exécutant en parallèle sur diverses architectures, et
103 ce type de programmation est en plein essor.\\
104
105 \noindent La classification non supervisée (\textit{clustering}) est une des branches de l'apprentissage non supervisé.
106 L'objectif est de regrouper les données en \textit{clusters} homogènes, suffisamment distincts deux à deux.
107 Depuis la proposition originale de Tyron~(1939) un grand nombre d'articles ont été publié à ce sujet (voir Berkhin~2006 pour une revue).
108 Cependant, il n'y a pas de consensus sur la définition d'un cluster : celle-ci varie en fonction des données, du contexte et de l'algorithme utilisé.
109 Malgré ce fait, la classification non supervisée reste une technique très populaire qui permet
110 de réduire la taille des données en les résumant à quelques représentants ; c'est particulièrement intéressant lorsqu'on travaille sur de grosses bases de données.\\
111
112 \noindent Dans ce travail nous avons choisi d'adapter un algorithme de clustering classique pour une exécution parallèle, opérant sur des données de dimension réduite.
113 La première partie présente la technique retenue afin d'abaisser la dimension via une base d'ondelettes.
114 L'algorithme classant les données en parallèle est expliqué dans la seconde partie, puis nous montrons quelques résultats de tests.
115
116 \section{Réduction de dimension}
117
118 Dans cette section nous expliquons comment sont traitées les variables fonctionnelles (voir Antoniadis et al.~(2013) pour plus de détails).\\
119
120 \noindent Chaque fonction $z$ est d'abord discrétisée sur une fine grille (toutes les 30 minutes pour les consommations électriques), et
121 la discrétisation est encore notée $z = \{ z(t_i), i = 1, \ldots, N \}$.
122 $z$ est alors approchée (jusqu'à l'échelle $J$) par un développement tronqué sur une base d'ondelettes avec un coefficient d'échelle $c_{0,0}$
123 et les coefficients d'ondelettes $\{d_{j, k}\}_{j, k}$ :
124 %
125 \begin{equation} \label{approx}
126 z_J(t) = c_{0,0} \phi_{0, 0} (t) + \sum_{j=0}^{J-1} \sum_{k=0}^{2^j - 1} d_{j,k} \psi_{j, k} (t).
127 \end{equation}
128 Alors, l'énergie $\mathcal{E}_Z = \| z \|^2_{ L_2 }$ de chaque fonction $z$ est égale à la somme des énergies
129 de ses coefficients en ondelettes distribuées à travers les échelles :
130 %
131 \begin{equation} \label{scaledist}
132 \mathcal{E}_z \approx c_{0,0}^2 + \sum_{j=0}^{J-1} \| \mathbf{W}_j \|^2_2,
133 \end{equation}
134 %
135 où $\| \mathbf{W}_j \|^2_2 = (d_{j, 0}, \ldots d_{j, 2^j - 1})'$, l'approximation étant due à la troncature à l'échelle $J$.
136 On ne s'intéresse qu'à l'information contenue dans la forme des fonctions, pas à celle de son niveau moyen.
137 Ainsi, on définit la contribution absolue de l'échelle $j$ à l'énergie globale de la fonction centrée comme
138 \[ \hbox{cont}_j = \| \mathbf{W}_j \|^2_2, \qquad j=0,\ldots,J-1. \]
139 Finalement, chaque fonction est caractérisée par le vecteur de ses contributions absolues à l'énergie globale.\\
140
141 \noindent En pratique nous choisissons $J$ de l'ordre de $\log_2(N)$ : c'est la valeur maximale possible compte-tenu de la discrétisation.
142
143 \section{$k$-médoïdes parallèle}
144
145 Nous rappelons tout d'abord l'algorithme des $k$-médoïdes, puis indiquons comment s'est déroulée la parallélisation.\\
146
147 %\subsection{Algorithme des $k$-médoïdes}
148 \noindent \textbf{Algorithme des $k$-médoïdes}\\
149 Comme dans l'algorithme des $k$-means, l'idée est de partitionner les données autour de $k$ centres, ici appelés \emph{médoïdes}.
150 La fonction à minimiser (\emph{distorsion}) est similaire :
151 $$D(x) = \min_{m_1,\dots,m_k \in \mathbb{R}^d} \sum_{i=1}^{n} \min_{j=1,\dots,k} \| x_i - m_j \| \, ,$$
152 avec $x = (x_1,\dots,x_n)$, $\|\,.\,\|$ pouvant désigner n'importe quelle norme ; ici nous choisissons la norme euclidienne.
153 Les distances n'apparaissant pas au carré, cet algorithme est moins sensible aux outliers que le $k$-means.
154 Cependant, sa programmation est plus délicate car dans le cas de la médiane spatiale il n'existe pas de formule analogue à celle de la moyenne.
155 La première implémentation de l'algorithme est celle de Kaufman et Rousseeuw~(1987), PAM pour Partitioning Around Medoids.
156 Elle est assez coûteuse, mais donne de bons résultats et reste simple à écrire. Diverses heuristiques ou accélérations autour de cette implémentation
157 ont été développés (Chu et al.~2002, etc.), mais nous utilisons ici la version originale, qui se révèle suffisante.\\
158 %TODO: encadré algo PAM. [si reste de la place...]
159
160 %\subsection{Parallélisation avec MPI}
161 \noindent \textbf{Parallélisation avec MPI}\\
162 MPI est une librarie permettant de faciliter l'écriture de programmes en parallèle.
163 %Elle est disponible pour divers langages dont le C, que nous avons choisi.
164 %~ Son principe est le suivant :
165 %~ \begin{enumerate}
166 %~ \item un certain nombre de coeurs de calcul sont alloués et initialisés avec les mêmes valeurs sauf une : le rang du processus ;
167 %~ \item chaque coeur exécute séquentiellement deux types d'instructions : locales, comme dans un programme normal,
168 %~ et de communication, où il envoie un ou plusieurs message à un ou plusieurs autres processus. Ces messages peuvent demander ou envoyer des résultats, mais aussi
169 %~ effectuer des actions plus élaborées comme [TODO]
170 %~ \item le calcul se termine lorsque tous les coeurs sont arrêtés.
171 %~ \end{enumerate}
172 Nous l'utilisons en mode master-slave, c'est à dire que le travail est divisé en deux types d'entités: un processus coordinateur,
173 et des coeurs se contentant d'exécuter les demandes du processus maître.
174 %~ \begin{itemize}
175 %~ \item master : reçoit l'entrée initiale, coordonne les autres processus pour effectuer la tâche, et rassemble les résultats ;
176 %~ \item slave : boucle en attendant des instructions du processus maître, exécute les sous-tâches et retourne les résultats partiels.
177 %~ \end{itemize}
178 Voici le flot d'exécution du programme final :\\
179 %\begin{enumerate}
180 \begin{addmargin}[1em]{2em}% 1em left, 2em right
181 \noindent \textbf{1.} le processus maître découpe le problème en sous-tâches sur des jeux de données plus petits, et les envoie à chaque esclave ;\\
182 \textbf{2.} pour une sous-tâche donnée, on réduit la dimension puis applique l'algorithme de clustering, et retourne les centres ;\\
183 \textbf{3.} le processus principal récupère et aggrège les résultats en un jeu de $k$ centres.\\
184 \end{addmargin}
185 %\end{enumerate}
186 Le code sera disponible prochainement sur \href{https://github.com/}{github}.
187 %TODO: code disponible en ligne sur github. (faut beautifier quelques bricoles dans le code d'abord, en particulier serialize/deserialize et type d'ondelette en argument (?!)
188
189 \section{Applications}
190
191 Deux jeux de données ont été utilisés ici : des évolutions de magnitudes d'étoiles, et de consommations électriques.
192
193 \subsection{Magnitudes d'étoiles}
194
195 Ce jeu de données récupéré via le site web de Keogh et al.~(2011) consiste en un ensemble d'entraînement de 1000 courbes,
196 et une base de test de 8236 courbes. Chacune d'entre elle a un label compris entre 1 et 3 ; la figure \ref{figsltr3clusts} les représente.
197 On remarque que les groupes 1 et 3 sont assez similaires, contenant des courbes difficiles à classer.
198
199 \begin{figure}[H]
200 \begin{minipage}[c]{.32\linewidth}
201 \includegraphics[width=5cm,height=3.5cm]{img/slgr1.png}
202 \vspace*{-0.3cm}
203 \caption{Groupe 1}
204 \end{minipage}
205 \begin{minipage}[c]{.32\linewidth}
206 \includegraphics[width=5cm,height=3.5cm]{img/slgr2.png}
207 \vspace*{-0.3cm}
208 \caption{Groupe 2}
209 \end{minipage}
210 \begin{minipage}[c]{.32\linewidth}
211 \includegraphics[width=5cm,height=3.5cm]{img/slgr3.png}
212 \vspace*{-0.3cm}
213 \caption{Groupe 3}
214 \end{minipage}
215 \label{figsltr3clusts}
216 \end{figure}
217
218 Compte-tenu du relatif faible nombre d'échantillons nous pouvons lancer le programme sur tout le jeu de données ;
219 cela permet de comparer aux résultats obtenus par la version parallèle, que l'on espère presque aussi bons.
220 Le tableau \ref{tabDistorSl} contient les distorsions empiriques calculées sur les ensemble d'entraînement et de test,
221 ainsi que l'adéquation des deux partitions ("intra"), et leur adéquation à la partition réelle ("inter"). Cette dernière est mauvaise à cause de la remarque précitée :
222 les courbes des clusters 1 et 3 se ressemblent trop pour appliquer un algorithme de partitionnement de type $k$-means.\\
223
224 \begin{table}[H]
225 \centering
226 \begin{tabular}{|l|c|c|c|}
227 \hline
228 & Distorsion & "Intra-adéquation" & "Inter-adéquation" \\
229 \hline
230 Entraînement seq. & 1.31e4 & 0.79 & 0.77\\
231 \hline
232 Entraînement // & 1.40e4 & 0.79 & 0.68\\
233 \hline
234 Test seq. & 1.09e5 & 0.78 & 0.76\\
235 \hline
236 Test // & 1.15e5 & 0.78 & 0.69\\
237 \hline
238 \end{tabular}
239 \caption{Distorsions et indices d'adéquation des partitions}
240 \label{tabDistorSl}
241 \end{table}
242
243 %~ 1) Starlight curves : utiliser 1000 (resp. 3000) courbes pour le clustering, puis ~9000 (resp. ~7000) pour classif.
244 %~ Comparer les médoïdes (renuméroter en sortie du code), et afficher les perfs : taux de classif correcte.
245
246 \subsection{Consommations électriques irlandaises}
247
248 Ce jeu de données consiste en 4621 séries temporelles représentant l'évolution de la consommation életrique d'autant de foyers irlandais.
249 Celles-ci sont similaires aux courbes EDF sur lesquelles vise à être appliquée notre méthode.
250 Nous avons choisi d'appliquer l'algorithme avec 3 et 5 classes. Compte-tenu du grand nombre de points de discrétisation (25k)
251 et de la haute variabilité des données, celles-ci sont difficiles à représenter. Ainsi nous n'indiquons que les résultats numériques ;
252 ils sont visibles dans le tableau \ref{tabDistorIr}, et sont cette fois plutôt bons.\\
253
254 \begin{table}[H]
255 \centering
256 \begin{tabular}{|l|c|c|}
257 \hline
258 & Distorsion & "Intra-adéquation" seq. VS //\\
259 \hline
260 3 clusters seq. & 1.90e7 & 0.90\\
261 \hline
262 3 clusters // & 2.15e7 & 0.90\\
263 \hline
264 5 clusters seq. & 1.61e7 & 0.89\\
265 \hline
266 5 clusters // & 1.84e7 & 0.89\\
267 \hline
268 \end{tabular}
269 \caption{Distorsions et indices d'adéquation des partitions}
270 \label{tabDistorIr}
271 \end{table}
272 %pour un nombre de clusters égal à 3, 7 et 15.
273
274 \section{Conclusion}
275
276 Nous avons cherché à identifier des groupes de consommateurs à partir de données fonctionnelles
277 pour bénéficier de l'information supplémentaire fournie par la forme des courbes, qui serait perdue
278 si on les considérait comme de simples vecteurs. Cette forme est capturée $-$ entre autres caractéristiques $-$
279 par les coefficients d'ondelettes, regroupés par niveaux d'énergie. Les dissimilarités sont calculées ensuite
280 via une distance $L^p$. Alternativement (ou complémentairement), il serait intéressant d'utiliser une mesure de dissimilarité
281 plus directement basée sur la forme des courbes, comme le font Heckman et Zamar~(2000).\\
282
283 Ensuite, la procédure de clustering mise en place est prévue pour passer à l'échelle pour plusieurs millions de courbes.
284 En effet, elle a été conçue initialement pour être appliquée aux séries temporelles des clients EDF (plusieurs dizaines de millions).
285 Elle consiste à appliquer l'algorithme des $k$-médoïdes sur des groupes de courbes, puis des groupes de médoïdes
286 jusqu'à obtenir un seul ensemble traité sur un processseur.
287 Les résultats obtenus sur les deux jeux de données présentés sont assez encourageants, et permettent d'envisager une utilisation à plus grande échelle.
288
289 %~ \section{Exemple de r\'ef\'erences bibliographiques}
290 %~ La n\'ecessit\'e de produire des r\'esum\'es clairs et bien
291 %~ r\'ef\'erenc\'es a \'et\'e d\'emontr\'ee par Achin et Quidont~(2000).
292 %~ Le r\'ecent article de Noteur~(2003) met en \'evidence \dots
293
294 %Quelques rappels :
295 %%
296 %\begin{center}
297 %%
298 %\begin{tabular}{lr} \hline
299 %%
300 %Accent aigu : & \'e; \\
301 %Accent grave : & \`a;\\
302 %Accent circonflexe : & \^o mais \^{\i};\\
303 %Tr\'emas : & \"o mais \"{\i};\\
304 %C\'edille : & \c{c}. \\ \hline
305 %\end{tabular}
306 %%
307 %\end{center}
308
309 %--------------------------------------------------------------------------
310
311 \section*{Bibliographie}
312
313 \noindent [1] A. Antoniadis, X. Brossat, J. Cugliari et J.-M. Poggi (2013), Clustering Functional Data Using Wavelets, {\it International Journal of Wavelets, Multiresolution and Information Processing}, 11(1), 35--64.\\%, \texttt{doi:10.1142/S0219691313500033}
314 \noindent [2] R. Bekkerman, M. Bilenko et J. Langford - éditeurs (2011), Scaling up Machine Learning: Parallel and Distributed Approaches, {\it Cambridge University Press}.\\
315 \noindent [3] P. Berkhin (2006), A Survey of Clustering Data Mining Techniques, {\it Grouping Multidimensional Data, éditeurs : J. Kogan, C. Nicholas, M. Teboulle}.\\
316 \noindent [4] F. Chang, J. Dean, S. Ghemawat, W.C. Hsieh, D.A. Wallach, M. Burrows, T. Chandra, A. Fikes, et R.E. Gruber (2006), Bigtable: A Distributed Storage System for Structured Data, {\it Seventh Symposium on Operating System Design and Implementation}.\\
317 \noindent [5] S.-C. Chu, J.F. Roddick et J.S. Pan (2002), An Efficient K-Medoids-Based Algorithm Using Previous Medoid Index, Triangular Inequality Elimination Criteria, and Partial Distance Search, {\it Lecture Notes in Computer Science}, 2454, 63--72.\\
318 \noindent [6] J. Dean et S. Ghemawat (2004), MapReduce: Simplified Data Processing on Large Clusters, {\it Sixth Symposium on Operating System Design and Implementation}.\\
319 \noindent [7] G. De Francisci Morales et A. Bifet (2013), Introducing SAMOA, an open source platform for mining big data streams, {\it http://yahooeng.tumblr.com/post/65453012905/introducing-samoa-an-open-source-platform-for-mining}.
320 \noindent [8] N.E. Heckman et R.H. Zamar (2000), Comparing the shapes of regression functions. {\it Biometrika}, 87(1), 135--144.\\
321 \noindent [9] U. Kang, C.E. Tsourakakis et C. Faloutsos (2009), PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations, {\it IEEE International Conference on Data Mining}.\\
322 \noindent [10] L. Kaufman et P.J. Rousseeuw (1987), Clustering by means of Medoids, {\it Statistical Data Analysis Based on the L\_1-Norm and Related Methods, éditeur : Y. Dodge}.\\
323 \noindent [11] E. Keogh, Q. Zhu, B. Hu, Y. Hao, X. Xi, L. Wei et C.A. Ratanamahatana (2011), The UCR Time Series Classification/Clustering, {\it http://www.cs.ucr.edu/\~{}eamonn/time\_series\_data/}.\\
324 \noindent [12] R.C. Tryon (1939), Cluster analysis. {\it New York: McGraw Hill}.\\
325 %\noindent [7] C.C. Aggarwal - éditeur (2006) Data Streams: Models and Algorithms, \{it Advances in Database Systems}.
326 %[Pegasus: Mining billion-scale graphs in the cloud ? mars 2012, mais 4 pages...]
327 %Data Warehousing and Knowledge Discovery.
328 %TODO : find paper :
329 %http://melmeric.files.wordpress.com/2013/04/samoa-a-platform-for-mining-big-data-streams.pdf
330 %http://yahooeng.tumblr.com/post/65453012905/introducing-samoa-an-open-source-platform-for-mining
331
332 %\noindent [2] Auteurs (ann\'ee), Titre, revue, localisation.
333 %~ \noindent [3] Achin, M. et Quidont, C. (2000), {\it Th\'eorie des
334 %~ Catalogues}, Editions du Soleil, Montpellier.
335
336 \end{document}
337
338 %~ Possible références :
339 %~
340 %~ == general
341 %~
342 %~ The Elements of Statistical Learning, Trevor Hastie, Robert Tibshirani, Jerome H. Friedman
343 %~ (14.3.10 vers page 515)
344 %~
345 %~ Titre Clustering by Means of Medoids
346 %~ Volume 3 ;Volume 87 de Reports of the Faculty of Mathematics and Informatics. Delft University of Technology
347 %~ Numéro 87,Partie 3 de Reports of the Faculty of Mathematics and Informatics
348 %~ Auteurs Leonard Kaufman, Peter Rousseeuw
349 %~ Éditeur Fac., Univ., 1987
350 %~ Longueur 14 pages
351 %~
352 %~ Finding Groups in Data: An Introduction to Cluster Analysis (Wiley Series in Probability and Statistics) [Paperback]
353 %~ Leonard Kaufman (Author), Peter J. Rousseeuw (Author)
354 %~
355 %~ == extensions, generalisations, autres algos...
356 %~
357 %~ K-AP: Generating Specified K Clusters by Efficient Affinity Propagation
358 %~ Xiangliang Zhang, Wei Wang, Kjetil Nørvag, and Michele Sebag
359 %~ http://www.idi.ntnu.no/~noervaag/papers/ICDM2010.pdf
360 %~
361 %~ A Coherent and Heterogeneous Approach to Clustering
362 %~ Arian Maleki, Nima Asgharbeigi
363 %~ http://www.ece.rice.edu/~mam15/geo_kmedoid_AIPR08.pdf
364 %~
365 %~ An Efficient K-Medoids-Based Algorithm Using Previous Medoid Index, Triangular Inequality Elimination Criteria, and Partial Distance Search
366 %~ Shu-Chuan Chu,
367 %~ John F. Roddick,
368 %~ J. S. Pan
369 %~ Data Warehousing and Knowledge Discovery
370 %~ Lecture Notes in Computer Science Volume 2454, 2002, pp 63-72
371 %~
372 %~ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3069&rep=rep1&type=pdf
373 %~ An efficient approach to scale up k-medoid based algorithms in large databases
374 %~ Maria Camila N. Barioni, Humberto L. Razente, Agma J. M. Traina, Caetano Traina Jr. ∗
375 %~ XXI Simpósio Brasileiro de Banco de Dados
376 %~
377 %~ Computational Science and Its Applications – ICCSA 2005
378 %~ Lecture Notes in Computer Science Volume 3482, 2005, pp 181-189
379 %~ A New and Efficient K-Medoid Algorithm for Spatial Clustering
380 %~ Qiaoping Zhang,
381 %~ Isabelle Couloigner
382 %~
383 %~ == parallel
384 %~
385 %~ Scaling Up Machine Learning: Parallel and Distributed Approaches
386 %~ Ron Bekkerman, Mikhail Bilenko, John Langford
387 %~
388 %~ http://www.cs.umn.edu/tech_reports_upload/tr2001/01-001.pdf
389 %~ http://www.cs.umn.edu/research/technical_reports/view/01-001
390 %~ http://www.cs.cmu.edu/~lingwang/lectures/paralleldatamining2013.pdf
391 %~ ...
392 %~
393 %~ == k-medoids parallel
394 %~
395 %~ Parallelising the k-Medoids Clustering Problem Using Space-Partitioning
396 %~ Alejandro Arbelaez, Luis Quesada
397 %~ http://www.aaai.org/ocs/index.php/SOCS/SOCS13/paper/viewFile/7225/6231
398 %~
399 %~ K-Medoids: CUDA Implementation
400 %~ Douglas Roberts
401 %~
402 %~ Parallelization of K-medoid clustering algorithm
403 %~ Aljoby, W. ; Queen Arwa Univ., Yemen ; Alenezi, K.
404 %~ Published in:
405 %~ Information and Communication Technology for the Muslim World (ICT4M), 2013 5th International Conference on
406 %~ Date of Conference: 26-27 March 2013
407 %~ Page(s):
408 %~ 1 - 4
409 %~ Print ISBN:
410 %~ 978-1-4799-0134-0
411 %~ INSPEC Accession Number:
412 %~ 13518450
413 %~
414 %~ R package sprint
415 %~ http://www.ed.ac.uk/schools-departments/pathway-medicine/our-research/ghazal-group/pathway-informatics/sprint/download
416 %~ http://www.biomedcentral.com/1471-2105/9/558
417 %~ Software
418 %~ SPRINT: A new parallel framework for R
419 %~ Jon Hill1*, Matthew Hambley1, Thorsten Forster2, Muriel Mewissen2, Terence M Sloan1, Florian Scharinger1, Arthur Trew1 and Peter Ghazal2
420 %~ http://www.biomedcentral.com/content/pdf/1471-2105-9-558.pdf
421 %~
422 %~ ???
423 %~
424 %~ BIRCH: an efficient data clustering method for very large databases
425 %~ Authors: Tian Zhang Computer Sciences Dept., Univ. of Wisconsin-Madison
426 %~ Raghu Ramakrishnan Computer Sciences Dept., Univ. of Wisconsin-Madison
427 %~ Miron Livny Computer Sciences Dept., Univ. of Wisconsin-Madison
428 %~ Published in:
429 %~ SIGMOD '96 Proceedings of the 1996 ACM SIGMOD international conference on Management of data
430 %~ Pages 103-114
431 %~ ACM New York, NY, USA ©1996
432 %~ ISBN:0-89791-794-4 doi>10.1145/233269.233324
433 %~
434 %~ find geometric median (not medoid)
435 %~ http://users.jyu.fi/~samiayr/pdf/ayramo_eurogen05.pdf
436 %~
437 %~ ...
438 %~ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.9449&rep=rep1&type=pdf
439 %~
440 %~ http://biostats.bepress.com/cgi/viewcontent.cgi?article=1003&context=ucbbiostat
441 %~ a new PAM algo...
442 %~
443 %~ k-medoids initialization :
444 %~ http://seer.lcc.ufmg.br/index.php/jidm/article/viewFile/99/82