First International Conference on Emerging Trends in Engineering and Technology

Rough Set Approach for Feature Reduction in Pattern Recognition through Unsupervised Artificial Neural Network
A. G. Kothari A.G. Keskar A.P. Gokhale Rucha Pranjali Lecturer Professor Professor Deshpande Deshmukh agkothari72@re B.Tech Student B.Tech Student diffmail.com Department of Electronics & Computer Science Engineering, VNIT, Nagpur Abstract
The Rough Set approach can be applied in pattern recognition at three different stages: pre-processing stage, training stage and in the architecture. This paper proposes the application of the Rough-Neuro Hybrid Approach in the pre-processing stage of pattern recognition. In this project, a training algorithm has been first developed based on Kohonen network. This is used as a benchmark to compare the results of the pure neural approach with the RoughNeuro hybrid approach and to prove that the efficiency of the latter is higher. Structural and statistical features have been extracted from the images for the training process. The number of attributes is reduced by calculating reducts and core from the original attribute set, which results into reduction in convergence time. Also, the above removal in redundancy increases speed of the process reduces hardware complexity and thus enhances the overall efficiency of the pattern recognition algorithm Keywords: core, dimensionality reduction, feature extraction, rough sets, reducts, unsupervised ANN as any type of ANN is the most general tool and can work well in noisy conditions also. The image data set in this project consists of printed alphanumeric characters in ten fonts. Since the input data contains lots of inconsistencies, the unsupervised type ANN is preferred. The result of suggested approach is used as a benchmark for comparison with the Rough set based approach. As the discernibility in features respective to inter class classification is not exploited in the unsupervised ANN approach; the attributes used can be redundant. Because of this, dimensionality of feature space increases which further makes the process complicated and time consuming. Since it is a real time application early convergence is also equally important. In such circumstances individualistic approach based on rough sets is required. The rough set based postulation basically exploits fully the above referred discernibility between the parameters required for inter-class classification. This is done by finding reducts and core using rough sets which reduce the dimensionality of the feature space [2]. But for a very huge data set like this, pure rough set approach will also have limitation of delayed convergence. Hence a rough set approach be used for preprocessing or attribute reduction and the reduced attribute set can be fed to the neural classifier for pattern recognition.

1. Introduction
In some cases of object classification, there may be a conflict regarding the exact class to which a data object belongs. It may belong to the boundary region between two classes and hence cannot be classified crisply. In such cases, when the boundary region is non-empty, the set is said to be rough. Rough Set Theory deals with the classification and analysis of such inconsistent data. For efficient pattern recognition, two main processes can be used: statistical process or artificial neural network based process. Because of numerous limitations of statistical processes and inherent advantages of ANN, the second approach is preferred

2. Image Extraction

Pre-Processing

&

feature

2.1 Image Pre-processing
The original data set is subjected to a number of preliminary processing steps to make it usable by the feature extraction algorithm. Pre-processing aims at producing data that is easy for the pattern recognition system to operate on accurately. The main objectives of pre-processing [3] are: binarization, noise reduction, skeletonization, boundary extraction, stroke width compensation [10], truncation of redundant portion of image and resizing to a specific size. Image binarization consists of conversion of a gray scale

978-0-7695-3267-7/08 $25.00 © 2008 IEEE DOI 10.1109/ICETET.2008.230

1196

Authorized licensed use limited to: San Jose State University. Downloaded on February 22, 2009 at 00:57 from IEEE Xplore. Restrictions apply.

image into a binary image. Noise reduction is performed using morphological operations like dilation, erosion etc. Skeletonization of the image gives an approximate single-pixel skeleton, which helps in the further stages of feature extraction and classification. The outermost boundary of the image is extracted to further obtain the boundary related attributes such as chain codes and number of loops. Stroke width compensation is performed to repair the character strokes, to fill small holes and to reduce uneven nature of the characters. The white portion surrounding the image can create noise in the feature extraction process and also increases the size of image unnecessarily. Truncation is performed to remove this white portion. In the end, the image is resized to a predefined size: 64pixel x 64pixel in this case

Structural features are based on topological and geometrical properties of the character, such as aspect ratio, loops, strokes and their directions etc. In this project, the boundary of the image is obtained and chain code is calculated for it. Then the number of ones, twos till number of eights is calculated. This is a good attribute for discernibility between different characters. Also the number of loops and perimeter of the image is obtained

Figure. 2. Zoning

Figure 3. Crossings

3. Unsupervised Neural Network Approach
In a neural network, if the target output is not known; the training method adopted is unsupervised learning. The network may modify the weight so that the most similar input vector is assigned to the same output unit. It is also referred to as self-organization, because it self organizes data presented to the network and detects their emergent collective properties. Advantages of unsupervised training are that classification is closer to human thinking and training does not change with small inconsistencies in data. It is also less lengthy compared to supervised neural networks. Paradigms of unsupervised learning are Hebbian learning and competitive learning rule. In this project, we use the latter. Winner-take-all algorithm is used here for competitive learning and is applied to the Kohonen Self-organizing network. The neural network units update their weights by forming a new weight vector that is a linear combination of the old weight vector and the current input vector. The unit whose weight vector is closest to the input vector is allowed to learn. An excel sheet with rows representing characters and columns representing attributes is used as input to the training algorithm. It is as shown in Fig. 4. The first column belongs to the decision attribute while remaining columns (30) denote the condition attributes. The decision attribute gives the outcome based on the values of the condition attributes, which are the inputs to the neural network. The data set in this project consists of printed alpha-numeric characters in ten fonts with 5 repetitions creating a data set of 1300 characters.

Figure. 1. Image pre-processing

2.2 Feature Extraction
In feature extraction stage, each character is represented as a feature vector, which becomes its identity. The major goal of feature extraction is to extract a set of features, which maximizes the recognition rate with the least amount of elements. The feature extraction process used in this project consists of two types of features: statistical and structural [2, 3, 7]. The major statistical features used are: zoning, crossings, pixel density, Euler number and compactness. In zoning, the 64 x 64 character image is divided into 16 x 16 pixel parts and pixel density of each part is calculated individually. This helps in obtaining local characteristics rather than global characteristics and is an important attribute for pattern recognition. Crossings count the number of transitions from background to foreground pixels along vertical and horizontal lines through the character image. For eg, In Fig. 3. , there are 6 vertical crossings (white to black and black to white) and 4 horizontal crossings in both the upper and lower part. Pixel Density is calculated over the whole 64 x 64 image. Euler number of an image is a scalar whose value is the total number of objects in the image minus the total number of holes in those objects. Euler number is also calculated for each image.

1197

Authorized licensed use limited to: San Jose State University. Downloaded on February 22, 2009 at 00:57 from IEEE Xplore. Restrictions apply.

Figure 4. Data set containing image attributes used for training

4. Rough-Neuro Hybrid Approach
Use of rough sets results into dimensionality reduction and optimized classification with removal of redundant attributes. Also, neural network is the most generalized tool for pattern recognition and has capability of working in noisy conditions also. This paper proposes a new Rough-Neuro Hybrid Approach in the pre-processing stage of pattern recognition. This reduces the convergence time, which was higher for the Kohonen Algorithm based training. Reducts and Cores are extracted from the set of given attributes. In this process, a set of equivalence classes which are indiscernible using the set of given attributes are identified. Only those attributes are kept which preserve the indiscernibility relation and the redundant ones are removed, as they do not affect the classification. A reduct is thus, a reduced set of attributes, which classifies the data set with the same efficiency as that of the original attribute set. Reducts ease the process of making predictions and decision making which in turn gives improved classification with reduced dimensionality of feature space [5, 6].

which is subset of A consists of the set of attributes that can be used to discern between objects x, y which are elements of U: “MA(x, y) consists of all those a which belongs to A and discerns between x and y.”[5,6]. After finding discernibility matrix, overall relative weight of each attribute is calculated by adding its relative weights of individual’s pairs of objects as shown in table 1.0. This becomes our parameter to choose the reduced set of attributes. Core is the set of all those attributes, which are essential for classification between two classes, and there is no alternative for those attributes. The third step thus includes finding such core attributes and also finding finally the reducts. Core can be found from the discernibility matrix itself. Any entry where each attribute has weight 0 except a single attribute, which has weight 1. Union of core and attributes from relative weight is taken. Top 45%-50% percent attributes are taken as reducts, which is then combined with core to form the final reducts. And then this set is given to the neural networks for decisionmaking.

4.1 Steps for finding reducts
The flowchart of algorithm for extracting reducts is as shown in figure 5. In first step the discernibility matrix is calculated for the input information. Whereas the information is technically defined as “information system I in terms of a pair (U, A), where U is a nonempty finite set of objects and A is a non-empty finite set of attributes.”[5,6] While the discernibility matrix is defined as an information system I define a matrix MA called a discernibility matrix. Each entry MA(x, y)

Figure 5 Steps for finding reducts For better understanding the example shown in Table 2.0 can be seen. A close look of this pattern recognition data reveals that the conditional attribute PixDen (zone1) is redundant.

1198

Authorized licensed use limited to: San Jose State University. Downloaded on February 22, 2009 at 00:57 from IEEE Xplore. Restrictions apply.

Thus only Euler Number and Avg PixDen are needed to take a decision. These reduced attributes are called reducts Table 1: Relative contribution of various condition attributes.

First Impression, 2006, PEARSON Education, pages 348497 [3] Hongsheng Su, Qunzhan Li, “Fuzzy Neural Classifier for Fault Diagnosis of Transformer Based on Rough Sets Theory”, IEEE, CS, 2223 to 2227 [4] Zdzislaw Pawlak, “ROUGH SETS- Theoretical Aspects of Reasoning about data”, 1991, Kluwer Academic Publishers, pages 1-43 [5] Hongsheng Su, Qunzhan Li Fuzzy “Neural Classifier for Fault Diagnosis of Transformer Based on Rough Sets Theory”, IEEE, CS, 2223 to 2227 [6] Andrew Kusiak “Rough Set Theory: A Data Mining Tool for Semiconductor Manufacturing”, IEEE transactions on electronics packaging manufacturing, vol. 24, no. 1, January 2001,Pages 44-50 [7] Giorgos Vamvakas , “Optical Character Recognition for Handwritten Characters”, National Center for Scientific Research “Demokritos” Athens - Greece , Institute of Informatics and Telecommunications and Computational Intelligence Laboratory (CIL) [8] Seethalakshmi R. , Sreeranjani T.R. , Balachandar T, Abnikant Singh, Markandey Singh, Ritwaj Ratan, Sarvesh Kumar, “Optical Character Recognition for printed Tamil text using Unicode”, Journal of Zhejiang University SCIENCE [9] Noor Ahmed Shaikh, Dr. Zubair A. Shaikh, “A Generalized Thinning Algorithm for Cursive and NonCursive Language Scripts” [10] Jianming Hu, Donggang Yu and Hong Yan, “Algorithm for stroke width compensation of handwritten characters”, Electronics Letters Online No19961501 [11] Chichang Jou, Tai- Yuan Hsiao, Hung-Chang Lee, “Handwritten Numeral Recognition based on Reduced features extraction and Fuzzy Membership function” [12] Jerzy W. Grzymala-Busse, “Introduction to Rough Set Theory and Applications”

Table 2.0: Training data with condition and decision attributes. PixDen (zone 1) is the local pixel density of the first zone obtained in zoning of image. Avg PixDen is the normalized pixel density of the entire image

5. Results
The Pure Neural approach, used for benchmarking, gave an efficiency of 55%. The method proposed above was used for finding reducts which reduced the dimensionality of the attribute set. The Kohonen network was trained again with this reduced set. Efficiency of 53.33% was obtained using Rough-Neuro Hybrid approach. The slight reduction in efficiency is compensated by the resulting removal in redundancy, decrease in number of epochs required for convergence and reduction in hardware complexity. Thus RoughNeuro hybrid approach proves to be better for pattern recognition as compared to pure neural approach

6. References
[1] S. N. Sivanandam S. Sumathi S. N. Deepa, “Introduction to Neural Networks using Matlab 6.0” first edition, 2006, Tata MCGraw Hill, pages 531-536 [2] Rafael C. Gonzalez, Richard E. Woods, Steven L. Eddiins, “Digital Image Processing using MATLAB” ,

1199

Authorized licensed use limited to: San Jose State University. Downloaded on February 22, 2009 at 00:57 from IEEE Xplore. Restrictions apply.