Directed binary hierarchies and directed ultrametrics. (English) Zbl 1360.62340
Summary: Directed binary hierarchies have been introduced in order to give a graphical reduced representation of a family of association rules. This type of structure extends the classical binary hierarchical classification in a very specific way. In this paper an accurate formalization of this new structure is studied. A directed hierarchy is defined as a set of ordered pairs of subsets of the initial individual set satisfying specific conditions. A new notion of directed ultrametricity is studied. The main result consists in establishing a bijective correspondence between a directed ultrametric space and a directed binary hierarchy. Finally, an algorithm is proposed in order to transform a directed ultrametric structure into a graphical representation associated with a directed binary hierarchy.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62P15 | Applications of statistics to psychology |
References:
| [1] | AGRAWAL, R., IMIELINSKY, T., and SWAMI, A. (1993), ”Mining Association Rules Between Sets of Items in Large Databases”, in Proceedings of the ACM SIGMOD’93, pp. 207–216. |
| [2] | BENZÉCRI, J.P. (1973), L’Analyse des Données : La Taxinomie (Vol. 1), Paris: Dunod. · Zbl 0297.62038 |
| [3] | DURAND, C., and FICHET, B. (1988), ”One to One Correspondence in Pyramidal Representation: An Unified Approach”, in Classification and Related Methods of Data Analysis, ed. H.H. Bock, Amsterdam: North-Holland, pp. 85–90. · Zbl 0733.92029 |
| [4] | GORDON, A.D. (1999), Classification, London: Chapman & Hall. |
| [5] | GRAS, R. (1979), Contribution à L’étude Expérimentale et L’analyse de Certaines Acquisitions Cognitives et de Certains Objectifs Didactiques en Mathématiques, Doctorat d’État, PhD thesis, Université de Rennes 1. |
| [6] | GRAS, R.,AG ALMOULOUD, S., BAILLEUL,M., LARHER, A.A., POLO,M., RATSIMBARAJOHN, H., and TOTOHASINA, A. (1996), L’implication Statistique - Nouvelle Méthode Exploratoire de Données, France: La Pensée Sauvage. |
| [7] | GRAS, R., GUILLET, F., SPAGNOLO, F., and SUZUKI, E. (eds.) (2008), Statistical Implicative Analysis, Studies in Computational Intelligence (Vol. 127), Berlin Heidelberg: Springer. · Zbl 1343.62003 |
| [8] | GRAS, R., and KUNTZ, P. (2005), ”Discovering R-rules with a Directed Hierarchy”, Soft Computing, 10, 453–460. · Zbl 1096.68701 · doi:10.1007/s00500-005-0506-8 |
| [9] | GRAS, R., KUNTZ, P., and RÉGNIER, J-C. (2004), ”Significativité des Niveaux d’une Hiérarchie Orientée en Analyse Statistique Implicative”, in 11-èmes Rencontres de la Société Francophone de Classification, ed. Université de Bordeaux, pp. 39–50. |
| [10] | GUILLET, F., and HAMILTON, H.J. (eds.) (2007), QualityMeasures in DataMining, Studies in Computational Intelligence (Vol. 43), Berlin Heidelberg: Springer. |
| [11] | JOHNSON, S.C. (1967), ”Hierarchical Clustering Schemes”, Psychometrika, 32, 241–254. · Zbl 1367.62191 · doi:10.1007/BF02289588 |
| [12] | KLEMENTTINEN,M.,MANILLA, H., RONKAINEN, P., TOIVONEN, H., and VERKAMO, A.I. (1994), ”Finding Interesting Rules from Large Sets of Discovered Association Rules”, in Proceedings of the 3rd International Conference on Information and Knowledge Management, ed. ACM, pp. 401–407. |
| [13] | LENT, B., SWAMI, A.N., and WIDOW, J. (1997), ”Clustering Association Rules”, in Proceedings of the 13th Conference on Data Engineering, IEEE Computer Society: Washington, pp. 220–231. |
| [14] | LERMAN, I-C. (1970), Les Bases de la Classification Automatique, Paris: Gauthier-Villars. · Zbl 0199.51402 |
| [15] | LERMAN, I-C. (1981), Classification et Analyse Ordinale des Données, Paris: Dunod. |
| [16] | LERMAN, I-C. (2007), ”Sur les Différentes Expressions Formelles d’une Hiérarchie Binaire Symétrique ou Implicative”, in Rencontres de la Société Francophone de Classification, ed. SupTélécom Paris, pp. 139–142. |
| [17] | LERMAN, I-C. (2008), ”Analyse Logique, Combinatoire et Statistique de la Construction d’une Hiérarchie Binaire Implicative; Niveaux et Noeuds Significatifs”, Mathématiques et Sciences Humaines, Mathematics and Social Sciences, 184, 47–103. · Zbl 1171.62040 · doi:10.4000/msh.10974 |
| [18] | LERMAN, I-C., and AZÉ, J. (2007), ”A New Probabilistic Measure of Interestingness for Association Rules, Based on the Likelihood of the Link”, in Quality Measures in Data Mining, Studies in Computational Intelligence (Vol. 43), eds. F. Guillet and H.J. Hamilton, Berlin Heidelberg: Springer, pp. 207–236. · Zbl 1397.62023 |
| [19] | LERMAN, I-C., GRAS, R., and ROSTAM, H. (1981), ”Élaboration et Évaluation d’un Indice d’Implication pour des Données Binaires I et II”, Mathématiques et Sciences Humaines, 74–75, 5–35, 5–47. · Zbl 0493.62093 |
| [20] | LERMAN, I-C. (1991), ”Foundations of the Likelihood Linkage Analysis (lla) Classification Method”, Stochastic Models and Data Analysis, 7, 63–76. · Zbl 0800.62320 · doi:10.1002/asm.3150070107 |
| [21] | LOEVINGER, J. (1947), ”A Systematic Approach to the Construction and Evaluation of Tests of Ability”, Psychological Monographs, 61, 1–49. · doi:10.1037/h0093565 |
| [22] | MURTAGH, F. (1984), ”Counting Dendograms: A Survey”, Discrete Applied Mathematics, 7, 191–199. · Zbl 0528.62055 · doi:10.1016/0166-218X(84)90066-0 |
| [23] | TAKEUCHI, A., SAITO, T., and YADOHISA, H. (2007), ”Asymmetric Agglomerative Hierarchical Clustering Algorithms and Their Evaluation”, Journal of Classification, 24, 123–143. · Zbl 1130.62063 · doi:10.1007/s00357-007-0002-1 |
| [24] | TOIVONEN, H., KLMENTTINEN,M., RONKAIREN, P., HATONEN, K., and MANILA, H. (1995), ”Pruning and Grouping Discovered Association Rules”, in Workshop Notes of the ECML Workshop on Statistics, Machine Learning and Knowledge Discovering in Databases, Crete, Greece, pp. 47–52. |
| [25] | YADOHISA, H. (2002), ”Formulation of Asymmetric Agglomerative Hierarchical Clustering and Graphical Representation of its Results”, Bulletin of the Computational Statistics of Japan, 15, 309–316. |
| [26] | ZIELMAN, B., and HEISER, W.J. (1996), ”Models for Asymmetric Proximities”, British Journal of Mathematical and Statistical Psychology, 49, 127–146. · Zbl 0858.62101 · doi:10.1111/j.2044-8317.1996.tb01078.x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
