Foursquare’de 65 milyondan fazla mekandan oluşan geniş bir koleksiyon var. Bu mekan bilgisi, kullanıcıların sevecekleri benzer mekanları keşfetmesi için kullandığımız ana ipuçlarından birisi. Benzer mekanlar sadece aşağıda gösterilen özellikleri iyileştirmekle kalmıyor aynı zamanda arama ve önerme algoritmalarımızın da altında çalışan skorlama bileşenini oluşturuyor.
Bir süredir benzer mekanlar ipuçları olmakla birlikte, yakın zamanda problemi baştan aşağı elden geçirdik. Bu gönderi, son mekan benzerliği güncellemesine nasıl yaklaştığımız hakkında genel bir bakış sağlayacaktır.
Orjinal mekan benzerliği job’ı, farklı Luigi konfigürasyonlarına sahip ham mapreducelar’ı kullanan scala sarıcılarımızı (wrapper) kullanan iki farklı hadoop job’ından oluşmaktaydı. Yeniden yazımdan sonra, bütün benzer mekan önerisi tek bir Luigi konfigürasyonu ile Scalding job’ına alınarak aynı zamanda kod okunurluğunu da artırılmış oldu. Ayrıca önceki Thrift yapısını yeniden organize ederek sonuç dosyası olan HFile‘ı da küçülterek optimize ettik. Bunun sayesinde benzer mekanların online alındığı anda kullanıcı tarafındaki servislerde oluşan sunucu yüklerini de hafifletmiş olduk.
Eşziyaret
Mekan benzerliğini hesaplama eşziyaretin kullanılmasının öncüsü olarak şu önermeyi ele alabiliriz, eğer çok kişi sıklıkla iki mekana gidiyorsa veya bu iki mekana gidilme sıklığı benzer ise bu iki mekanın birbirine benzer olduğu varsayılabilir. Örneğin Hayes Valley’deki Smitten Dondurmacısına gidenler aynı zamanda Mission taraflarındaki Humphry Slocombe dondurmacısına da gitmiş. İkisi de sezonsal lezzetler sunan benzer hipster dondurmacılarından. Eşziyaret çok değerli bir ipucu olabilir özellikle üzerinde çalışacak 10 milyar check-inimiz var ise.
Eşziyareti ölçekli olarak hesaplamanın da kendine has bazı zorlukları var. En genel olarak yapmak istediğimiz şey mekanlar arasındaki kosinüs benzerliğini hesaplamak. Her mekanı bir kullanıcı vektörü olarak modelliyoruz: Eğer n kullanıcımız var ise her mekan n uzunluğunda bir vektör oluyor. Eğer i. indeksteki kullanıcı o mekanı daha önceden ziyaret etmiş ise vektörün i. değeri 1 oluyor etmemişse 0. Basit olarak bütün kullanıcıların check-in verileri üzerinden bütün eşziyaret edilen mekanların kosinüs benzerliğini hesaplayabiliriz. Tabi böyle bir işlem geçmişi çok derin olan kullanıcılarda O(n²) olmasından dolayı kabul edilemeyecek çalışma zamanlarına yol açacak ve Hadoop sunucumuzun kalbini kıracaktır :(
Aşağıda hesaplamayı optimize etmek için ele aldığımız bazı maddeler var:
- Örnekleme: Twitter’daki elemanlar genel hatları burada verilen DISCO algoritması ile geldiler. Bu algoritma genel olarak final benzerlik ölçümlerini büyük oranda değiştirmeden eldeki veri setini akıllı bir şekilde örneklendirmeye yarıyor.
- Yansıtma (Matematiksel Küme Simetri Özelliği): Mekan A -> Mekan B eşziyaretini hesaplamak demek tersini ayrıca hesaplamaya ihtiyacınız yok demek. Eğer veriyi düzgünce sıralarsak, ihtiyaç olan hesaplama sayısını büyük oranda düşürebiliriz.
Eşziyaret tabi ki kusursuz değil. Buradaki problemlerden birisi havaalanları ve tren istasyonları gibi büyük küme mekanları içinde insanların bütün normalizasyon çabalarına rağmen gürültü oluşturması. Ayrıca yerellik problemleri de var örneğin şarküteri mağazası akşam yemeği mekanının yanında olabilir ve ortak bir çok müşterileri olabilir ama bu ortak ziyaretçiler onların benzer olduğun anlamına gelmez.
Kategori
Sıklıkla gittiğiniz bir restoran düşünün, onu tek bir kategoriye indirerek kategorilendirebilirsiniz. Örneğin benim favori barbekü restorantım basitçe “Barbekü Restoranı” olarak kategorilendirilebilir. Bir barbekü restoranı standart bir restoran olarak da değerlendirilebilir veya Amerikan restoranı olarak da. Foursquare’de her mekanın bir ana kategorisi var ancak başka alt kategorileri de olabilir. Ek olarak kategoriler ağaç hiyerarşisinde modellendi böylece her kategori başka bir kategorinin üst veya alt kategorisi olabilir. Önceden benzerliği sadece kategorileri ve üst kategorileri üzerinden hesaplıyorduk. Bir Dim Sum restoranı başka bir dim sum restoranı ile birebir eşleşecektir ancak en dip kategori noktasında örneğin Hong Kong restoranı kategorisi ile eşleşmeyecektir.
Naif bir inceleme olsa da kategorik benzerliği açıklamak için en iyi yöntem olmadığını kanıtlamak için yeterli. Örneğin Hot Pot restoranı ile Çin restoranı çok benzer ama modellenme yöntemlerinden dolayı aralarındaki benzerliği çıkarsamak oldukça zor. Hot Pot restoranının Çin Restoranına Filipin restoranından daha benzer olmasını istiyoruz.
Bu problemi kısmen gidermek için birazdan bahsedeceğimi problemi gidermek üzere maksimum benzerlik tahminini kullandık: X kategorisi ile etiketlenmiş en az bir başka kategorisi daha olan bir mekan verilsin, bu mekanın aynı zamanda kategori Y olarak etiketlenmesinin olasılığı nedir ? Kategori çiftlerinin birlikte bulunmalarına bakarsak, birebir kategori listesi karşılaştırmasına göre daha ayrıntılı ve rafine sonuç verecektir. Bu ölçüm yöntemi bir Hot Pot restoranının bir Çin Restoranına(hesaplanan benzerlik %27) bir Filipin Restoranından(hesaplanan benzerlik %0.0!) daha fazla benzediğine dair istenen çıktıyı verir. Bu noktada zaten büyük bir gelişme yapmış olduk.
Yüksek kategori benzerlik benzerliği olan mekanlar arasındaki eşziyaretlere baktığımızda tam da yukarıda tanımladığımız problem ile karşılaşmış oluyorz. Eğer bir kullanıcı sıklıkla X dondurmacısı ve Y dondurmacısına gidiyorsa; X ve Y büyük olasılıkla benzerdir deriz. Bu ölçüm büyük şehirlerde ve çok fazla insan trafiği ile birlikte zengin mekan bilgisi olan şehirlerde çok işe yarıyor. Peki ya daha küçük nüfuslu bir şehre veya mahalleye bakıyorsak ?
Tatlar (Tastes)
Tatlar sadece Foursquare’de bulunan ve mekan benzerliğini belirlemede değerli olan diğer başka bir özellik. Foursquare’deki her mekan ile ilişkilendirilmiş çeşitli tatlar mevcut, yani eğer çok fazla check-ini olmayan mekanlarımız var ise aradaki açığı tatlar ile kapatıyoruz. Genel olarak tat benzerliğini hesaplamak için tf-idf‘e bakarak iki mekan arasında eşleşen tatları buluyoruz. Bu ölçüm ile benzer ana tatlara sahip mekanları çok fazla eşziyaret olmasa bile gruplandırabiliyoruz. Tat benzerliği aynı zamanda görünürde alakasız ama aslında benzer yemek/deneyim sunan mekanları bulmamızda da yardımcı oluyor. Örneğin eğer Poutine hayranı iseniz hem Amerikan restoranı olan Citizen’s Band ve Şarap barı-Gastropub olan Jamber Wine Pub‘ı seveceksiniz.
Bütün bu parçalar favori mekanlarına benzer mekanları bulmak için birlikte çalışıyor. Bu çalışmanın sonucu olarak sunulan benzer mekan sayısında güzel bir artış sağladık ve bu yeni method sayesinde benzer mekanlar web CTR‘da Birleşik Devletlerde %7 global olarak ise %3 arttı. Eğer mekan sayfasına bakıyorsanız benzer mekanlara uygulamada veya webde göz atabilirsiniz.
Kaynak : Finding Similar Venues in Foursquare
