nach oben

Soft Computing

Erschienen in:

01.05.2012 | Focus

A K-nearest neighbours method based on imprecise probabilities

verfasst von: Sebastien Destercke

Erschienen in: Soft Computing | Ausgabe 5/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

K-nearest neighbours algorithms are among the most popular existing classification methods, due to their simplicity and good performances. Over the years, several extensions of the initial method have been proposed. In this paper, we propose a K-nearest neighbours approach that uses the theory of imprecise probabilities, and more specifically lower previsions. We show that the proposed approach has several assets: it can handle uncertain data in a very generic way, and decision rules developed within this theory allow us to deal with conflicting information between neighbours or with the absence of close neighbour to the instance to classify. We show that results of the basic k-NN and weighted k-NN methods can be retrieved by the proposed approach. We end with some experiments on the classical data sets.

Vorheriger Artikel Filtering with clouds

Nächster Artikel Extending information processing in a Fuzzy Random Forest ensemble

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

In the figure, each point of the simplex represents a probability distribution in barycentric coordinates, and the probability mass of an element is proportional to the distance between a point and the edge opposite to this element. See (Quaeghebeur and Cooman 2008) for details about the simplex representation.

Amores J, Sebe N, Radeva P (2006) Boosting the distance estimation: application to the k-nearest neighbor classifier. Pattern Recognit Lett 27:201–209CrossRef

Asuncion A, Newman D (2007) UCI machine learning repository http://www.ics.uci.edu/∼mlearn/MLRepository.html

Bedford T, Cooke R (2001) Probabilistic risk analysis. Foundations and Methods. Cambridge University Press, UKMATH

Berger JO (1994) An overview of robust Bayesian analysis. Test 3:5–124 (with discussion)MathSciNetMATHCrossRef

Bernard JM (2008) An introduction to the imprecise dirichlet model. Int J Approx Reason 39:123–150MathSciNetCrossRef

Chen YS, Hung YP, Yen TF, Fuh CS (2007) Fast and versatile algorithm for nearest neighbor search based on a lower bound tree. Pattern Recognit 40:360–375MATHCrossRef

Chow C (1970) On optimum recognition error and reject tradeoff. IEEE Trans Inf Theory 16:21–27CrossRef

Corani G, Zaffalon M (2009) Lazy naive credal classifier. In: KDD Workshop on Knowledge Discovery from Uncertain Data, pp 30–37

Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE Trans Inf Theory 13:21–27MATHCrossRef

de Campos L, Huete J, Moral S (1994) Probability intervals: a tool for uncertain reasoning. I. J Uncertain Fuzziness Knowl Based Syst 2:167–196MATHCrossRef

Denoeux T (1995) A k-nearest neighbor classification rule based on dempster-shafer theory. IEEE Trans Syst Man Cybern 25:804–813CrossRef

Destercke S (2010a) A decision rule for imprecise probabilities based on pair-wise comparison of expectation bounds. In: Combining Soft Computing and Statistical Methods in Data Analysis, Springer, Berlin, pp 189–197

Destercke S (2010b) A k-nearest neighbours method based on lower previsions. In: IPMU, pp 129–138

Dubois D, Prade H (1988) Possibility theory: an approach to computerized processing of uncertainty. Plenum Press, New YorkMATH

Dubuisson B, Masson M (1993) A statistical decision rule with incomplete knowledge about classes. Pattern Recognit 26:155–165CrossRef

Dudani S (1976) The distance-weighted k-nearest neighbor rule. IEEE Trans Syst Man Cybern 6:325–327

Finetti B (1974) Theory of probability, vol 1-2. Wiley, NY (translation of 1970 book)

Fix E, Hodges J (1951) Discriminatory analysis, nonparametric discrimination: consistency properties. Technical Report 4, USAF School of Aviation Medicine

Gilboa I, Schmeidler D (1989) Maxmin expected utility with non-unique prior. J Math Econ 18:141–153MathSciNetMATHCrossRef

Hastie T, Tibshirani R (1996) Discriminant adaptive nearest neighbor classification. IEEE Trans Pattern Anal Mach Intell 18:607–616CrossRef

Hsieh CH, Liu YJ (2000) Fast search algorithms for vector quantization of images using multiple triangle inequalities and wavelet transform. IEEE Trans Image Process 9:321–328MathSciNetMATHCrossRef

Hüllermeier E (2007) Case-based approximate reasoning. Theory and decision library, vol 44. Springer, Berlin

Jaffray JY, Jeleva M (2007) Information processing under imprecise risk with the Hurwicz criterion. In: Proceedings of the fifth Int. Symp. on Imprecise Probabilities and Their Applications

Keller J, Gray M, Givens J (1985) A fuzzy k-nn neighbor algorithm. IEEE Trans Syst Man Cybern 15:580–585

Miranda E (2008) A survey of the theory of coherent lower previsions. Int J of Approx Reason 48:628–658MathSciNetMATHCrossRef

Moral S, Sagrado J (1997) Aggregation of imprecise probabilities. In: BouchonMeunier B (eds) Aggregation and fusion of imperfect information. Physica-Verlag, Heidelberg, pp 162–188

Quaeghebeur E, Cooman GD (2008) Extreme lower probabilities. Fuzzy Sets Syst 159:2163–2175MATHCrossRef

Regoli G (1999) Inference under imprecise probability assessments. Soft Comput 3:181–186CrossRef

Shafer G (1976) A mathematical theory of evidence. Princeton University Press, New JerseyMATH

Smets P, Kennes R (1994) The transferable belief model. Artif Intell 66:191–234MathSciNetMATHCrossRef

Tomasi C, Manduchi R (1998) Stereo matching as a nearest-neighbor problem. IEEE Trans Pattern Anal Mach Intell 20:333–340CrossRef

Toyama J, Kudo M, Imai H (2010) Probably correct k-nearest neighbor search in high dimensions. Pattern Recognit 43:1361–1372MATHCrossRef

Troffaes M (2007) Decision making under uncertainty using imprecise probabilities. Int J Approx Reason 45:17–29MathSciNetMATHCrossRef

Tsai CF, Lin CY (2010) A triangle area based nearest neighbors approach to intrusion detection. Pattern Recognit 43:222–229MATHCrossRef

Tsoumakas G, Vlahavas IP (2007) Random-labelsets: an ensemble method for multilabel classification. In: ECML, pp 406–417

Utkin L (2005) Extensions of belief functions and possibility distributions by using the imprecise dirichlet model. Fuzzy Sets Syst 154:413–431MathSciNetMATHCrossRef

Walley P (1982) The elicitation and aggregation of beliefs, Technical Report. University of Warwick

Walley P (1991) Statistical reasoning with imprecise probabilities. Chapman and Hall, New YorkMATH

Wang J, Neskovic P, Cooper L (2007) Improving nearest neighbor rule with a simple adaptive distance measure. Pattern Recognit Lett 28:207–213CrossRef

Williams PM (2007) Notes on conditional previsions. Int J Approx Reason 44:366–383MATHCrossRef

Zadeh L (1975) The concept of a linguistic variable and its application to approximate reasoning-I. Inf Sci 8:199–249MathSciNetMATHCrossRef

Zaffalon M, Corani G, Maua D (2011) Utility-based accuracy measures to empirically evaluate credal classifiers. In: Coolen F, de Cooman G, Fetz T, Oberguggenberger M (eds) ISIPTA 11, pp 401–410

Zhou CY, Chen YQ (2006) Improving nearest neighbor classification with cam weighted distance. Pattern Recognit 39:635–645MATHCrossRef

Zouhal L, Denoeux T (1998) An evidence-theoretic k-nn rule with parameter optimization. IEEE Trans Syst Man Cybern 28:263–271CrossRef

Titel: A K-nearest neighbours method based on imprecise probabilities
verfasst von: Sebastien Destercke
Publikationsdatum: 01.05.2012
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 5/2012
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-011-0773-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 5/2012

Towards interval-based non-additive deconvolution in signal processing

A cooperative coevolutionary approach dealing with the skull–face overlay uncertainty in forensic identification by craniofacial superimposition

Partially supervised Independent Factor Analysis using soft labels elicited from multiple experts: application to railway track circuit diagnosis

Extending information processing in a Fuzzy Random Forest ensemble

A fuzzy regression model based on distances and random variables with crisp input and fuzzy output data: a case study in biomass production

Guest editorial: special issue on “knowledge extraction from low quality data: theoretical, methodological and practical issues”