×

A formula for multiple classifiers in data mining based on Brandt semigroups. (English) Zbl 1168.94007

Classification of data plays one of the central roles in data mining and in practical applications of artificial intelligence methods in general (see [J. L. Yearwood and M. A. Mammadov, Classification technologies: optimization approaches to short text categorization. Tdea Group Inc. (2007)]). A well-known method of designing efficient multiple classifiers consists in representing them as several binary classifiers combined in one scheme. The main advantage of using combined multiple classifiers is that they can correct errors of individual binary classifiers and produce correct classifications despite individual classification errors. The problem of finding the number of errors of individual binary classifiers that a multiple classifier can correct in general is rather complicated. It is well-known that in full generality this problem is related to several other very difficult algorithmic problems (see [J. L. Yearwood and M. A. Mammadov [loc. cit.]). This note uses semigroup rings to introduce additional structure on the class sets of multiple classifiers, which makes it possible to generate these sets with a small number of generators. In special case of Brandt semigroups and their subsemigroups the authors have obtained a fairly concise formula for the number of errors of binary classifiers, which can be corrected by the corresponding multiple classifiers. This formula is the main result of paper. Examples are given to show that the formula does not directly generalize to all inverse semigroups and other classes of semigroups.

MSC:

94B05 Linear codes (general theory)
68P99 Theory of data
62P30 Applications of statistics in engineering and industry; control charts

Software:

BoosTexter
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alfaro, R., Kelarev, A.V.: Recent results on ring constructions for error-correcting codes. In: Algebraic Structures and Their Representations, XV Coloquio Latinoamericano de Algebra (Cocoyoc, Morelos, Mexico, July 20–26, 2003). Contemporary Math., vol. 376, pp. 1–12 (2005) · Zbl 1087.94028
[2] Alfaro, R., Kelarev, A.V.: On cyclic codes in incidence rings. Stud. Sci. Math. Hung. 43(1), 69–77 (2006) · Zbl 1174.94414
[3] Araújo, I.M., Kelarev, A.V., Solomon, A.: An algorithm for commutative semigroup algebras which are principal ideal rings with identity. Commun. Algebra 32(4), 1237–1254 (2004) · Zbl 1085.20042 · doi:10.1081/AGB-120028778
[4] Ash, C.J., Hall, T.E., Pin, J.-E.: On the varieties of languages associated with some varieties of finite monoids with commuting idempotents. Inf. Comput. 86(1), 32–42 (1990) · Zbl 0699.68091 · doi:10.1016/0890-5401(90)90024-C
[5] Auinger, K., Hall, T.E., Reilly, N.R., Zhang, S.: Congruences on the lattice of pseudovarieties of finite semigroups. Int. J. Algebra Comput. 7(4), 433–455 (1997) · Zbl 0885.20036 · doi:10.1142/S0218196797000198
[6] Bagirov, A.M., Yearwood, J.L.: A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems. Eur. J. Oper. Res. 170, 578–596 (2006) · Zbl 1085.90045 · doi:10.1016/j.ejor.2004.06.014
[7] Bagirov, A.M., Rubinov, A.M., Yearwood, J.: A global optimization approach to classification. Optim. Eng. 3, 129–155 (2002) · Zbl 1035.90060 · doi:10.1023/A:1020911318981
[8] Bagirov, A.M., Rubinov, A.M., Soukhoroukova, N.V., Yearwood, J.: Unsupervised and supervised data classification via nonsmooth and global optimization. Top 11, 1–93 (2003) · Zbl 1048.65059 · doi:10.1007/BF02578945
[9] Cazaran, J., Kelarev, A.V.: Generators and weights of polynomial codes. Arch. Math. (Basel) 69, 479–486 (1997) · Zbl 0898.94010
[10] Cazaran, J., Kelarev, A.V., Quinn, S.J., Vertigan, D.: An algorithm for computing the minimum distances of extensions of BCH codes embedded in semigroup rings. Semigroup Forum 73, 317–329 (2006) · Zbl 1145.94023 · doi:10.1007/s00233-006-0647-9
[11] Downey, R., Fellows, M.R., Whittle, G., Vardy, A.: The parameterized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29(2), 545–570 (1999) · Zbl 0943.68079 · doi:10.1137/S0097539797323571
[12] Easdown, D., East, J., FitzGerald, D.G.: Presentations of factorizable inverse monoids. Acta Sci. Math. (Szeged) 71(3–4), 509–520 (2005) · Zbl 1112.20049
[13] Easdown, D., Lavers, T.G.: The inverse braid monoid. Adv. Math. 186(2), 438–455 (2004) · Zbl 1113.20051 · doi:10.1016/j.aim.2003.07.014
[14] Easdown, D., Munn, W.D.: Trace functions on inverse semigroup algebras. Bull. Aust. Math. Soc. 52(3), 359–372 (1995) · Zbl 0845.20051 · doi:10.1017/S0004972700014854
[15] Easdown, D., Shneerson, L.M.: Principal Rees quotients of free inverse semigroups. Glasg. Math. J. 45(2), 263–267 (2003) · Zbl 1050.20041 · doi:10.1017/S0017089503001228
[16] Ferguson, B., Ghosh, R., Yearwood, J.L.: Modular neural network design for the problem of alphabetic character recognition. Int. J. Pattern Recogn. Artif. Intell. 19(2), 249–269 (2006) · Zbl 02218409 · doi:10.1142/S0218001405004009
[17] Gomes, G.M.S., Howie, J.M.: Semigroups with zero whose idempotents form a subsemigroup. Proc. R. Soc. Edinb. Sect. A 128, 265–281 (1998) · Zbl 0905.20043
[18] Gray, R., Ruškuc, N.: Generating sets of completely 0-simple semigroups. Commun. Algebra 33(12), 4657–4678 (2005) · Zbl 1102.20038 · doi:10.1080/00927870500276676
[19] Hall, T.E.: The radical of the algebra of any finite semigroup over any field. J. Aust. Math. Soc. Ser. A 11, 350–352 (1970) · Zbl 0241.20055 · doi:10.1017/S1446788700006753
[20] Hall, T.E.: Biprefix codes, inverse semigroups and syntactic monoids of injective automata. Theor. Comput. Sci. 32(1–2), 201–213 (1984) · Zbl 0567.68047 · doi:10.1016/0304-3975(84)90031-8
[21] Hall, T.E., Finite inverse semigroups and amalgamation. In: Semigroups and Their Applications (Chico, Calif., 1986), pp. 51–56 (1987)
[22] Hall, T.E.: Amalgamation for inverse and generalized inverse semigroups. Trans. Am. Math. Soc. 310, 313–323 (1988) · Zbl 0706.20045 · doi:10.1090/S0002-9947-1988-0965756-7
[23] Hall, T.E., Imaoka, T.: Representations and amalgamation of generalized inverse *-semigroups. Semigroup Forum 58, 126–141 (1999) · Zbl 0930.20055 · doi:10.1007/s002339900001
[24] Hall, T.E., Johnston, K.G.: The lattice of pseudovarieties of inverse semigroups. Pac. J. Math. 138, 73–88 (1989) · Zbl 0629.20031
[25] Hall, T.E., Kublanovskii, S.I., Margolis, S., Sapir, M.V., Trotter, P.G.: Algorithmic problems for finite groups and finite 0-simple semigroups. J. Pure Appl. Algebra 119(1), 75–96 (1997) · Zbl 0880.20040 · doi:10.1016/S0022-4049(96)00050-3
[26] Hall, T.E., Shoji, K.: Finite bands and amalgamation bases for finite semigroups. Commun. Algebra 30(2), 911–933 (2002) · Zbl 0999.20049 · doi:10.1081/AGB-120013191
[27] Howie, J.M.: Fundamentals of Semigroup Theory. Clarendon, Oxford (1995) · Zbl 0835.20077
[28] Imaoka, T., Hall, T.E.: Amalgamation of generalized inverse *-semigroups. In: Proc. 19th Symposium on Semigroups, Languages and their Related Fields (Matsue, 1995), pp. 8–14, Shimane Univ., Matsue (1995)
[29] Joachims, T.: Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms. The International Series in Engineering and Computer Science. Springer, Berlin (2002)
[30] Kelarev, A.V.: Ring Constructions and Applications. World Scientific, London (2002) · Zbl 0999.16036
[31] Kelarev, A.V.: Graph Algebras and Automata. Dekker, New York (2003) · Zbl 1070.68097
[32] Kelarev, A.V., Passman, D.S.: A description of incidence rings of group automata. Contemp. Math. 456, 27–33 (2008) · Zbl 1154.16015
[33] Lashkarizadeh, B.M., Samea, H.: Approximate amenability of certain semigroup algebras. Semigroup Forum 71(2), 312–322 (2005) · Zbl 1086.43002 · doi:10.1007/s00233-005-0516-y
[34] Luger, G.: Artificial Intelligence Structures and Strategies for Complex Problem Solving, 5th edn. Addison-Wesley, Reading (2005) · Zbl 1107.47011
[35] Mammadov, M.A., Rubinov, A.M., Yearwood, J.: The study of drug-reaction relationships using global optimization techniques. In: Optimization Methods and Software (2007) · Zbl 1116.92034
[36] Margolis, S.W., Meakin, J.C.: E-unitary inverse monoids and the Cayley graph of a group representation. J. Pure Appl. Algebra 58, 45–76 (1989) · Zbl 0676.20037 · doi:10.1016/0022-4049(89)90052-2
[37] Mitchell, J.D.: Turán’s graph theorem and maximum independent sets in Brandt semigroups. In: Semigroups and Languages, pp. 151–162. World Scientific, River Edge (2004) · Zbl 1189.20048
[38] Okniński, J.: Semigroup Algebras. Dekker, New York (1991)
[39] Schapire, R.E., Singer, Y.: BoosTexter: A boosting-based system for text categorization. Mach. Learn. 39(2/3), 135–168 (2000) · Zbl 0951.68561 · doi:10.1023/A:1007649029923
[40] Shevrin, L.N., Ovsyannikov, Ja.A.: Semigroups and their Subsemigroup Lattices. Kluwer, Dordrecht (1996) · Zbl 0858.20054
[41] Tilakaratne, C.D.: Stock market prediction based on quantified intermarket influence. PhD Thesis, University of Ballarat, Australia (2007)
[42] Yearwood, J.L., Mammadov, M.: Classification technologies: optimization approaches to short text categorization. Idea Group Inc. (2007)
[43] Yearwood, J.L., Stranieri, A.: The generic/actual argument model of practical reasoning. Decis. Support Syst. 41, 358–379 (2006) · doi:10.1016/j.dss.2004.07.004
[44] Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques. Elsevier, Amsterdam (2005) · Zbl 1076.68555
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.