Some Symmetry Based Classifiers

• Autorzy: Saha S. , Bandyopadhyay S.
• Języki publikacji: EN

Abstrakty

EN

In this paper, a novel point symmetry based pattern classifier (PSC) is proposed. A recently developed point symmetry based distance is utilized to determine the amount of point symmetry of a particular test pattern with respect to a class prototype. Kd-tree based nearest neighbor search is used for reducing the complexity of point symmetry distance computation. The proposed point symmetry based classifier is well-suited for classifying data sets having point symmetric classes, irrespective of any convexity, overlap or size. In order to classify data sets having line symmetry property, a line symmetry based classifier (LSC) along the lines of PSC is thereafter proposed in this paper. To measure the total amount of line symmetry of a particular point in a class, a new definition of line symmetry based distance is also provided. Proposed LSC preserves the advantages of PSC. The performance of PSC and LSC are demonstrated in classifying fourteen artificial and real-life data sets of varying complexities. For the purpose of comparison, k-NN classifier and the well-known support vector machine (SVM) based classifiers are executed on the data sets used here for the experiments. Statistical analysis, ANOVA, is also performed to compare the performance of these classification techniques.

Słowa kluczowe

EN

pattern classification; point symmetry; Kd-tree; symmetry based distance; nearest neighbour rule; line symmetry

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 90, nr 1-2
• Strony: 107--123
• Opis fizyczny: bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Saha S.

autor

Bandyopadhyay S.

• Machine Intelligence Unit Indian Statistical Institute Kolkata - 700 108, India,

Bibliografia

• [1] Anderberg, M. R.: Computational Geometry: Algorithms and Applications, Springer, 2000.
• [2] Anderson, T. W., Scolve, S.: Introduction to the Statistical Analysis of Data, Houghton Mifflin, 1978.
• [3] Asuncion, A., Newman, D.: UCI Machine Learning Repository, 2007.
• [4] Attneave, F.: Symmetry Information and Memory for Pattern, Am. J. Psychology, 68, 1995, 209-222.
• [5] Bandyopadhyay, S., Maulik, U.: Efficient prototype reordering in nearest neighbor classification, Pattern Recognition, 35, 2002, 2791 2799.
• [6] Bandyopadhyay, S., Saha, S.: GAPS: A Clustering Method Using A New Point Symmetry Based Distance Measure, Pattern Recog., 40, 2007, 3430-3451.
• [7] Bentley, J. L., Weide, B. W., Yao, A. C.: Optimal expected-time algorithms for closest point problems, ACM Transactions on Mathematical Software, 6(4), 1980, 563-580.
• [8] Chou, C. H., Su, M. C., Lai, E.: Symmetry as A new Measure for Cluster Validity, in: 2nd WSEAS Int. Conf. on Scientific Computation and Soft Computing, Crete, Greece, 2002, 209-213.
• [9] Cover, T. M., Hart, P.: Nearest Neighbor pattern classification, IEEE Trans. Information Theory, 13, 1967, 21-27.
• [10] Crammer, K., Singer, Y.: On the Algorithmic Implementation of Multi-class SVMs, JMLR, 2001.
• [11] Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and other kernel-based learning methods, Cambridge University Press, 2000.
• [12] Fisher, R. A.: The Use of Multiple Measurements in Taxonomic Problems, Annals of Eugenics, 3, 1936, 179-188.
• [13] Fix, E., Hodges, J.: Discriminatory analysis, nonparametric discrimination: consistency properties, Technical Report 4, USAF School of Aviation Medicine, Randolph Field, Texas, 1951.
• [14] Friedman, J. H., Bently, J. L., Finkel, R. A.: An Algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software, 3(3), 1977, 209-226.
• [15] Gonzalez, R. C., Woods, R. E.: Digital Image Processing, Addison-Wesley, Massachusetts, 1992.
• [16] Joachims, T.: SVMmulticlass: Multi-Class Support Vector Machine, 2007, Http://svmlight.joachims.org/svm multiclass.html.
• [17] Jolliffe, I.: Principal Component Analysis, Springer Series in Statistics, England, 1986.
• [18] Liu, C.-L., Nakagawa, M.: Prototype Learning Algorithms for Nearest Neighbor Classifier with Application to Handwritten Character Recognition, ICDAR -99: Proceedings of the Fifth International Conference on Document Analysis and Recognition, IEEE Computer Society, Washington, DC, USA, 1999.
• 19] Mount, D. M., Arya, S.: ANN: A Library for Approximate Nearest Neighbor Searching, 2005, Http://www.cs.umd.edu/_mount/ANN.
• [20] Pal, S. K., Bandyopadhyay, S., Murthy, C. A.: Genetic algorithms for generation of class boundaries, IEEE Trans. System Man Cybernet, 28(6), 1998, 816-828.
• [21] Pal, S. K., Majumder, D. D.: Fuzzy sets and decision making approaches in vowel and speaker recognition, IEEE Transactions on Systems, Man, and Cybernetics, 7, 1977, 625-629.
• [22] Su, M.-C., Chou, C.-H.: A Modified Version of the K-means Algorithm with a Distance Based on Cluster Symmetry, IEEE Transactions Pattern Analysis and Machine Intelligence, 23(6), 2001, 674-680.