Classification Technique that associates samples to classes previously known. May be Crisp or Fuzzy Supervised Classification MLP trained Adriano Joaquim de O Cruz ©2002 NCE/UFRJ [email protected] Non supervised K-NN e fuzzy K-NN not trained *@2001 Adriano Cruz *NCE e IM - UFRJ K-NN and Fuzzy K-NN Classification Methods Classes identified by patterns Classifies by the k nearest neighbours Previous knowledge about the problem classes It is not restricted to a specific distribution of the samples *@2001 Adriano Cruz *NCE e IM - UFRJ Classification Classification 3 Crisp K-NN Classification 2 Crisp K-NN Crisp K-NN Supervised clustering method (Classification method). Classes are defined before hand. Classes are characterized by sets of elements. The number of elements may differ among classes. The main idea is to associate the sample to the class containing more neighbours. Class 1 *NCE e IM - UFRJ Classification 5 Crisp K-NN Class 3 w5 w9 w14 w8 Class 4 w11 w 12 s w7 w6 Class 5 3 nearest neighbours, and sample s is closest to pattern w6 on class 5. *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 6 Crisp K-NN Consider W={w ={w1, w2, ..., wt} a set of t labelled data. Each object w is defined by l characteristics i wi=(w =(wi1, wi2, ..., wil). Input of y unclassified elements. k the number of closest neighbours of y. E the set of k nearest neighbours (NN). *@2001 Adriano Cruz w4 w13 w10 *@2001 Adriano Cruz Class 2 w2 w3 w1 *NCE e IM - UFRJ Classification 7 Let t be the number of elements that identify the classes. Let c be the number of classes. Let W be the set that contain the t elements Each cluster is represented by a subset of elements from W. *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 8 Crisp K-NN algorithm Crisp K-NN algorithm cont. set set k {Calculating the NN} for t for i = 1 to = 1 to Calculate distance from y to xi if if i<=k then add then add xi to E else else if if xi is closer to y than any previous NN then delete the farthest neighbour then delete the farthest neighbour and include xi in the set E *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 9 Determine the majority class represented in the set E and include y in this class. if there is a draw, if there is a draw, then calculate the sum of distances from then calculate the sum of distances from y to all neighbours in each class in the draw if the sums are different if the sums are different then add then add xi to class with smallest sum else add else add xi to class where last minimum was found *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 10 Fuzzy K-NN Classification Fuzzy K-NN The basis of the algorithm is to assign membership as a function of the object’s distance from its K-nearest neighbours and the memberships in the possible classes. J. Keller, M. Gray, J. Givens. A Fuzzy KNearest Neighbor Algorithm. IEEE Transactions on Systems, Man and Cybernectics, vol smc-15, no 4, July August 1985 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 12 Fuzzy K-NN Fuzzy K-NN Classe 2 Classe 1 w2 w4 w 13 w1 w10 w11 Classe 4 *@2001 Adriano Cruz w8 w7 w12 w14 Consider W={w ={w1, w2, ..., wt} a set of t labelled data. Each object wi is defined by l characteristics wi=(w =(wi1, wi2, ..., wil). Input of y unclassified elements. k the number of closest neighbours of y. E the set of k nearest neighbours (NN). i(y) is the membership of y in the class i ij is the membership in the ith ith class of the jth vector of the labelled set (labelled wj in class i) . w6 Classe 5 *NCE e IM - UFRJ Classification 13 Fuzzy K-NN *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 14 Fuzzy K-NN algorithm Let t be the number of elements that identify the classes. Let c be the number of classes. Let W be the set that contain the t elements Each cluster is represented by a subset of elements from W . *@2001 Adriano Cruz w5 w9 w3 Classe 3 *NCE e IM - UFRJ Classification 15 set set k {Calculating the NN} for t for i = 1 to = 1 to Calculate distance from y to xi if if i<=k then add then add xi to E else else if if xi is closer to y than any previous NN then delete the farthest neighbour then delete the farthest neighbour and include xi in the set E *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 16 Computing ij(y) Fuzzy K-NN algorithm Calculate i(y) using for c // number of classes for i = 1 to = 1 to k ∑ μij μi ( y )= j=1 k ∑ j=1 *@2001 Adriano Cruz ( ( 1 ∥y −x j∥2/( m−1 ) 1 ∥y−x j∥2/( m−1) *NCE e IM - UFRJ ) ) Classification 17 ij(y) can be assigned class membership in several ways. They can be given complete membership in their known class and non membership in all other. Assign membership based on distance from their class mean. Assign membership based on the distance from labelled samples of their own class and those from other classes. *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 18 ICC-KNN System Classification ICC-KNN System Non-Parametric Statistical Pattern Recognition System Associates FCM, fuzzy KNN and ICC Evaluates data disposed on several class formats *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 20 ICC-KNN System ICC-KNN First Module Divided in two modules First module (training) chooses the best patterns to use with K-NN chooses the best fuzzy constant and best number of neighbours (K) Finds structure on data sample Divided into two phases • FCM – Applied to each class using many numbers of categories • ICC – Finds the best number of categories to represent each class uses fuzzy k-nn to classify *NCE e IM - UFRJ Classification 21 ICC-KNN First Phase Patterns for K-NN which are the centres of the chosen run of FCM Number of centres which are all the centres of the number of categories resulting after applying ICC to all FCM runs *NCE e IM - UFRJ *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 22 ICC-KNN Second Phase Results of applying FCM and ICC *@2001 Adriano Cruz First phase of training Finds the best patterns for fuzzy K-NN Second module (classification) *@2001 Adriano Cruz Classification Module Classification 23 Second phase of training Evaluates the best fuzzy constant and the best number of neighbours so to achieve best performance on the K-NN tests several m and k values finds m and k for the maximum rate of crisp hits *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 24 ICC-KNN ICC-KNN block diagram Pattern Recognition Module Distributes each data to its class Classification Module Uses the chosen patterns, m and k to classify data Pattern Recognition Module U1cmin Class 1 FCM ICC w1 U1cmáx W, Uw UScmin Class s FCM ICC Fuzzy K-NN m k Fuzzy K-NN W Uw ws UScmáx Not classified Data *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 25 *@2001 Adriano Cruz ICC-KNN *NCE e IM - UFRJ Classification 26 ICC-KNN algorithm Let R={ R={r1,r2,...,rn} be the set of samples. Classification Module Each sample ri belongs to one of s known classes. First phase of training Let Uic be the inclusion matrix for the class i with c categories. Let Vic be the centre matrix for the class i with c categories. Let wi be equal to the best Vic of each class Step 1. Set m Step 2. Set cmin and cmáx Step 3. For each s known class Generate the set Rs with the points from R belonging to the class s For each category c in the interval [ cmin , cmáx] cmáx] Run FCM for c and the set Rs generating Usc and Vsc Calculate ICC for Rs e Usc End Define the patterns ws of class s as the matrix Vsc that maximizes ICC Let W be the set of sets of centres wi *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 27 Step 4. Generate the set W = {w1, ..., ws} *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 28 ICC-KNN algorithm Second phase of Training Step 5. Set mmin e mmáx Step 6. Set kmin e kmáx For each m from [mmin , mmáx] For each k from [kmin , kmáx] Run fuzzy K-NN for the patterns from the set W generating Umk Calculate the number of crisp hits for Umk ICC-KNN algorithm Pattern Recognition Module Step 9. Apply fuzzy K-NN using patterns form the set W and the chosen parameters m and k to the data to be classified. Step 7. Choose m and k that yields the best crips hit figures Step 8. if there is a draw If the k’s are different Choose the smaller k else Choose the smaller m *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 29 ICC-KNN results *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 30 ICC-NN results 2000 samples, 4 classes, 500 samples in each class Classes 1 and 4 – concave classes Classes 2 and 3 – convex classes, elliptic format *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 31 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 32 ICC-KNN results ICC-KNN results First phase of training Second phase of Training FCM applied to each class Running fuzzy K-NN Training data 80% 400 samples from each class c = 3..7 and m = 1,25 ICC applied to results Patterns from first phase Random patterns k = 3 a 7 neighbours m = {1,1; 1,25; 1,5; 2} Classes 1 and 4 4 categories Classes 2 and 3 3 categories *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 33 ICC-KNN results *NCE e IM - UFRJ *@2001 Adriano Cruz Classification 34 ICC-KNN results Dados de Treinamento Classes Conclusão:K-NN é mais estável em relação ao valor de m para os padrões da PFT *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 35 Padrões da PFT Padrões Aleatórios 1 2 3 4 1 2 3 4 1 388 10 0 2 213 66 0 121 2 14 379 0 7 19 380 0 1 3 0 0 376 24 3 0 324 73 4 0 1 2 397 4 46 1 349 Training data Lines classes Columns classification m = 1,5 e k = 3 96,25% m = 1,1 e k = 3 79,13% (random patterns) *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 36 ICC-KNN results ICC-KNN x Others Dados de Testes Classes Padrões da PFT Padrões Aleatórios 1 2 3 4 1 2 3 4 1 97 2 0 1 53 27 0 20 2 4 93 0 3 4 96 0 0 3 0 0 90 10 0 0 82 18 4 0 0 1 99 0 15 0 85 FCM, FKCN, GG e GK Fase de Treinamento (FTr) Dados de treinamento c = 4 e m = {1,1; 1,25; 1,5; 2} Associar as categorias às classes • Critério do somatório dos graus de inclusão o Cálculo do somatório dos graus de inclusão dos pontos de cada classe em cada categoria o Uma classe pode ser representada por mais de uma categoria Test data Lines classes Columns classification Pad. PFT – 94,75% Pad. Aleat – 79% *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 37 ICC-KNN x Others Fase de Teste ICC-KNN Classe representada por mais de 1 categoria Grau de inclusão = soma dos graus de inclusão dos pontos nas categorias que representam a classe *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 38 ICC-KNN x Others Dados de Teste Inicialização dos métodos com os centros da FTr Calcula o grau de inclusão dos pontos em cada categoria *NCE e IM - UFRJ *@2001 Adriano Cruz Classification 39 FCM FKCN GG GK 66% 66% 69% 84% 95,75% 83% 70,75% 70,75% 69% 89,5% 36,5s 23,11s 2,91s 2,59s 22,66s 18,14s 94,75% N T KNN A. 79% R GK para m = 2 84% FCM e FKCN 66% para m = 1,1 e m = 1,25 GG-FCM 69% para m = 1,1 e 1,25 GG Aleatório 57,75% para m = 1,1 e 25% para m = 1,5 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 40 GK GK GK Classes 1 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 41 2 3 4 1 77 6 0 17 2 6 94 0 0 3 0 0 97 3 4 0 0 32 68 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 42 KNN+Fuzzy C-Means algorithm Classification KNN+Fuzzy Cmeans System The idea is an two-layer clustering algorithm First an unsupervised tracking of cluster centres is made using K-NN rules The second layer involves one iteration of the fuzzy c-means to compute the membership degrees and the new fuzzy centres. Ref. N. Zahit et all, Fuzzy Sets and Systems 120 (2001) 239-247 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 44 First Layer (K-NN) KNN-1FCMA settings Let X={x ={x1,…,xn} be a set of n unlabelled objects. Let X={x ={x1,…,xn} be a set of n unlabelled objects. c is the number of clusters. The first layer consists of partitioning X into c cells using the fist part of K-NN. Each cell i is (1<=i (1<=i<=c <=c) represented as Ei (yi, K-NN of yi, Gi) Fix c the number of clusters. Choose m>1 (nebulisation factor). Set k = Integer(n Integer(n/c –1). Let I={1,2,…, n} be the set of all indexes of X. I={1,2,…,n Gi is the center of cell Ei and defined as Gi = *@2001 Adriano Cruz ∑ x k ∈Ei xk / k + 1 *NCE e IM - UFRJ Classification 45 KNN-1FCMA algorithm step 1 Calculate Calculate G0 for c for i = 1 to = 1 to Search in I for the index of the farthest object yi from Gi1 For j = 1 to n Calculate distance from yi to xj if j <= k then add then add xj to Ei else else if if xi is closer to y than any previous NN then delete the farthest neighbour then delete the farthest neighbour and include x in the set Ei Classification 47 *NCE e iIM - UFRJ *@2001 Adriano Cruz *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 46 KNN-1FCMA algorithm cont. Include yi in the set Ei . Calculate Gi. Delete yi index and the KNN indexes of yi from I. if if I then for each remaining object then for each remaining object x determine the minimum distance to any centre Gi of Ei. classify x to the nearest centre. update all centres. *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 48 KNN-1FCMA algorithm step2 Compute the matrix U according to c μik = Results KNN-1FCMA 2 −1 m−1 (∑ ( ) ) l=1 d ik d lk Calculate all fuzzy centres using n ∑ ( μie )m⋅x ej v ij= e=1 n ∑ ( μ ie )m e =1 *@2001 Adriano Cruz *NCE e IM - UFRJ Classification 49 Data Elem c FCMA KNN-1FCMA FCMA S1 20 2 0 0 11 S2 60 3 1 0 8 S3 80 4 2 0 10 S4 120 6 13 13 19 IRIS23 150 2 14 13 10 IRIS 100 3 16 17 12 *@2001 Adriano Cruz Misclassification rate Number of Iterations avg *NCE e IM - UFRJ Classification 50

Download
# Classification