Problem eliminacji nieprzystających obiektów w zadaniu rozpoznawania wzorca

Widok

Metadane zasobu

Tytuł	Problem eliminacji nieprzystających obiektów w zadaniu rozpoznawania wzorca Wariant tytułu: Issue of elimination of unsiutable objects in pattern recognition task
Osoby	Autorzy: Marcin Jerzy Luckner Partner: Instytut Badań Systemowych PAN w Warszawie
Opis	Problem rozpoznawania wzorca jest dobrze znanym i zbadanym zagadnieniem. Może być reprezentowany poprzez funkcję klasyfikującą, która przypisuje obiektom etykiety klas. Jednakże, jeśli obiekt nie należy do żadnej z rozpoznawanych klas funkcja klasyfikująca przypisze go błędnie do jednej z nich. W praktyce taka sytuacja zachodzi często w przypadku zakłóconych danych wejściowych. Rozwiązaniem jest zastosowanie mechanizmu eliminującego nieprzystające wzorce. Problem odrzucania zostanie zaprezentowany na przykładzie rzeczywistego zadania, jakim jest rozpoznawanie cyfr na mapach geodezyjnych. Mapy zawierają zarówno grafikę jak i tekst. Część graficzną tworzą linie I specjalistyczne symbole. Część tekstowa składa się z symboli alfanumerycznych. Ograniczenie rozpoznawania do cyfr nie eliminuje praktycznego aspektu zagadnienia, gdyż taki klasyfikator może być użyty przy budowie trójwymiarowego modelu terenu lub przy identyfikacji działek. W przypadku rozpoznawania cyfr można wyszczególnić trzy główne źródła błędów, pozostające w zróżnicowanej iteracji z poszczególnymi, rozpoznawalnymi klasami. Kleksy i fragmenty grafiki będą błędnie przypisywane do różnych klas. Dla innych symboli da się wykazać preferencję klasyfikacji. Na przykład litera 'g' będzie częściej mylona z cyfrą '9' niż '1'. Wreszcie, sklejone cyfry będą częściowo prezentowały cechy dwóch cyfr i można się spodziewać, że ich rozkład będzie się głównie zawierał w dwóch klasach. Ta różnorodność wymaga zastosowania różnych metod odrzucania. Do rozwiązania zadania klasyfikacji zastosowano maszyny wektorów podpierających - supported vector machines (SVM). Klasyfikator ten rozdziela klasy hiperpłaszczyzną i może być zastosowany tylko do podziałów binarnych. By obejść to ograniczenie zaproponowano algorytmy tworzące hierarchiczne struktury klasyfikatorów. Algorytm tworzący drzewo grupujące znajduje, w każdym kroku, dwie najbliższe klasy. Następnie tworzy rozdzielający je klasyfikator. Klasy te są usuwane, a w ich miejsce powstaje pojedyncza klasa grupująca ich reprezentantów. Postępowanie to stosuje się do momentu, gdy uzyskamy pojedynczą klasę zawierającą wszystkie elementy. W wyniku uzyskujemy drzewo binarne łączące klasyfikatory SVM. W procesie klasyfikacji decyzje klasyfikatorów SVM, prowadzą do następnych klasyfikatorów, aby w wyniku przypisać obiekt do jednej z klas. Opisana struktura zapewnia 95 procentową skuteczność dla omawianego zadania. Jest to wynik podobny do uzyskanego przez szeroko stosowane metody takie jak sieci neuronowe. Jednak zaproponowana metoda umożliwia implementację różnorodnych metod odrzucania. Pierwsza metoda odrzucania ma na celu eliminację pomyłek między klasami. Dla każdego klasyfikatora definiowany jest próg. Jeżeli poparcie dla decyzji klasyfikatora jest niższe od zadanego progu element jest odrzucany. Druga metoda odrzuca przypadki, które zajmują odrębny rejon przestrzeni danych niż rozpoznawane klasy poprzez określenie dopuszczalnego zakresu cech dla poszczególnych klas. Ostatnia metoda definiuje alternatywną funkcję klasyfikującą w dodatkową klasę-śmietnik. Wszystkie elementy przypisane do tej klasy są odrzucane. Testy dowiodły, że tylko metoda budująca alternatywną funkcję klasyfikującą pozwala osiągnąć dobre rezultaty. Skuteczność odrzucania (procent poprawnie odrzuconych przypadków, nienależących do rozpoznawanych klas) przekracza 96 procent, a skuteczność rozpoznawania (procent poprawnie rozpoznanych elementów należących do rozpoznawanych klas) osiąga 85 procent. Łączna skuteczność, po uwzględnieniu liczności zbiorów, wynosi 93 procent. Pozostałe metody nie mogą być używane samodzielnie, jednakże dodanie zbioru ograniczającego zakres cech do alternatywnej funkcji klasyfikującej powoduje eliminację znacznej liczby przypadków i ogranicza koszt obliczeniowy. (Polski) Opis w innym języku: The pattern recognition task is a commonly know issue with many theoretical and practical solutions. It can be described by a classification function that assigns a label of recognized class to an object. However, if this object does not belong to any of know classes, the classification function will assign it incorrectly to one of classes. In practice such situation is very common, especially when input data is corrupted. For that reason a rejection mechanism is postulated to eliminate unsuitable elements. The problem of rejection will be presented on a real task, which is recognition of digits from geodetic maps. The maps contain both graphic and text. The graphic part of a map consists of lines and special symbols. The text part contains alphanumerical symbols. The recognition tasks focused on digits only are very limited, but can be used in practice to define a three-dimension model of terrain or to identify a parcel. In case of the digit recognition task, possible sources of mistakes can be divided into three groups of various interaction level with recognized classes. Blots and fragmented graphic elements will be evenly distributed among classes by a classification function. Other map symbols (including letters) will prefer a single class. For example the letter 'g' will be confused with the figure '9' rather than with the figure '1'. Finally, touching digits (two symbols analyzed as one) will be distributed mainly between two classes. Diversity of error sources results in different rejection methods. Now it is necessary to describe the classification function used in the discussed task. An implementation based on the supported vector machines (SVM). This classifier splits given data space between two classes with a hyperplane. In case of two-dimensional data space, split is defined by a line. However, this method can only be used to separate two classes. In a digit recognition task ten classes occur. To solve this problem in the dissertation a hierarchical structure of SVM classifiers has been proposed. In the algorithm creating grouping tree, in each step, two nearest classes are founded. For those classes a SVM classifier is created. Next, classes are replaced by class collecting all their cases. This sequence is repeated until there is only one class left. As a result, binary tree, that connects SVM classifiers, is given. In a recognition process an SVM decision leads to the next classifier. Finally, the object is assigned to a class by the decision of the last classifier. The described structure gives 95 percent accuracy for the discussed task. This result is similar to results of commonly used methods such as neural networks. However, this technique allows implementation of various rejection methods. The first rejection method eliminates cases mistaken between classes. For each SVM classifier a threshold can be defined. If the confidence level for a classifier decision is lower than the threshold, the element is rejected. (Angielski)
Słowa kluczowe	"rozpoznawanie wzorca"@pl, "odrzucanie"@pl, "zespoły klasyfikatorów"@pl, "pattern recognition"@en, "klasyfikacja"@pl
Klasyfikacja	Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / informatyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie
Charakterystyka	Miejsce powstania: Warszawa Czas powstania: 2009 Liczba stron: 112 Promotor: Władysław Homenda Język zasobu: Polski Lokalizacja: Warszawa
Licencja	CC BY-SA 4.0
Informacje techniczne	Deponujący: Anna Wasilewska Data udostępnienia: 16-10-2018
Kolekcje	Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Cytowanie

Skopiowano

Marcin Jerzy Luckner. Problem eliminacji nieprzystających obiektów w zadaniu rozpoznawania wzorca. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Podobne zasoby

Wielorozdzielczościowa klasyfikacja za pomocą kombinacji estymatorów jądrowych

Mateusz Kobos, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / informatyka (2011)

Problem rozpoznawania wzorców dla zagadnień słabo zrównoważonych

Wojciech Lesiński, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / informatyka (2011)

Metody subgradientowe dla zadań klasyfikacji w sieciach neuronowych (RB-1994-83)

Krzysztof Kiwiel, Piotr Kowalski, Bożena Łopuch, artykuł, rozdział, Instytut Badań Systemowych PAN w Warszawie, Dziedzina nauk ścisłych i przyrodniczych / matematyka (2018)

Klasyfikacja bayesowska informacji niedokładnej typu przedziałowego

Piotr Kowalski, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / informatyka (2011)

Algorytm podejmowania decyzji z wykorzystaniem identyfikacji dwustopniowej

Krzysztof Brzostowski, praca dyplomowa, Politechnika Wrocławska, dziedzina nauk technicznych / informatyka (2011)

Selekcja na bieżąco z danych masowych przy użyciu zespołu klasyfikatorów

Marcin Gromisz, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / informatyka (2011)

Zobacz więcej