كيفية تخزين مجموعات للعثور على أنماط مماثلة بسرعة ؟

Question

(هذا ليس واجب و لا تعمل المسألة.انها مجرد مصلحة شخصية/الاحتلال كلي خيالية.ولكن أنا مهتم في خوارزمية جيدة أو بنية البيانات.)

دعونا نفترض أن كنت اركض موقع التعارف.و ميزة خاصة أن في الفردي يقابله فيلم طعم.(لماذا لا؟)

في هذه الحالة سوف تحتاج إلى طريقة لتخزين فيلم التقييم لكل مستخدم.(حتى الآن لا توجد مشكلة.) وأود أن تحتاج إلى بنية بيانات للعثور على أفضل تركيب المستخدم.المسافة بين اثنين من طعم أنماط سيكون متوسط المسافة بين كل التقييم أن كل من أدلى المستخدمين.

على سبيل المثال

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

المسافة(X,Z) = متوسط( abs(9-9) + abs(1-4) ) = 1.5

المسافة(Y,Z) = متوسط( abs(4-6) + abs(6-4) + abs(8-7) ) = 1.666

حتى السيدX يناسب أفضل قليلا إلى السيدةZ من السيدY لا.

أنا أحب soulution أن ...

• ...لا تحتاج إلى كثير من العمليات على قاعدة البيانات
• ...لا تحتاج إلى التعامل مع الكثير من البيانات
• ...تشغيل سريع
• ...تقديم أفضل مطابقة
• ربما أود أن تنظر جيدا تقريبية جدا.

نحاول أن نضع في اعتبارنا أن هذا ينبغي أيضا العمل مع الآلاف من الممكن الأفلام المستخدمين أن معدل فقط حوالي 20-50 الأفلام الآلاف من المستخدمين.

(لأن هذا هو لغز عقلي وليس مشكلة حقيقية ، العمل arrounds لا يساعد حقا.)

ماذا سيكون الخاص بك خوارزمية البحث أو بنية البيانات ؟

Answer 1

يبدو الكثير مثل نيتفليكس الجائزة التحدي ، وبشكل أكثر تحديدا في النصف الأول من النهج الأكثر شعبية.تطبيقات ممكنة من ما كنت تحاول أن تفعل عديدة ومتنوعة.لا أحد منهم كفاءة استثنائية ، L1 متري هو خيار جيد خاصة موثوقة المتبادلة.

Answer 2

يبدو أنك تبحث عن أقرب الجيران في فيلم الفضاء.و المسافة الخاصة بك وظيفة هو L1 متري.ربما يمكنك استخدام فهرس الجغرافية من نوع ما.ربما يمكنك استخدام تقنيات من تصفية التعاونية.

Answer 3

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance

وسوف يكون تعقيد O(n^1.5)) بدلا من O(n²) ، كما سيكون هناك n مقارنات sqrt(n) الأفلام (متوسط أفلام مليئة معا من كل زوج).