Paving the way to next generation data-stream clustering: towards a unique and statistically valid cluster structure at any time step

Pascal Cuxac; Alain Lelu; Martine Cadot

hal-00579770, version 1

Paving the way to next generation data-stream clustering: towards a unique and statistically valid cluster structure at any time step

Pascal Cuxac () ¹, Alain Lelu ( Auteur à contacter de préférence ) ^2, 3, 4, Martine Cadot () ⁵

International Journal of Data Mining, Modelling and Management (IJDMMM) 3, 4 (2011) 341-360

Résumé : In the domain of data-stream clustering, e.g. dynamic text mining, our goal is a two-fold and long term one: 1) at each data input, the resulting cluster structure has to be unique, independent of the order of the preceding inputs, 2) this structure has to be meaningful for an expert, e.g. not composed of a huge "catch-all" cluster in a cloud of tiny specific ones, as is often the case with large sparse datatables. The first preliminary condition is satisfied by our Germen density-mode seeking algorithm, but the relevance of the clusters vis-à-vis expert judgment relies on the definition of a data density, relying itself on the type of graph chosen for embedding the similarities between text inputs. Having already demonstrated the dynamic behavior of Germen algorithm, we focus here on appending a Monte-Carlo method for extracting statistically valid inter-text links, which looks promising applied both to an excerpt of the Pascal bibliographic database, and to the Reuters-RCV1 news test collection. Time and space complexity of our algorithms are eventually discussed.

1 : Institut de l'information scientifique et technique (INIST)
CNRS : UPS76
2 : KIWI (LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : Laboratoire de Semio-Linguistique, Didactique et Informatique (LASELDI)
Université de Franche-Comté
4 : Institut des Sciences de la Communication du CNRS (ISCC)
CNRS : UPS3088
5 : ABC (Apprentissage et Biologie Computationnelle) (LORIA)
CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

hal-00579770, version 1
http://hal.archives-ouvertes.fr/hal-00579770
oai:hal.archives-ouvertes.fr:hal-00579770
Contributeur : Martine Cadot <>
Soumis le : Jeudi 24 Mars 2011, 20:24:01
Dernière modification le : Vendredi 16 Mars 2012, 16:19:33

Voir la fiche détaillée

Documents associés

DOI : 10.1504/IJDMMM.2011.042933

Exporter

Bibtex EndNote TEI RefWorks

%% hal-00579770, version 1
%% http://hal.archives-ouvertes.fr/hal-00579770
@article{cuxac:hal-00579770,
    hal_id = {hal-00579770},
    url = {http://hal.archives-ouvertes.fr/hal-00579770},
    title = {{Paving the way to next generation data-stream clustering: towards a unique and statistically valid cluster structure at any time step}},
    author = {Cuxac, Pascal and Lelu, Alain and Cadot, Martine},
    abstract = {{In the domain of data-stream clustering, e.g. dynamic text mining, our goal is a two-fold and long term one: 1) at each data input, the resulting cluster structure has to be unique, independent of the order of the preceding inputs, 2) this structure has to be meaningful for an expert, e.g. not composed of a huge "catch-all" cluster in a cloud of tiny specific ones, as is often the case with large sparse datatables. The first preliminary condition is satisfied by our Germen density-mode seeking algorithm, but the relevance of the clusters vis-{\`a}-vis expert judgment relies on the definition of a data density, relying itself on the type of graph chosen for embedding the similarities between text inputs. Having already demonstrated the dynamic behavior of Germen algorithm, we focus here on appending a Monte-Carlo method for extracting statistically valid inter-text links, which looks promising applied both to an excerpt of the Pascal bibliographic database, and to the Reuters-RCV1 news test collection. Time and space complexity of our algorithms are eventually discussed.}},
    keywords = {data stream clustering; text mining; incremental algorithm; randomisation test; density mode clustering; graph validation; data mining},
    language = {Anglais},
    affiliation = {Institut de l'information scientifique et technique - INIST , KIWI - LORIA , Laboratoire de Semio-Linguistique, Didactique et Informatique - LASELDI , Institut des Sciences de la Communication du CNRS - ISCC , ABC (Apprentissage et Biologie Computationnelle) - LORIA},
    pages = {341-360},
    journal = {International Journal of Data Mining, Modelling and Management (IJDMMM)},
    volume = {3},
    number = {4 },
    audience = {internationale },
    doi = {10.1504/IJDMMM.2011.042933 },
    year = {2011},
}

%F hal-00579770, version 1
%0 Journal Article
%U http://hal.archives-ouvertes.fr/hal-00579770
%2 INFO:INFO_OH;INFO:INFO_IR;INFO:INFO_DL;INFO:INFO_TT;STAT:AP
%T Paving the way to next generation data-stream clustering: towards a unique and statistically valid cluster structure at any time step
%A Cuxac, Pascal
%A Lelu, Alain
%A Cadot, Martine
%+ Institut de l'information scientifique et technique - INIST , KIWI - LORIA , Laboratoire de Semio-Linguistique, Didactique et Informatique - LASELDI , Institut des Sciences de la Communication du CNRS - ISCC , ABC (Apprentissage et Biologie Computationnelle) - LORIA
%X In the domain of data-stream clustering, e.g. dynamic text mining, our goal is a two-fold and long term one: 1) at each data input, the resulting cluster structure has to be unique, independent of the order of the preceding inputs, 2) this structure has to be meaningful for an expert, e.g. not composed of a huge "catch-all" cluster in a cloud of tiny specific ones, as is often the case with large sparse datatables. The first preliminary condition is satisfied by our Germen density-mode seeking algorithm, but the relevance of the clusters vis-à-vis expert judgment relies on the definition of a data density, relying itself on the type of graph chosen for embedding the similarities between text inputs. Having already demonstrated the dynamic behavior of Germen algorithm, we focus here on appending a Monte-Carlo method for extracting statistically valid inter-text links, which looks promising applied both to an excerpt of the Pascal bibliographic database, and to the Reuters-RCV1 news test collection. Time and space complexity of our algorithms are eventually discussed.
%G Anglais
%R 10.1504/IJDMMM.2011.042933
%J International Journal of Data Mining, Modelling and Management (IJDMMM)
%2 internationale
%8 2011-00-00
%V 3
%N 4
%P 341-360
%K data stream clustering; text mining; incremental algorithm; randomisation test; density mode clustering; graph validation; data mining

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00579770"><analytic>
<author><persName><forename>Pascal</forename><surname>Cuxac</surname></persName>
<affiliation>
<orgName type="laboratory">INIST</orgName>
<orgName type="team">Institut de l'information scientifique et technique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UPS76</orgName>
</affiliation>
</author>
<author><persName><forename>Alain</forename><surname>Lelu</surname></persName>
<affiliation>
<orgName type="laboratory">LORIA</orgName>
<orgName type="team">KIWI</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LASELDI</orgName>
<orgName type="team">Laboratoire de Semio-Linguistique, Didactique et Informatique</orgName>
<country>FR</country>
<orgName type="institution">Université de Franche-Comté</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">ISCC</orgName>
<orgName type="team">Institut des Sciences de la Communication du CNRS</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UPS3088</orgName>
</affiliation>
</author>
<author><persName><forename>Martine</forename><surname>Cadot</surname></persName>
<affiliation>
<orgName type="laboratory">LORIA</orgName>
<orgName type="team">ABC (Apprentissage et Biologie Computationnelle)</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">Paving the way to next generation data-stream clustering: towards a unique and statistically valid cluster structure at any time step</title></analytic><monogr><title level="j" type="main">International Journal of Data Mining, Modelling and Management (IJDMMM)</title><imprint><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="vol">3</biblScope><biblScope type="issue">4</biblScope><biblScope type="pp">341-360</biblScope></imprint></monogr><idno type="doi">10.1504/IJDMMM.2011.042933</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00579770</idno></biblStruct>
</listBibl>
</listBibl>