Result: Survey of Nearest Neighbor Condensing Techniques

La règle du plus proche voisin identifie la catégorie d'un élément inconnu en fonction des catégories de ses voisins les plus proches connus. Cette technique est efficace dans de nombreux domaines tels que la reconnaissance d'événements, la catégorisation de texte et la reconnaissance d'objets. Son principal avantage est sa simplicité, mais son principal inconvénient est sa complexité informatique pour les grands ensembles d'entraînement. Cet inconvénient a été traité par la communauté des chercheurs comme le problème de la sélection des prototypes. Pour tenter de résoudre ce problème, plusieurs techniques présentées comme des techniques de condensation ont été proposées. Les algorithmes de condensation tentent de déterminer un ensemble de prototypes significativement réduit en gardant la performance de la règle 1-NN sur cet ensemble proche de celle atteinte sur l'ensemble d'entraînement complet. Dans cet article, nous présentons une enquête sur certaines techniques de condensation KNN qui sont CNN, RNN, FCNN, Drop1-5, DEL, IKNN, TRKNN et CBP. Toutes ces techniques peuvent améliorer l'efficacité du temps de calcul. Mais ces algorithmes ne parviennent pas à prouver la minimalité de leur ensemble résultant. Pour cela, une possibilité est de les hybrider avec d'autres algorithmes, appelés heuristiques ou métaheuristiques modernes, qui, eux-mêmes, peuvent améliorer la solution. Les métaheuristiques qui ont fait leurs preuves dans la sélection des attributs sont principalement les algorithmes génétiques et la recherche tabu. Nous allons également faire la lumière dans cet article sur certaines techniques récentes axées sur ce modèle.
La regla del vecino más cercano identifica la categoría de un elemento desconocido de acuerdo con las categorías de sus vecinos más cercanos conocidos. Esta técnica es eficiente en muchos campos como el reconocimiento de eventos, la categorización de texto y el reconocimiento de objetos. Su principal ventaja es su simplicidad, pero su principal inconveniente es su complejidad informática para grandes conjuntos de entrenamiento. Este inconveniente fue tratado por la comunidad de investigadores como el problema de la selección de prototipos. Tratando de resolver este problema se propusieron varias técnicas presentadas como técnicas de condensación. Los algoritmos de condensación intentan determinar un conjunto de prototipos significativamente reducido manteniendo el rendimiento de la regla 1-NN en este conjunto cerca del alcanzado en el conjunto de entrenamiento completo. En este documento presentamos una encuesta de algunas técnicas de condensación de KNN que son CNN, RNN, FCNN, Drop1-5, DEL, IKNN, TRKNN y CBP. Todas estas técnicas pueden mejorar la eficiencia en el tiempo de cálculo. Pero estos algoritmos no logran demostrar la minimalidad de su conjunto resultante. Para ello, una posibilidad es hibridarlos con otros algoritmos, llamados heurística moderna o metaheurística, que, por sí mismos, pueden mejorar la solución. Las metaheurísticas que han demostrado resultados en la selección de atributos son principalmente algoritmos genéticos y búsqueda tabú. También arrojaremos luz en este documento sobre algunas técnicas recientes que se centran en esta plantilla.
The nearest neighbor rule identifies the category of an unknown element according to its known nearest neighbors' categories. This technique is efficient in many fields as event recognition, text categorization and object recognition. Its prime advantage is its simplicity, but its main inconvenience is its computing complexity for large training sets. This drawback was dealt by the researchers' community as the problem of prototype selection. Trying to solve this problem several techniques presented as condensing techniques were proposed. Condensing algorithms try to determine a significantly reduced set of prototypes keeping the performance of the 1-NN rule on this set close to the one reached on the complete training set. In this paper we present a survey of some condensing KNN techniques which are CNN, RNN, FCNN, Drop1-5, DEL, IKNN, TRKNN and CBP. All these techniques can improve the efficiency in computation time. But these algorithms fail to prove the minimality of their resulting set. For this, one possibility is to hybridize them with other algorithms, called modern heuristics or metaheuristics, which, themselves, can improve the solution. The metaheuristics that have proven results in the selection of attributes are principally genetic algorithms and tabu search. We will also shed light in this paper on some recent techniques focusing on this template.
تحدد قاعدة الجار الأقرب فئة عنصر غير معروف وفقًا لفئات جيرانه الأقرب المعروفين. هذه التقنية فعالة في العديد من المجالات مثل التعرف على الأحداث وتصنيف النص والتعرف على الكائنات. ميزتها الرئيسية هي بساطتها، ولكن إزعاجها الرئيسي هو تعقيد الحوسبة لمجموعات التدريب الكبيرة. تم التعامل مع هذا العيب من قبل مجتمع الباحثين كمشكلة اختيار النموذج الأولي. في محاولة لحل هذه المشكلة، تم اقتراح العديد من التقنيات المقدمة كتقنيات تكثيف. تحاول خوارزميات التكثيف تحديد مجموعة مخفضة بشكل كبير من النماذج الأوّلية التي تحافظ على أداء قاعدة 1 - NN في هذه المجموعة قريبة من تلك التي تم الوصول إليها في مجموعة التدريب الكاملة. في هذه الورقة، نقدم مسحًا لبعض تقنيات التكثيف KNN وهي CNN و RNN و FCNN و Drop1 -5 و DEL و IKNN و TRKNN و CBP. كل هذه التقنيات يمكن أن تحسن الكفاءة في وقت الحساب. لكن هذه الخوارزميات تفشل في إثبات الحد الأدنى من مجموعتها الناتجة. لهذا، فإن أحد الاحتمالات هو تهجينها مع خوارزميات أخرى، تسمى الاستدلال الحديث أو metaheuristics، والتي، في حد ذاتها، يمكن أن تحسن الحل. إن الدراسات الاستدلالية التي أثبتت نتائجها في اختيار السمات هي في الأساس خوارزميات وراثية وبحث عن التابو. سنسلط الضوء أيضًا في هذه الورقة على بعض التقنيات الحديثة التي تركز على هذا النموذج.