كشف التشابه السريع

Question

لدي مجموعة كبيرة من الأشياء وأحتاج إلى معرفة أوجه التشابه بينها.

لأكون أكثر دقة:بالنظر إلى كائنين يمكنني حساب اختلافهما كرقم، أ قياس - القيم الأعلى تعني تشابهًا أقل، والصفر يعني أن الكائنات لها محتويات متطابقة.تتناسب تكلفة حساب هذا الرقم مع حجم الجسم الأصغر (كل كائن له حجم معين).

أحتاج إلى القدرة على العثور بسرعة، في ضوء كائن ما، على مجموعة الكائنات المشابهة له.

لأكون أكثر دقة:أحتاج إلى إنتاج بنية بيانات تقوم بتعيين أي كائن o إلى مجموعة الكائنات التي لا تختلف عن o أكثر من d، بالنسبة لبعض قيم الاختلاف d، بحيث لا يستغرق إدراج الكائنات في المجموعة وقتًا أكثر مما لو كانت في مصفوفة أو قائمة مرتبطة (وربما تكون كذلك بالفعل).عادة، ستكون المجموعة أصغر بكثير من العدد الإجمالي للكائنات، لذلك من المفيد حقًا إجراء هذه العملية الحسابية.إنه أمر جيد بما فيه الكفاية إذا كانت بنية البيانات تفترض وجود d ثابتًا، ولكن إذا كانت تعمل مع d عشوائيًا، فهذا أفضل.

هل رأيت هذه المشكلة من قبل أو شيء مشابه لها؟ما هو الحل الجيد؟

لأكون أكثر دقة:يتضمن الحل المباشر حساب الاختلافات بين جميع أزواج الكائنات، ولكن هذا بطيء - O(n²) حيث n هو عدد الكائنات.هل هناك حل عام أقل تعقيدا؟

Answer 1

دون معرفة المزيد من التفاصيل حول القياس، من الصعب القول. ليس لدي أي أفكار للقضاء على جانب O (n ^ 2)، ولكن قد يكون هناك طريقة للحد من بعض الثوابت المعنية. على سبيل المثال، إذا كان لديك متري Euclidean D (P و Q) = SQRT ((p_1-q_1) ^ 2 + .. + (p_n-q_n) ^ 2)، يمكنك مربع المسافة الخاصة بك و مقارنته بالجزئي مبالغ (p_i-q_i) ^ 2 وتوقف عند تجاوز D ^ 2.

ما إذا كان هذا سيوفر في الواقع الوقت يعتمد الوقت على مدى مكلفة المقارنة هو مجرد حساب الاستلقاء وعدد حسابات القوائم التي يمكن أن تتوقع تجنبها عن طريق القيام بذلك (من الواضح، أصغر D، أفضل).

Answer 2

أحتاج إلى إنتاج بنية بيانات تقوم بتعيين أي كائن O إلى مجموعة الكائنات لا مزيد من اختصارها إلى O من D، لبعض القيمة الاختلاف D.

قد يكون من الأسرع للتخلي عن حساب التشابه عندما يصبح المجموع الفرعي أكبر من d. وبعد على سبيل المثال، إذا كانت أوجه التشابه بناء على مسافات جيب التمام أو Hausdorff التي يمكن بسهولة القيام بها.

 

ملاحظة: إذا كان لا يمكن القيام بذلك، فقد تكون مشكلتك مرتبطة بمشكلة جيران K-Learps (أو أكثر دقة أقرب مشكلة جار مع وجود حي عتبة). يجب أن تبحث عن الخوارزميات التي تجد أعضاء قريبة دون حوسبة جميع المسافات (ربما شيء باستخدام عدم المساواة مثلث). يجب أن تساعدك ويكيبيديا على استكشاف الخوارزميات المناسبة.

Answer 3

إذا كان مقياس التشابه الخاص بك متعديا، فلن تضطر إلى حساب التشابه لجميع أزواج الكائنات منذ كائنات A، B، C:

similarity(a,c) = similarity(a,b) op similarity(b,c)

أين op هو عامل ثنائي مثل الضرب أو الإضافة.

Answer 4

أعتقد أن الحل يعتمد على الكثير من التفاصيل حول طبيعة مشكلتك.

1. هل تحتاج إلى العثور على كائنات مماثلة لنفس الكائن عدة مرات، أم مرة واحدة فقط؟إذا كان ذلك عدة مرات، فإن إنشاء بنية بيانات حيث تقوم بحساب الفرق مرة واحدة لكل زوج ثم توصيل الكائنات بكائنات مماثلة بحيث يمكنك استرداد القائمة بسرعة دون إعادة الحساب قد يكون بمثابة تحسين مفيد للغاية للأداء.

2. ما هي طبيعة الحساب؟من ناحية، إذا كانت طبيعة الاختلاف هي، على سبيل المثال، الفرق في الارتفاع بين شخصين، فإن الحفاظ على القائمة مرتبة حسب الارتفاع سيتيح لك العثور على الكائنات المتشابهة بسرعة كبيرة.أفترض أن المشكلة الحقيقية أكثر تعقيدًا من ذلك، ولكن وفقًا لهذا المنطق، إذا كان الفرق هو مجموع عدة كميات خطية، فيمكنك إنشاء مصفوفة متعددة الأبعاد، ثم تخيل من الناحية النظرية مجموعة الكائنات المتشابهة مثل تلك داخل مجال n الأبعاد (أيدائرة، كرة، كرة مفرطة، إلخ) تتمحور حول الكائن المرجعي، ثم ابحث عنها مرة أخرى مباشرةً.في الواقع، يخطر لي أنه إذا كانت حسابات نصف القطر معقدة جدًا أو تستغرق الكثير من وقت التشغيل، فإن التقريب الجيد سيكون إنشاء مكعب ذو أبعاد n (أي.Square، cube، tesseract، إلخ) حول الكائن المرجعي، واسترجع جميع الكائنات الموجودة داخل هذا المكعب كـ "مرشحين"، ثم قم بإجراء الحساب الفعلي على المرشحين.

على سبيل المثال، لنفترض أن "الفرق" هو ​​مجموع القيم المطلقة للاختلافات بين ثلاث سمات، على سبيل المثال a1 وa2 وa3.يمكنك إنشاء مصفوفة ثلاثية الأبعاد وتعيين قيمة كل عقدة من المصفوفة على الكائن بهذه القيم، إن وجدت.ثم إذا كنت تريد العثور على جميع الكائنات التي يكون اختلافها أقل من d عن الكائن o، فيمكنك كتابة:

for (x1=o.a1-d;x1<o.a1+d;++x1)
{
  for (x2=o.a2-d;x1<o.a2+d;++x2)
  {
    for (x3=o.a3-d;x1<o.a3+d;++x3)
    {
      if (array[x1][x2][x3]!=null
        && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
        {
          ... found a match ...
        }
    }
  }
}

أظن أن قواعد الاختلاف أكثر تعقيدًا من ذلك، لكن حسنًا، ما عليك سوى إضافة تعقيد إلى الآلية لتتناسب مع تعقيد القواعد.الهدف هو استخدام المصفوفة لتحديد مجموعة الكائنات التي يتعين عليك فحصها.

3. مرة أخرى حول طبيعة الحساب:إذا كان أحد العناصر التي تشكل الفرق، أو بعض المجموعات الفرعية الصغيرة، يميل إلى أن يكون أكثر أهمية من العناصر الأخرى، فقم بإنشاء بنية بيانات تسمح لك بمقارنة ذلك بسرعة ضمن النطاق.إذا كان في النطاق، قم بإجراء مقارنة كاملة.إذا لم يكن الأمر كذلك، فأنت لا تنظر إليه حتى.

Answer 5

أليس من الممكن استخدام كD-Tree؟

قد يكون من الضروري (إن أمكن) لتطبيع الأبعاد. بعد ذلك، تحتاج فقط إلى ملء الشجرة، واستخدم بحث "أقرب جيران N"، وحاول العثور على أي كائن داخل نطاق معين.

Answer 6

مثال على الكائنات: الصور والمستندات. بالطبع العمل مع التمثيل الخام لهذه الكائنات غير مفيدة في الغالب. عادة ما يقوم المرء بمعالجة النموذج الخام مسبقا وإيقاف تشغيله إلى بعض النموذج الطبيعي (للمستندات، ويقول ناقلات يمثل كل إدخال رقم / النسبة المئوية من المرات التي ظهرت كلمة معينة، للصور يمكن أن يكون تمثيلا للعماات المرئية الموجودة في الصورة).

إذا تم إصلاح D و A ^ 2 مسبقا هو ممكن، فيمكنك فقط استخدام تمثيل رسم بياني باستخدام قائمة مرتبطة لكل كائن على سبيل المثال. يمكنك الحصول على حلول أكثر كفاءة على حساب الدقة باستخدام خوارزميات القريب أقرب جيران.

Answer 7

هل يمكننا أن نفترض أن التشابه غير متعدي، أي. diff(a,c) == diff(a,b) + diff(b,c)ب إذا كان الأمر كذلك، يمكنك تجربة ما يلي:

1. فرز مجموعة الكائنات. إذا لم يكن لدى مقياس التشابه الكائن قيمة مطلقة لائقة، فيمكنك تحديد كائن واحد بشكل تعسفي ك "صفر" وفرز جميع الكائنات الأخرى حسب تشابهها لهذا الكائن.
2. للعثور على الكائنات مع التشابه s ل o, ، تجد o في القائمة الفرز، والبحث على اليسار وإلى اليمين حتى ينمو فرق أكبر من s.

ميزة هذه هي أن الفرز يمكن القيام به مرة واحدة، والبناء المحدد اللاحق يتناسب مع عدد الأعضاء الذين سيكونون في المجموعة.

Answer 8

يبدو وكأنه شجرة bk. هنا مثال صغير. وبعد يمكنك إنشاء شجرة وتحقق من الفرع الذي يجب استخدامه بحثا عن كائن مماثل ولا، لذلك يمكنك منع O(n2)