Analys av grannskapskomponenter

Grannskapskomponentanalys är en övervakad inlärningsmetod för att klassificera multivariat data i distinkta klasser enligt ett givet avståndsmått över data. Funktionellt tjänar den samma syften som K-närmaste grannar-algoritmen och använder direkt ett relaterat koncept som kallas stokastiska närmaste grannar .

Definition

Analys av grannskapskomponenter syftar till att "lära" ett avståndsmått genom att hitta en linjär transformation av indata så att den genomsnittliga klassificeringsprestandan (LOO) maximeras i det transformerade utrymmet. Nyckelinsikten till algoritmen är att en matris $A$ som motsvarar transformationen kan hittas genom att definiera en differentierbar objektivfunktion för ${\displaystyle A} ,$ följt av användning av en iterativ lösare såsom konjugerad gradientnedstigning . En av fördelarna med denna algoritm är att antalet klasser $k$ kan bestämmas som en funktion av ${\displaystyle A} ,$ upp till en skalärkonstant. Denna användning av algoritmen tar därför upp frågan om modellval .

Förklaring

För att definiera $A$ definierar vi en objektivfunktion som beskriver klassificeringsnoggrannheten i det transformerade rummet och försöker bestämma $A^{*}$ så att denna objektivfunktion maximeras.

$A^{*}={\mbox{argmax}}_{A}f(A)$

Leave-one-out (LOO) klassificering

Överväg att förutsäga klassetiketten för en enskild datapunkt genom konsensus av dess $k$ -närmaste grannar med ett givet avståndsmått. Detta är känt som " lea-one-out" -klassificering. Emellertid kan uppsättningen av närmaste grannar $C_{i}$ vara ganska annorlunda efter att alla punkter har passerats genom en linjär transformation. Specifikt kan uppsättningen av grannar för en punkt genomgå diskreta förändringar som svar på jämna förändringar i elementen i $A$ , vilket innebär att varje objektiv funktion $f(\cdot )$ baserat på grannar till en punkt kommer att vara styckvis-konstanta , och därför inte differentierbara .

Lösning

Vi kan lösa denna svårighet genom att använda ett tillvägagångssätt inspirerat av stokastisk gradientnedstigning . Istället för att betrakta $k$ -närmaste grannar vid varje transformerad punkt i LOO-klassificeringen, kommer vi att betrakta hela den transformerade datamängden som stokastiska närmaste grannar . Vi definierar dessa med hjälp av en softmax-funktion av det kvadratiska euklidiska avståndet mellan en given LOO-klassificeringspunkt och varje annan punkt i det transformerade rummet:

$p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2} }}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if}}j\neq i\ \0,&{\mbox{if}}j=i\end{cases}}$

Sannolikheten för att korrekt klassificera datapunkt $i$ är sannolikheten att klassificera punkterna för var och en av dess grannar med samma klass $C_{i}$ :

$p_{i}=\sum _{j\in C_{i}}p_{ij}\quad$ där $p_{ij}$ är sannolikheten att klassificera granne $j$ till punkt $i$ .

Definiera målfunktionen med hjälp av LOO-klassificering, denna gång med hela datamängden som stokastiska närmaste grannar:

$f(A)=\summa _{i}\summa _{j\in C_{i}}p_{ij} =\summa _{i}p_{i}$

Observera att under stokastiska närmaste grannar är konsensusklassen för en enda punkt $i$ det förväntade värdet av en punkts klass i gränsen för ett oändligt antal sampel som dras från fördelningen över dess grannar ${\ displaystyle j\in C_{i}}$ dvs: $P(Class(X_{i})= Klass(X_{j}))=p_{ij}$ . Således är den förutsagda klassen en affin kombination av klasserna för varannan punkt, viktad av softmax-funktionen för varje $j\in C_{j}$ där $C_{j}$ är nu hela den transformerade datamängden.

Detta val av objektivfunktion är att föredra eftersom det är differentierbart med avseende på $A$ (beteckna $x_{ij}=x_{i}-x_{j}$ ) :

${\frac {\partial f }{\partial A}}=-2A\summa _{i}\summa _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\summa _{k}p_{ik}x_{ik}x_{ik}^{T}\right)$

$=2A\sum _{i}\vänster (p_{i}\summa _{k}p_{ik}x_{ik}x_{ik}^{T}-\summa _{j\in C_{i}}p_{ij}x_{ij}x_{ ij}^{T}\right)$

Att erhålla en gradient för $A$ innebär att den kan hittas med en iterativ lösare som konjugerad gradientnedstigning . Observera att i praktiken utvärderas de flesta av de innersta termerna av gradienten till obetydliga bidrag på grund av det snabbt minskande bidraget från avlägsna punkter från den intressanta punkten. Detta innebär att den inre summan av gradienten kan trunkeras, vilket resulterar i rimliga beräkningstider även för stora datamängder.

Alternativ formulering

"Maximera $f(\cdot )$ är ekvivalent med att minimera $L_{1}$ -avståndet mellan den förutsagda klassfördelningen och den sanna klassfördelningen (dvs: där $p_{i}$ inducerad av $A$ är alla lika med 1). Ett naturligt alternativ är KL-divergensen, som inducerar följande objektiva funktion och gradient:" (Goldberger 2005)

$g(A)=\sum _{i}\log \left(\sum _ {j\in C_{i}}p_{ij}\right)=\summa _{i}\log(p_{i})$

${\frac {\partial g}{\partial A}}=2A\summa _{i}\left(\summa _{k}p_{ik}x_{ik}x_{ik}^{T}-{\ frac {\summa _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\summa _{j\in C_{i}}p_{ij}}} \höger)$

I praktiken tenderar optimering av $A$ med denna funktion att ge liknande prestandaresultat som med originalet.

Historia och bakgrund

Grannskapskomponentanalys utvecklades av Jacob Goldberger, Sam Roweis, Ruslan Salakhudinov och Geoff Hinton vid University of Torontos avdelning för datavetenskap 2004.

Se även

J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Analys av grannskapskomponenter . Framsteg inom neurala informationsbehandlingssystem. 17, 513–520, 2005.

externa länkar

programvara

MLPACK -biblioteket innehåller en C++ -implementering
nca ( C++ )
scikit-learns implementering av " NeighborhoodComponentsAnalysis " ( Python )