anlak.com

Temel Bileşenler Analizi (PCA) çıkarımı

, Sunday, 5 February 2012
Sevgili dostum İsmail Arı şuradaki yazısında PCA hakkında kapsamlı ve güzel bilgiler veriyor. İsmail yazısında kovaryans matrisini diyagonal hale getirecek dönüşüm üzerinden çıkarımı yapıyor. Ben problemi farklı bir açıdan ele alıp, PCA yapmak için neden özvektörleri bulmamız gerektiğini varyansın maksimizasyonu ile göstereceğim. Elimden geldiğince basit anlatmaya çalışacağım, mümkün olduğunca az süslü hatta Yunan alfabesinden olmayan harfler kullanacağım, buna rağmen anlamak için konu hakkında birazcık altyapıya sahip olmanız gerekebilir. Yine de yazının uzunluğu gözünüzü korkutmasın, yeterince anlaşılır olmak adına bilerek fazla açıklama yaptığımdan uzadı, içeriğin yeterince basit olduğunu umuyorum.

İlkin problemimizi tanımlayalım. Elimizde bir kısım veri var ve öyle bir dönüşüm yapmak istiyoruz ki, bu dönüşümün sonunda elimizdeki örnekler birbirinden mümkün olduğunca ayrılmış, dağılmış, saçılmış olsun.

Problemi matematiksel olarak ifade edelim. Elimizde $n$ adet veri örneği olsun. Her sütun bir veri örneğine denk gelecek şekilde $X$ matrisini oluşturalım. Dönüşüm matrisimiz $w$ olsun. Bu dönüşümün ($w^TX$) sonunda saçılımın en fazla olmasını istiyoruz.


İlkin tek boyuta indirecek dönüşümü $w_1$ ele alalım. Bu dönüşümün sonucunda elde ettiğimiz yeni değişkenlere de $z_1$ diyelim. Öyle bir dönüşüm arıyoruz ki, $z_1$ için saçılımın en fazla olmasını istiyoruz:
$$
\arg\max\limits_{w_1} \; \text{Var}(z_1)
$$
Başka bir deyişle:
$$
\arg\max\limits_{w_1} \; \text{Var}(w_1^TX)
$$
$$
\newcommand{\E}{\mathop{\mathbb E}}
\renewcommand{\< }{\left<}
\renewcommand{\>}{\right>}
\newcommand{\Var}{\text{Var}}
\newcommand{\CovSym}{\mathbf{\Sigma}}
$$
Varyansın tanımını hatırlayalım, $\< \cdot\>$ beklenen değer operatörü olmak üzere:
$$
\Var(x) = \< (x-\mu)^2\>
$$
İzdüşümden sonraki varyansı yerine koyalım, ortalamanın da aynı dönüşüme tabi olduğuna dikkatinizi çekerim:
$$
\begin{align*}
\Var(w^TX) &= \< (w^TX-w^T\mu)^2\> \\
&= \< w^T(X-\mu)(X-\mu)^Tw \> \\
&= w^T \< (X-\mu)(X-\mu)^T \> w\\
\end{align*}
$$
$\< (X-\mu)(X-\mu)^T\>$ ifadesinin kovaryansa, $\CovSym$, karşılık geldiğini biliyoruz (bilmiyorsak bakıp öğreniyoruz), o halde:
$$
\Var(w^TX) = w^T\CovSym w
$$
Bu bulduğumuzu yerine koyduğumuz zaman, esas problemimiz şu hale gelmiş oldu:
$$
\arg\max\limits_{w_1} \; w_1^T\CovSym w_1
$$
Sözle ifade edecek olursak, $w_1$ yerine hangi değeri koyarsak $w_1^T\CovSym w_1$ ifadesi en büyük değerine ulaşır?

İfademize bakacak olursak, $w_1$ yerine sonsuz büyük/uzun bir değer koyarsak $w_1^T\CovSym w_1$ ifadesi en yüksek değerini alır. Bu sonuç pek işimize yaramıyor maalesef, elimize hiçbir şey geçmemiş oldu, o yüzden işimize yarayabilecek bir sonuç üretecek şekilde yeniden ifade etmeye çalışalım problemimizi.

$w_1$in uzunluğu değil, yönü önemli bizim için, çünkü onun üzerine sadece izdüşüm alıyoruz. 1 birim ya da 99 birim uzunluğunda olması bizi ilgilendirmiyor. O yüzden problemimizin düzgün bir çözümü olması için $w_1$in uzunluğunu 1 alalım:
$$
||w_1|| = 1
$$
Bu kısıtımızı esas ifademize yedirmemiz lazım. Bunu yapmanın yolu Lagrange Çarpanı yöntemini kullanmak, şuradaki yazımda bundan bahsetmiştim.
$$
\arg\max\limits_{w_1} \; w_1^T\CovSym w_1 - \lambda (||w_1|| - 1)
$$
Başka bir deyişle:
$$
\arg\max\limits_{w_1} \; w_1^T\CovSym w_1 - \lambda (w_1^T w_1 - 1)
$$
İfadeyi en yüksek ya da düşük yapan $w_1$ değerini bulmak için, $w_1$e göre türev alıp sıfıra eşitleriz (kalkülüsten hatırlarsınız):
$$
(\CovSym + \CovSym ^T) w_1 - 2 \lambda w_1 = 0
$$
Kovaryans matrislerinin özelliğinden $\CovSym = \CovSym^T$ olduğunu biliyoruz. Bunu kullanıp ifadeyi düzenlersek:
$$
\begin{align*}
2 \CovSym w_1 - 2 \lambda w_1 = 0\\
\CovSym w_1 = \lambda w_1
\end{align*}
$$
elde ederiz ki, bu da tam olarak $w_1$in $\CovSym$'in özvektörü olduğunun ifadesidir. Kabaca hatırlatayım, $A$ bir matris, $\lambda$ bir skaler ve $x$ bir vektör ve $x$, $Ax = \lambda x$ sağlıyor ise $x$'e $A$'nın özvektörü denir.

Peki acaba $w_1$, $\CovSym$'in hangi özvektörü? Bunu bulmak için bulduğumuz sonucu esas problemimiz olan $w_1^T \CovSym w_1$ ifadesinde yerine koyalım, neticede bu ifadeyi maksimize etmeye çalışıyorduk en başından:
$$
\begin{align*}
w_1^T \CovSym w_1 &= w_1^T \lambda w_1 \\
&= \lambda w_1^T w_1\\
&= \lambda ||w_1||\\
&= \lambda
\end{align*}
$$
buluruz. $||w_1||$ uzunluğunun 1'e eşit olduğu bilgisini kullandık son adımda. Elde ettiğimiz sonuç ne demek? Şu demek: Esas ifademizi maksimize etmek istiyorsak $\lambda$'yı maksimize etmeliyiz. $\lambda$'nın da en büyük olması, en büyük özdeğer olduğu durumdur.

Sonuç olarak, ilk izdüşüm alacağımız yön, verinin kovaryans matrisinin en büyük özdeğerine denk düşen özvektör olarak seçilmelidir.

İkinci ve daha sonraki izdüşümler de benzer bir yolla bulunursa bunların da sırasıyla ikinci ve daha sonraki özdeğerlere denk düşen özvektörler olması gerektiği bulunabilir. Çıkarımı yaparken dikkat edilmesi gereken nokta, bir sonraki izdüşümleri yaparken bir önceki bulduğunuz yöne dik olmaları gerektiğidir, yani $w_1 \cdot w_2 = 0$. Bunu da Lagrange çarpanı olarak ifadenize eklemeniz gerekir.

Dikkat edilmesi gereken önemli noktalardan biri de, tüm bunları yaparken, verinizin ortalamasının $0$ olması gerekir, PCA öncesinde ve sonrasında bu gerekli dönüşümü yapmanız lazım.

No comments:

Post a comment