n boyutlu eşleştirme algoritması

Question

Bazı tavsiyeleri burada bulabilirsiniz. N-boyutlu bir alanda eşleşen algoritmaya bakmaya başlamak için iyi bir yer bilen var mı? Örneğin, orada herhangi bir arkadaşlık sitesi 2 kişi ile eşleştirmek için bir çeşit algoritma kullanmalıdır. Okuduğum şey, bir karakterin özelliklerini, her bir karakteristik için bir nokta sistemi ile n boyutlu bir dizide haritalayabilmemizdir. Bir insanın tüm (mevcut) özelliklerine sahip olduktan sonra, bu kişiyi n boyutlu bir dizi içinde bir noktada temsil edebiliriz. Daha sonra, 2 kişiyi eşleştirmek için bu n-dim dizisinde 2 nokta arasındaki en kısa mesafeyi bulmak kadar basit olacaktır. Bu tür bir algoritmanın uygulanmasında herhangi bir referans var mı? Bu tür şeyleri yazmanın en iyi dili nedir?

Answer 1

Öncelikle en tanıdık olduğunuz dili seçin. Bunu işlemek için algoritmalar oldukça basittir ve herhangi bir modern dilde çalışmalıdır. (Bir dizi dizi ve potansiyel olarak bir matris kütüphanesi olduğu sürece, iyi olmalısınız.) Bunlardan birçoğunu C, C++ ve C# 'de uygulamıştım ama python, vb.net, vb.

Ne yapmaya çalıştığınıza bağlı olarak, birkaç seçenek vardır.

Bu söylenecek şey, yapmak istediğiniz hedeflere bağlıdır. En iyi eşleşmeyi bulmak istiyorsanız, basit mesafe hesaplamaları kullanabilirsiniz (örneğin: n boyutlu dizideki her boyut/özellik için karelerin toplamı), isteğe bağlı olarak her özellik uzaklığı ve en yakın noktayı kullanın.

İnsanları gruplandırmak istiyorsanız, clustering algorithms'a bakmak isteyeceksiniz. Böyle bir veri için, K-Means'in bir çeşit kümelenmesinin ya da bulanık c-araç kümelenmesinin en iyi şekilde çalışacağından şüphelenirim. Eğer bir kişi için en yakın eşleşmeyi bulmak istiyorsanız

Answer 2

Bentley & Shamos çok boyutlu bir böl ve fethet yöntemi yayınlanan: O'da Böl ve yönet süresini (N, N log): Divide-and-conquer in multidimensional space Proceedings of Bilgisayar teorisi üzerine sekizinci yıllık ACM sempozyumu 1976. this bir kopyasını alamıyorsanız, yardımcı olabilir. Ancak, örnek uygulamanız için en yakın komşusu bulmak en büyük sorun olarak görünmüyor - pek çok şey, girdileri boyutlara ayırıyor. Örneğin, bir boyut "hayvanları sever" ise, & kediyi seven ama atlara dayanamayan birine ne değeri veriyorsunuz? Atları seven, köpeklerin iyi olduğunu düşünen, kediler tarafından rahatsız edilen ve akvaryum balığı konusunda kararsız olan nedir?

Answer 3

Bahsettiğiniz işlem k = 1 ile k-en yakın komşu olarak bilinir. Benzer vektörleri bulmak için en sezgisel yaklaşımdır.

http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

Answer 4

Nasıl çözümü aşağıdaki ilgili.

Kullanıcıların U1, U2, U3, U4, U5 olduğunu varsayalım. Nitelikler A1, A2, A3, A4, A5 ..... Am

Mağaza olan bu

A1

olarak - U1, U2, U3 ... A2 - U4, U6, U7 ... A3 -

Profil özniteliği, dizin ve tüm kullanıcıları depolar. Şimdi, eğer yeni bir Kullanıcı gelirse, onun niteliklerine bakın ve bu nitelikler için ortak insanları bulun. Bu listelerde bir kişinin var olduğu zaman sayısı - yüksek sıralama.

Answer 5

Örneğinizle anlattığınız n boyutsal eşleşme değil, birden çok özelliğe sahip düğümlerin bipartite matching olmasıdır. (Bu mesafeyi iki kişi hesapladığında verilen bir işlevi sağlamanız gerekecektir). Bunun için çok verimli algoritmalar olmalı. N boyutsal eşleştirmede, düğümleri ikiden fazla kümeyle eşleştirmeyi denediniz (örneğinizde, insanları bedene, ruha ve müzik tercihlerine indirebileceğinizi, sonra bunları yeni kişiler haline getirebildiğinizi varsayalım. Daha sonra n-boyutlu eşleşme insanları birbirinden ayırın ve onları yeniden tasarlayın, böylece yeni kişiler gerçekten güzel çiftler yaparlar: D) İşte np-complete olan wikipedia article for 3-dimentional matching.

Ayrıca, başka biri tarafından da belirtildiği gibi, hedefiniz kişilerle eşleşmiyorsa, ancak uyumlu gruplar buluyorsa, bunları gruplara ayırmayı düşünmelisiniz. Bu, örn. Unsupervised Learning