Skip to main content
Top

2017 | OriginalPaper | Chapter

k-Nearest Neighbour Using Ensemble Clustering Based on Feature Selection Approach to Learning Relational Data

Authors : Rayner Alfred, Kung Ke Shin, Mohd Shamrie Sainin, Chin Kim On, Paulraj Murugesa Pandiyan, Ag Asri Ag Ibrahim

Published in: Advances in Information and Communication Technology

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Due to the growing amount of data generated and stored in relational databases, relational learning has attracted the interest of researchers in recent years. Many approaches have been developed in order to learn relational data. One of the approaches used to learn relational data is Dynamic Aggregation of Relational Attributes (DARA). The DARA algorithm is designed to summarize relational data with one-to-many relations. However, DARA suffers a major drawback when the cardinalities of attributes are very high because the size of the vector space representation depends on the number of unique values that exist for all attributes in the dataset. A feature selection process can be introduced to overcome this problem. These selected features can be further optimized to achieve a good classification result. Several clustering runs can be performed for different values of k to yield an ensemble of clustering results. This paper proposes a two-layered genetic algorithm-based feature selection in order to improve the classification performance of learning relational database using a k-NN ensemble classifier. The proposed method involves the task of omitting less relevant features but retaining the diversity of the classifiers so as to improve the performance of the k-NN ensemble. The result shows that the proposed k-NN ensemble is able to improve the performance of traditional k-NN classifiers.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Fayyad, U., Shapiro, G.P., Smyth, P.: From data mining to knowledge discovery in data mining. AI Mag. 17(3), 37–54 (1996) Fayyad, U., Shapiro, G.P., Smyth, P.: From data mining to knowledge discovery in data mining. AI Mag. 17(3), 37–54 (1996)
2.
go back to reference Hansen, L.K., Salamon, P.: Neural network ensembles. IEEE Trans. Pattern Anal. Mach. Intell. 12, 993–1001 (1990)CrossRef Hansen, L.K., Salamon, P.: Neural network ensembles. IEEE Trans. Pattern Anal. Mach. Intell. 12, 993–1001 (1990)CrossRef
3.
go back to reference Ali, K.M., Pazzani, M.J.: Error reduction through learning multiple descriptions. Mach. Learn. 24, 173–202 (1996) Ali, K.M., Pazzani, M.J.: Error reduction through learning multiple descriptions. Mach. Learn. 24, 173–202 (1996)
5.
go back to reference Freund, Y., Schapire, R.: Experiments with a new boosting algorithm. In: Thirteenth International Conference on Machine Learning (1996) Freund, Y., Schapire, R.: Experiments with a new boosting algorithm. In: Thirteenth International Conference on Machine Learning (1996)
6.
go back to reference Quinlan, J.R.: Bagging, boosting and C4.5. In: Fourteenth National Conference on Artificial Intelligence (1996) Quinlan, J.R.: Bagging, boosting and C4.5. In: Fourteenth National Conference on Artificial Intelligence (1996)
7.
go back to reference Cover, T.M., Hart, P.E.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967)CrossRefMATH Cover, T.M., Hart, P.E.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967)CrossRefMATH
8.
go back to reference Holland, J.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975). MIT Press, Cambridge (1992) Holland, J.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975). MIT Press, Cambridge (1992)
9.
go back to reference Fraser, A.S.: Simulation of genetic systems by automatic digital computers I. Introduction/Aust. J. Biol. Sci. 10, 484–491 (1957) Fraser, A.S.: Simulation of genetic systems by automatic digital computers I. Introduction/Aust. J. Biol. Sci. 10, 484–491 (1957)
10.
go back to reference Bay, S.D.: Nearest neighbour classification from multiple feature subsets. Intell. Data Anal. 3(3), 191–209 (1999)CrossRef Bay, S.D.: Nearest neighbour classification from multiple feature subsets. Intell. Data Anal. 3(3), 191–209 (1999)CrossRef
11.
go back to reference Getoor, L.: Multi-relational data mining using probalilistic relational models: research summary. In: Proceedings of the First Workshop in Multi-Relational Data Mining (2001) Getoor, L.: Multi-relational data mining using probalilistic relational models: research summary. In: Proceedings of the First Workshop in Multi-Relational Data Mining (2001)
12.
go back to reference Xia, P.Y., Ding, X.Q., Jiang, B.N.: A GA-based feature selection and ensemble learning for high-dimensional datasets. IEEE Int. Conf. Mach. Learn. Cybern. 3, 7–12 (2009) Xia, P.Y., Ding, X.Q., Jiang, B.N.: A GA-based feature selection and ensemble learning for high-dimensional datasets. IEEE Int. Conf. Mach. Learn. Cybern. 3, 7–12 (2009)
13.
go back to reference Canuto, A.M.P., Nascimento, D.S.C.: A genetic-based approach to features selection for ensembles using a hybrid and adaptive fitness function. In: IEEE International Joint Conference on Neural Networks (IJCNN), pp. 1–8 (2012) Canuto, A.M.P., Nascimento, D.S.C.: A genetic-based approach to features selection for ensembles using a hybrid and adaptive fitness function. In: IEEE International Joint Conference on Neural Networks (IJCNN), pp. 1–8 (2012)
14.
go back to reference Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. JMLR 3, 1157–1182 (2003)MATH Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. JMLR 3, 1157–1182 (2003)MATH
15.
go back to reference Saeys, V., Inza, I., Larrañaga, P.: A review of feature selection techniques in bioinformatics. Bioinformatics 23(19), 2507–2517 (2007)CrossRef Saeys, V., Inza, I., Larrañaga, P.: A review of feature selection techniques in bioinformatics. Bioinformatics 23(19), 2507–2517 (2007)CrossRef
16.
go back to reference Ghanem, A.S., Venkatesh, S., West, G.: Learning in imbalanced relational data. In: 2008 19th International Conference on Pattern Recognition, ICPR 2008, pp. 1–4 (2008) Ghanem, A.S., Venkatesh, S., West, G.: Learning in imbalanced relational data. In: 2008 19th International Conference on Pattern Recognition, ICPR 2008, pp. 1–4 (2008)
17.
go back to reference Macskassy, S., Provost, F.: A simple relational classifier. In: Proceedings of 2nd Workshop on Multi-Relational Data Mining (MRDM) (2003) Macskassy, S., Provost, F.: A simple relational classifier. In: Proceedings of 2nd Workshop on Multi-Relational Data Mining (MRDM) (2003)
18.
go back to reference Chen, J.X., Li, P.B.: Random forest for relational classification with application to terrorist profiling. In: IEEE International Conference on Granular Computing, GRC 2009, pp. 630–633 (2009) Chen, J.X., Li, P.B.: Random forest for relational classification with application to terrorist profiling. In: IEEE International Conference on Granular Computing, GRC 2009, pp. 630–633 (2009)
19.
go back to reference Alfred, R.: Optomizing feature construction process for dynamic aggregation of relational attributes. J. Comput. Sci. 5(11), 864 (2009)CrossRef Alfred, R.: Optomizing feature construction process for dynamic aggregation of relational attributes. J. Comput. Sci. 5(11), 864 (2009)CrossRef
20.
go back to reference Kheau, C.S., Alfred, R., Keng, L.H.: Dimensionality reduction in data summarization approach to learning relational data. In: Selamat, A., Nguyen, N.T., Haron, H. (eds.) ACIIDS 2013. LNCS (LNAI), vol. 7802, pp. 166–175. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36546-1_18 CrossRef Kheau, C.S., Alfred, R., Keng, L.H.: Dimensionality reduction in data summarization approach to learning relational data. In: Selamat, A., Nguyen, N.T., Haron, H. (eds.) ACIIDS 2013. LNCS (LNAI), vol. 7802, pp. 166–175. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-36546-1_​18 CrossRef
21.
go back to reference Kuncheva, L., Jain, L.: Designing classifier fusion systems by genetic algorithms. IEEE Trans. Evol. Comput. 4(4), 327–336 (2000)CrossRef Kuncheva, L., Jain, L.: Designing classifier fusion systems by genetic algorithms. IEEE Trans. Evol. Comput. 4(4), 327–336 (2000)CrossRef
22.
go back to reference Alfred, R.: The study of dynamic aggregation of relational attributes on relational data mining. In: Alhajj, R., Gao, H., Li, J., Li, X., Zaïane, O.R. (eds.) ADMA 2007. LNCS (LNAI), vol. 4632, pp. 214–226. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73871-8_21 CrossRef Alfred, R.: The study of dynamic aggregation of relational attributes on relational data mining. In: Alhajj, R., Gao, H., Li, J., Li, X., Zaïane, O.R. (eds.) ADMA 2007. LNCS (LNAI), vol. 4632, pp. 214–226. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-73871-8_​21 CrossRef
23.
go back to reference Alfred, R., Kazakov, D.: A clustering approach to generalized pattern identification based on multi-instanced objects withDARA. In: Local Proceedings of ADBIS, Varna, pp. 38–49 (2007) Alfred, R., Kazakov, D.: A clustering approach to generalized pattern identification based on multi-instanced objects withDARA. In: Local Proceedings of ADBIS, Varna, pp. 38–49 (2007)
24.
go back to reference Alfred, R., Kazakov, D.: Pattern-based transformation approach to relational domain learning using DARA. In: Crone, S.F., Lessmann, S., Stahlbock, R. (eds.) The Proceedings of the 2006 International Conference on Data Mining (DMIN 2006), 25–29 June, pp. 296–302. CSREA Press, Las Vegas (2006). ISBN: 1-60132-004-3 Alfred, R., Kazakov, D.: Pattern-based transformation approach to relational domain learning using DARA. In: Crone, S.F., Lessmann, S., Stahlbock, R. (eds.) The Proceedings of the 2006 International Conference on Data Mining (DMIN 2006), 25–29 June, pp. 296–302. CSREA Press, Las Vegas (2006). ISBN: 1-60132-004-3
25.
go back to reference Alfred, R.: Feature transformation: a genetic-based feature construction method for data summarization. Comput. Intell. 26(3), 337–357 (2010)MathSciNetCrossRefMATH Alfred, R.: Feature transformation: a genetic-based feature construction method for data summarization. Comput. Intell. 26(3), 337–357 (2010)MathSciNetCrossRefMATH
26.
go back to reference Alfred, R., Kazakov, D.: Discretization numbers for multiple-instances problem in relational database. In: Ioannidis, Y., Novikov, B., Rachev, B. (eds.) ADBIS 2007. LNCS, vol. 4690, pp. 55–65. Springer, Heidelberg (2007). doi:10.1007/978-3-540-75185-4_6 CrossRef Alfred, R., Kazakov, D.: Discretization numbers for multiple-instances problem in relational database. In: Ioannidis, Y., Novikov, B., Rachev, B. (eds.) ADBIS 2007. LNCS, vol. 4690, pp. 55–65. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-75185-4_​6 CrossRef
27.
go back to reference Srinivasan, A., Muggleton, S.H., Sternberg, M.J.E., King, R.D.: Theories for mutagenicity: a study in first-order and feature-based induction. Artif. Intell. 85, 277–299 (1996)CrossRef Srinivasan, A., Muggleton, S.H., Sternberg, M.J.E., King, R.D.: Theories for mutagenicity: a study in first-order and feature-based induction. Artif. Intell. 85, 277–299 (1996)CrossRef
Metadata
Title
k-Nearest Neighbour Using Ensemble Clustering Based on Feature Selection Approach to Learning Relational Data
Authors
Rayner Alfred
Kung Ke Shin
Mohd Shamrie Sainin
Chin Kim On
Paulraj Murugesa Pandiyan
Ag Asri Ag Ibrahim
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-49073-1_35

Premium Partner