Abstract-Nearest granne klassificerare som använder alla träningsprover för klassificering kräver stort minne och kräver stora online test beräkning. För att minska minneskraven och beräkningskostnaden har många algoritmer utvecklats som utför närmaste grannklassificering med endast ett litet antal representativa prover som erhållits från träningssetet. Vi kallar klassificeringen modell underliggande alla dessa algoritmer som Voronoi nätverk (Vnets), eftersom dessa algoritmer diskretize funktionen utrymme i Voronoi regioner och tilldela proverna i varje region till en klass. I detta dokument analyserar vi generaliseringskapaciteten hos dessa nätverk genom att begränsa generaliseringsfelet. Den klass av problem som kan "effektivt" lösas av Vnets kännetecknas av i vilken utsträckning uppsättningen punkter på beslutsgränserna fyller funktionsutrymmet, vilket kvantifierar hur effektivt ett problem kan lösas med hjälp av Vnets. Vi visar att Vnets asymptotiskt konvergerar till Bayes klassificerare med godtyckligt hög sannolikhet förutsatt att antalet representativa prover växer långsammare än kvadratroten av antalet träningsprover och även ger optimal tillväxthastighet av antalet representativa prover. Vi gör om analysen för beslut träd (DT) klassificerare och jämföra dem med Vnets. Dilemmat mellan partiskhet och variation och dimensionalitetens förbannelse med avseende på Vnet och DT diskuteras också.
I REF visas det att Vnet asymptotiskt konvergerar till Bayes klassificering med godtycklig hög sannolikhet förutsatt att antalet representativa prover växer långsammare än kvadratroten av antalet träningsprover.
Voronoi networks and their probability of misclassification
{'venue': 'IEEE transactions on neural networks', 'journal': 'IEEE transactions on neural networks', 'mag_field_of_study': ['Computer Science', 'Medicine']}