Çizge Kuramı ( Graph Theory ) ve Video Öneri Sistemleri

Geçen hafta Çizge Kuramını basitçe açıklamış, Çizge Kuramında önem arz eden bazı kavramlara değinmiştik.

Hatırlarsanız, yazının başında da, sizi biraz heyecanlandırmak için, Çizge Kuramının nerelerde kullanıldığından bahsetmiştim.

Bu hafta Çizge Kuramının kullanım alanlarından birini incelemek istiyorum. Çizge Kuramının kullanımını inceleyecek, işe yararlılığı üzerine tartışacak ve Çizge Kuramındaki kavramların nasıl bir fayda kattığını açıklayacağım.

Hemen örneğimize geçelim ve incelemeye başlayalım.

Bir “öneri sistemi”yani recommendation system yapmaya çalıştığınızı düşünelim ( youtube’daki sizin için önerilen videolar mekanizması gibi ) . Bu projeyi yapmanın geleneksel yolu, veri tabanlarına sorgular yaptırmaktır. Yani bir nevi veri tabanlarına sorular sormak. Bu sorgulara örnek olarak şu verilebilir:

Eğer: izlenen video eğlence kategorisinde ise

Video öner: eğlence kategorisinden

Farklı bir yol ise, Graph Theory’yi kullanmak.

Videoları ve kullanıcıları düğüm şeklinde temsil ederek, kullanıcıların içeriğe olan ilgisini de kenar şeklinde temsil ederek platformunuzu bir Çizgeye dökebilir, bu yolla öneri sisteminizi daha hızlı ve verimli kılabilirsiniz.

Üstteki cümleden hiçbir şey anlamadıysanız, bir önceki yazımı okumanızı öneririm. O yazıda düğüm ve kenar kavramlarını açıklıyorum.

Gelin basit bir video öneri sistemi Çizgesine beraber bakalım:

Bir video izleme sitesinin Çizgesi. Kırmızılar kullanıcılar, maviler videolar. Siyah bağlar alakalı videoları, turuncu bağlar izlenmeyi, mor bağlarsa arkadaşlığı temsil ediyor

Üstteki resimde 4 kullanıcısı, 12 videosu olan bir video platformunun çizgesini görüyorsunuz. Hangi kullanıcıların hangi videoları izlediği, hangi videoların birbiri ile alakalı olduğu, hangi kullanıcıların birbiri ile arkadaş olduğu işaretlenmiş.

Hadi video önerelim.

Osman’a bir video önermemiz gerektiğini düşünelim. Eğer sorgu yöntemlerini kullansaydık, Osman’ın sevdiği video tiplerini bulmamız, daha sonra o videolara benzeyen videoları bulmamız gerekirdi. Ama şimdi yapmamız gereken şey daha basit. Osman’ın etrafında “yürüyeceğiz” sadece.

Osman 6 ve 7. videoyu zaten izlemiş. Osman’a önereceğimiz ilk videolar 5 ve 8. videolar olurdu. Bunun sebebi, Osman’ın zaten izlediği videolara en yakın videoların 5 ve 8 olması.

Eğer kenarlarımız yani bağlarımız ağırlıklandırılmış olsaydı, Osman’a önce 5'i mi 8'i mi önermemiz gerektiğini hesaplayabilirdik. Ağırlıklandırmak demek, kenarlara puanlar vermek demek. Örneğin Osman 6. videoyu izlediğinde “beğen” butonuna basmışsa ama 7. videoyu izlediğinde hiçbir şey yapmamışsa, 6. videoya olan bağı daha “ağır” olurdu.

Ağır bağlar, genelde daha kalın olarak çizilir. Bu resimde Osman’ın, 6'ıncı videoya fazlaca bir ilgisi olduğu temsil ediliyor.

Öyle bir durumda Osman’a ilk önermemiz gereken video 5. video idi. Çünkü Osman 6. videoyu 7. videodan daha çok seviyor olurdu. 6'ıncı videoya yakın olan video da 5'incisi.

Şimdiki durumda Çizgemizde ağırlıklar yok. O yüzden Osman’a aynı anda hem 5. hem 8. videoyu önerdiğiimizi düşünelim. Osman daha sonra 8. videoyu izlesin.

Bu durumda Osman ve 8. video arasında yeni bir turuncu bağ oluşacaktı. Dikkat edin, 7 ve 8. videonun arasındaki bağ turuncu olmayacaktı, Osman’dan, 8. videoya yepyeni bir turuncu bağ oluşacaktı.

Eğer Çizgemiz ağırlıklandırılmış olsaydı, Osman ile 8. videonun arasındaki bağı, Osman ile 7. videonun arasındaki bağdan daha hafif yapabilirdik. Bunu yapmak istememizin sebebi, Osman’ın 8. videoyu kendi arayıp bularak değil, bir öneriye tıklayarak izlemiş olması. Yani Osman’ın 7. videoyu 8. videodan daha çok sevdiğini tahmin etmemiz.

Ancak Çizgemizde ağırlıklar yok. öyleyse:

‘7.video’< — — ->‘Osman’

‘8.video’< — — ->‘Osman’

Üstteki iki bağ, aynı önemi taşıyor.

Peki Arzu’ya hangi videoları önerebiliriz? Arzu hiçbir video izlememiş. Yani videoların birbirine benzerliğinden ona yapabileceğimiz bir öneri yok. Ama direk Arzu’nun etrafında “yürüyerek” Arzu’ya önermemiz gereken videoyu bulabiliriz.

Arzunun etrafında yürümeye başladığımızda Taha ile arkadaş olduğunu görüyoruz. Yürümeye devam ettiğimizde, Taha 3. videoyu izlediği için, Arzu’ya 3. videoyu önerebileceğimiz ortaya çıkıyor.

Öneri sistemi kısmına biraz mola vererek, Çizge Kuramının sitemizi yönetmekte sağlayacağı başka bir kolaylıktan da bahsetmek istiyorum.

Video Platformumuzun Bağ Yoğunluğu

Bu video platformunda, herkesin her videoyu izleyip izlemediğini, herkesin birbiri ile arkadaş olup olmadığını nasıl anlayabiliriz? Elbette “yoğunluk” hesabı yaparak. Yoğunluk hesabı yapmayı hatırlayalım:

Ş: Şu anda var olan tüm bağların sayısı

M: Mümkün olan tüm bağların sayısı

Yoğunluk = Ş / M

Videoların ne kadar izlendiğini bulmamız için, turuncu bağları saymamız gerekiyor. Daha sonra turuncu bağların yoğunluğunu bulacağız.

Bu yoğunluk işlemi bize platforma giren her kullanıcının, platformu ne kadar hararetli bir şekilde kullandığını gösterecek.

Demek istediğim şu. Platformumuza giren her kullanıcı, bir video izleyip daha sonra platformu kullanmayı bırakabilir. Öte yandan, başka bir senaryoda platforma giren her kullanıcı platformda kalıp, bir sürü video izlemeye devam edebilir.

Çoğu site için ikinci senaryo daha çekicidir, çünkü ikinci senaryoda kullanıcılar platformu daha çok kullanmış olur. Yani çoğu site, Çizgesinin yoğun olmasını bir başarı sayacaktır. İşte yoğunluk ölçümünü bunun için kullanmamız mümkün, platformun ne kadar başarılı bir şekilde kullanıcıları kendine bağladığını ölçmek için.

Hesabımıza başlayalım öyleyse:

Çizgemizde toplam 4 turuncu bağ var.

Mümkün olan tüm turuncu bağ sayısı ise 48. Bu sayısı şöyle hesapladım:

4kullanıcı * 12video = maksimum 48 izlenme

Öyleyse yoğunluğumuz:

4/48= 1/12 = 0.083

Yoğunluk değerimiz en fazla 1 olabilirdi. Öyle bir durumda tüm kullanıcılar, tüm videoları izlemiş olurdu. Yani platformumuz tükenmiş olurdu, aynı videoları tekrar izlemek dışında kimsenin izleyecek bir videosu kalmazdı.

Şimdiki tükenmişliğimiz ise %8 civarında.

Tükenmişliğimiz %30'u geçtiği zaman platforma yeni bir video yüklemek konusundaki çalışmalara başlamamız gerekebilir. Çünkü kullanıcılarımızın platformda hep yeni videolara rastlamasını isteriz. Ama tükenmişlik değeri yani turuncu bağ yoğunluğu %8 iken, yeni bir video yüklememize muhtemelen gerek yok. Çünkü zaten herkesin izleyebileceği daha bir sürü video var. Bunu da açıkladığımıza göre, kısa bir özetle yazımızı bitirelim.

Özet

Bu yazıda bir video platormu örneği üstünden Çizge Kuramının faydalarını inceledik.

İncelediğimiz kavramlar ve video platformundaki karşılıkları şunlardı:

Düğümler: Platformdaki kişiler, videolar

Kenarlar (Bağlar): Bir kişinin bir videoyu izlemesi (turuncu), iki videonun alakası (siyah), iki kişinin arkadaşlığı (mor).

Yürüme (Walk): Bir kişiden başlayarak, ve bağların üstünde yürüyerek, o kişiye önerebileceğimiz videolara ulaşmak.

Ağırlık: Bir kişinin bir videoyu ne kadar sevdiğini ölçmek.

Yoğunluk: Platformdaki insanların her birinin tüm videoları izlemeye ne kadar yakın olduğunu ölçmek. Yani platformumuzun her kullanıcıyı ne kadar kendine bağladığını görmek. Aynı zamanda, platforma ne zaman yeni bir video yüklememiz gerektiğini kestirmek. (Çünkü her kullanıcı platformda yeni videolar görmek ister, aynı videoları tekrar tekrar izlemek istemez.)

Bu haftalık bu kadar, kendinize iyi bakın!

ml engineer @primer ai | sharing thoughts on computers and other geeky stuff

ml engineer @primer ai | sharing thoughts on computers and other geeky stuff