On the number of clusterings in a hierarchical classication model with overlapping clusters

• Autorzy: Roman, A. , Podolak, I. T. , Deszyńska, A.
• Języki publikacji: EN

Abstrakty

EN

This paper shows a new combinatorial problem which emerged from studies on an articial intelligence classication model of a hierarchical classier. We introduce the notion of proper clustering and show how to count their number in a special case when 3 clusters are allowed. An algorithm that generates all clusterings is given. We also show that the proposed approach can be generalized to any number of clusters, and can be automatized. Finally, we show the relationship between the problem of counting clusterings and the Dedekind problem.

• Czasopismo: Schedae Informaticae
• Rocznik: 2011
• Tom: Vol. 20
• Strony: 137-157
• Opis fizyczny: Bibliogr. 23 poz., tab.

Twórcy

autor

Roman, A.

autor

Podolak, I. T.

autor

Deszyńska, A.

• Institute of Computer Science, Jagiellonian University, Prof. Stanisława Łojasiewicza 6, 30-348 Cracow, Poland,

Bibliografia

• [1] Schapire R. E.; The strength of weak learnability, Machine Learning, 5, 1990, pp. 197-227.
• [2] Eibl G., Pfeier K.-P.; Multiclass boosting for weak classiers, Journal of Machine Learning, 6, 2005, pp. 189-210.
• [3] Podolak I. T.; Hierarchical Classier with Overlapping class groups, Expert Systems with Applications, 34(1), 2008, pp. 673-682.
• [4] Podolak I. T.; Hierarchical rules for a hierarchical classier, Adaptive and Natural Computing Algorithms, 4431, 2007, pp. 749-757.
• [5] On-Line Encyclopedia of Integer Sequences. Available via http://www.research.att. com/~njas/sequences.
• [6] Lipski W.; Kombinatoryka dla programistow, Wydawnictwo Naukowe PWN, 2007.
• [7] Dedekind R.; Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Festschrift Hoch. Braunschweig u. ges. Werke(II), 1897, pp. 103-148.
• [8] Church R.; Numerical analysis of certain free distributive structures, Duke Math. J., 6(3), 1940, pp. 732{734.
• [9] Ward M.; Note on the order of free distributive lattices, Bull. Amer. Math. Soc., 52, 1946, pp. 423.
• [10] Yamamoto K. A.; A note on the order of free distributive lattices, The Science Reports of the Kanazawa University, 2, 1953, pp. 5-6.
• [11] Gilbert E. N.; Lattice theoretic properties of frontal switching functions, J. Math. Phys., 33(1), 1954, pp. 57-67.
• [12] Yamamoto K. A.; Logaritmic order of free distributive lattice, J. Math. Soc. Japan, 6(3{4), 1954, pp. 343{353.
• [13] Korobkov B. K.; On monotone functions in Boolean algebra (in Russian), Problemy Kibernet., 13, 1965, pp. 5-28.
• [14] Hansel G.; Sur le nombre des fonctions boolennes monotones de n variables, C.C. Acad. Sci Paris, 262(20), 1966, pp. 1088{1090.
• [15] Kleitman D.; On Dedekind's problem: The number of monotone Boolean functions, Proc. Amer. Math. Soc., 21, 1969, pp. 677-682.
• [16] Korshunov A. D.; The number of monotone Boolean functions, Problemy Kibernet., 38, 1981, pp. 5-108.
• [17] Kisielewicz A.; A solution of Dedekind's problem on the number of isotone Boolean functions, Journal für die Reine und Angewandte Mathematik, 386, 1988, pp. 139-144.
• [18] Tombak M., Isotam A., Tamme T.; On Logical Method for Counting Dedekind Numbers, Lecture Notes in Computer Science, 2138, 2001, pp. 424427.
• [19] Church R.; Enumeration by rank of the elements of the free distributive lattice with seven generators, Not. Amer. Math. So., 12, 1965, pp. 724.
• 20] Wiedemann D.; A computation of the eighth Dedekind number, Order, 8, 1991, pp. 5-6.
• [21] Dedekind's Problem. Available via http://www.mathpages.com/home/kmath030.htm.
• [22] Kilibarda G., Jovovic V.; On the number of monotone Boolean functions with xes number of lower units (in Russian), Intellektualnye sistemy, 7, 2003, pp. 193-217.
• [23] Kilibarda G., Jovovic V.; Antichains of Multisets, Journal of Integer Sequences, 7, 2007.