Hierarchical Clustering and Validity Assessment
Identifieur interne : 004381 ( Main/Exploration ); précédent : 004380; suivant : 004382Hierarchical Clustering and Validity Assessment
Auteurs : Frédéric Cao [France] ; José-Luis Lisani [Espagne] ; Jean-Michel Morel [France] ; Pablo Musé [Uruguay] ; Frédéric Sur [France]Source :
- Lecture Notes in Mathematics [ 0075-8434 ]
Abstract
The unsupervised classification of points into groups is commonly referred to as clustering or grouping. Clustering aims at discovering structure in a point data set by dividing it into its natural groups. There are three classical problems related to the construction of the right clusters. The first is evaluating the validity of a cluster candidate. In other words, is a group of points really a cluster, i.e. a group with a large enough density? The second problem is that meaningful clusters can contain or be contained in other meaningful clusters. A rule is needed to define locally optimal clusters by inclusion. This rule, however, is not enough to interpret correctly the data. The third problem is defining a correct merging rule between meaningful clusters, and thus being able to decide whether they should stay separate or unit. A unified a contrario method will be proposed for these problems. In continuation, some complexity issues and heuristics to find sound candidate clusters will be considered. In the next chapters, the clustering theory developed here will find a main application in shape recognition: the grouping of several local matches into a more global shape matching.
Url:
DOI: 10.1007/978-3-540-68481-7_7
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002626
- to stream Istex, to step Curation: 002593
- to stream Istex, to step Checkpoint: 000E09
- to stream Main, to step Merge: 004492
- to stream Main, to step Curation: 004381
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Hierarchical Clustering and Validity Assessment</title><author wicri:is="90%"><name sortKey="Cao, Frederic" sort="Cao, Frederic" uniqKey="Cao F" first="Frédéric" last="Cao">Frédéric Cao</name></author><author wicri:is="90%"><name sortKey="Lisani, Jose Luis" sort="Lisani, Jose Luis" uniqKey="Lisani J" first="José-Luis" last="Lisani">José-Luis Lisani</name></author><author wicri:is="90%"><name sortKey="Morel, Jean Michel" sort="Morel, Jean Michel" uniqKey="Morel J" first="Jean-Michel" last="Morel">Jean-Michel Morel</name></author><author wicri:is="90%"><name sortKey="Muse, Pablo" sort="Muse, Pablo" uniqKey="Muse P" first="Pablo" last="Musé">Pablo Musé</name></author><author wicri:is="90%"><name sortKey="Sur, Frederic" sort="Sur, Frederic" uniqKey="Sur F" first="Frédéric" last="Sur">Frédéric Sur</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A2188DCDE83F4329A305EAFDF49B985366805C29</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-68481-7_7</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-D0TH74X1-5/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002626</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002626</idno><idno type="wicri:Area/Istex/Curation">002593</idno><idno type="wicri:Area/Istex/Checkpoint">000E09</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000E09</idno><idno type="wicri:doubleKey">0075-8434:2008:Cao F:hierarchical:clustering:and</idno><idno type="wicri:Area/Main/Merge">004492</idno><idno type="wicri:Area/Main/Curation">004381</idno><idno type="wicri:Area/Main/Exploration">004381</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Hierarchical Clustering and Validity Assessment</title><author wicri:is="90%"><name sortKey="Cao, Frederic" sort="Cao, Frederic" uniqKey="Cao F" first="Frédéric" last="Cao">Frédéric Cao</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>DxO Labs, 3 rue Nationale, 92100 Boulogne Billancourt</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Boulogne-Billancourt</settlement></placeName></affiliation><affiliation></affiliation></author><author wicri:is="90%"><name sortKey="Lisani, Jose Luis" sort="Lisani, Jose Luis" uniqKey="Lisani J" first="José-Luis" last="Lisani">José-Luis Lisani</name><affiliation wicri:level="1"><country xml:lang="fr">Espagne</country><wicri:regionArea>Dep. Matemàtiques i Informàtica, University Balearic Islands, ctra. Valldemossa km.7,5, 07122 Palma de Mallorca, Balears</wicri:regionArea><wicri:noRegion>Balears</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Espagne</country></affiliation></author><author wicri:is="90%"><name sortKey="Morel, Jean Michel" sort="Morel, Jean Michel" uniqKey="Morel J" first="Jean-Michel" last="Morel">Jean-Michel Morel</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Ecole Normale Supérieure de Cachan, CMLA, 61 av. du Président Wilson, 94235 Cachan Cédex</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Cachan Cédex</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author wicri:is="90%"><name sortKey="Muse, Pablo" sort="Muse, Pablo" uniqKey="Muse P" first="Pablo" last="Musé">Pablo Musé</name><affiliation wicri:level="1"><country xml:lang="fr">Uruguay</country><wicri:regionArea>Instituto de Ingeniería Eléctrica, Julio Herrera y Reissig 565, 11300 Montevideo</wicri:regionArea><wicri:noRegion>11300 Montevideo</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Uruguay</country></affiliation></author><author wicri:is="90%"><name sortKey="Sur, Frederic" sort="Sur, Frederic" uniqKey="Sur F" first="Frédéric" last="Sur">Frédéric Sur</name><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>Loria Bat. C - projet Magrit Campus Scientifique, 54506 Vandoeuvre-lès-Nancy Cédex, BP 239</wicri:regionArea><wicri:noRegion>BP 239</wicri:noRegion><wicri:noRegion>BP 239</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Mathematics</title><idno type="ISSN">0075-8434</idno><idno type="ISSN">0075-8434</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0075-8434</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The unsupervised classification of points into groups is commonly referred to as clustering or grouping. Clustering aims at discovering structure in a point data set by dividing it into its natural groups. There are three classical problems related to the construction of the right clusters. The first is evaluating the validity of a cluster candidate. In other words, is a group of points really a cluster, i.e. a group with a large enough density? The second problem is that meaningful clusters can contain or be contained in other meaningful clusters. A rule is needed to define locally optimal clusters by inclusion. This rule, however, is not enough to interpret correctly the data. The third problem is defining a correct merging rule between meaningful clusters, and thus being able to decide whether they should stay separate or unit. A unified a contrario method will be proposed for these problems. In continuation, some complexity issues and heuristics to find sound candidate clusters will be considered. In the next chapters, the clustering theory developed here will find a main application in shape recognition: the grouping of several local matches into a more global shape matching.</div></front></TEI><affiliations><list><country><li>Espagne</li><li>France</li><li>Uruguay</li></country><region><li>Île-de-France</li></region><settlement><li>Boulogne-Billancourt</li><li>Cachan Cédex</li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Cao, Frederic" sort="Cao, Frederic" uniqKey="Cao F" first="Frédéric" last="Cao">Frédéric Cao</name></region><name sortKey="Morel, Jean Michel" sort="Morel, Jean Michel" uniqKey="Morel J" first="Jean-Michel" last="Morel">Jean-Michel Morel</name><name sortKey="Morel, Jean Michel" sort="Morel, Jean Michel" uniqKey="Morel J" first="Jean-Michel" last="Morel">Jean-Michel Morel</name><name sortKey="Sur, Frederic" sort="Sur, Frederic" uniqKey="Sur F" first="Frédéric" last="Sur">Frédéric Sur</name><name sortKey="Sur, Frederic" sort="Sur, Frederic" uniqKey="Sur F" first="Frédéric" last="Sur">Frédéric Sur</name></country><country name="Espagne"><noRegion><name sortKey="Lisani, Jose Luis" sort="Lisani, Jose Luis" uniqKey="Lisani J" first="José-Luis" last="Lisani">José-Luis Lisani</name></noRegion><name sortKey="Lisani, Jose Luis" sort="Lisani, Jose Luis" uniqKey="Lisani J" first="José-Luis" last="Lisani">José-Luis Lisani</name></country><country name="Uruguay"><noRegion><name sortKey="Muse, Pablo" sort="Muse, Pablo" uniqKey="Muse P" first="Pablo" last="Musé">Pablo Musé</name></noRegion><name sortKey="Muse, Pablo" sort="Muse, Pablo" uniqKey="Muse P" first="Pablo" last="Musé">Pablo Musé</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004381 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004381 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:A2188DCDE83F4329A305EAFDF49B985366805C29
|texte= Hierarchical Clustering and Validity Assessment
}}
| This area was generated with Dilib version V0.6.33. |  |