كيفية الكتلة الكائنات (بدون الإحداثيات)

Question

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

class Thing {
    public double DistanceTo(Thing other);
}

أود أن تجمع هذه الكائنات.أود أن السيطرة على عدد من المجموعات و أود من أجل "إغلاق" الأشياء أن تكون في نفس المجموعة:

List<Cluster> cluster(int numClusters, List<Thing> things);

يمكن لأي شخص أن يقترح (وصلة ;-)) بعض خوارزميات التجميع (أبسط أفضل!) أو المكتبات التي يمكن أن تساعدني ؟

التوضيح معظم خوارزميات التجميع تتطلب أن الكائنات تكون وضعت في بعض الابعاد الفضاء.هذا الفضاء هو استخدامها للعثور على "النقطة الوسطى" من المجموعات.في حالتي, أنا لا أعرف ما هو ولا أعرف كيفية استخراج تنسيق نظام من الأجسام. كل ما أعرفه هو كيف متباعدة 2 الكائنات. وأود أن تجد جيدة خوارزمية التجميع التي تستخدم فقط تلك المعلومات.

تخيل أنك التجميع على أساس "رائحة" كائن.كنت لا تعرف كيفية وضع "رائحة" في 2D الطائرة ، ولكن كنت لا تعرف ما إذا كان اثنين من رائحة مماثلة أم لا.

Answer 1

أعتقد أنك تبحث عن K-Medoids.انها مثل K-يعني في ذلك تحديد عدد مجموعات ، K, مقدما ولكن أنها لا تتطلب أن يكون لديك مفهوم "المتوسط" الكائنات أنت تجميع مثل K-يعني لا.

بدلا من ذلك, كل مجموعة لديها ممثل medoid, وهو عضو في الكتلة الأقرب إلى الوسط.يمكنك التفكير في الأمر على النحو نسخة من K-يعني أن يجد "الوساطات" بدلا من "الوسائل".كل ما تحتاجه هو المسافة متري إلى المجموعة الأشياء و لقد استعملت هذا في بعض من أعمالي الخاصة بالضبط نفس الأسباب التي ذكرها.

من السذاجة K-medoids ليس أسرع الخوارزمية ، ولكن هناك بسرعة المتغيرات التي ربما تكون جيدة بما فيه الكفاية لأغراض الخاصة بك.هنا وصف الخوارزميات و وصلات إلى وثائق تنفيذها في R:

1. بام الأساسية O(n^2) تنفيذ K-medoids.
2. كلارا هو أسرع بكثير ، عينات النسخة بام.وهو يعمل عن طريق تجميع عشوائي عينات فرعية من الكائنات مع بام و تجميع مجموعة كاملة من الكائنات على أساس فرعية.يجب أن تكون لا تزال قادرة على الحصول على جيد جدا clusterings سريع مع هذا.

إذا كنت بحاجة إلى مزيد من المعلومات ، هنا ورق الذي يعطي لمحة عامة عن هذه وغيرها من K-medoids الأساليب.

Answer 2

وهنا لمحة عامة عن خوارزمية التجميع التي لا تملك K-يعني اشتراط إيجاد النقطه الوسطى.

1. تحديد المسافة بين كل الكائنات.سجل n معظم كائنات منفصلة.
   [يجد جذور لدينا مجموعات الوقت O(n^2)]
2. تعيين كل من هذه n نقاط عشوائية على n جديدة متميزة المجموعات.
3. لكل كائن آخر:
   [تعيين الأشياء إلى مجموعات الوقت O(n^2)]
   1. لكل مجموعة:
      1. حساب متوسط المسافة من مجموعة إلى هذا الكائن عن طريق حساب متوسط المسافة من كل كائن في الكتلة إلى الكائن.
         
   2. تعيين كائن إلى أقرب العنقودية.

هذه الخوارزمية بالتأكيد مجموعة الكائنات.ولكن لها وقت O(n^2).بالإضافة إلى أنها تسترشد الأولى n نقاط المختار.

يمكن لأي شخص تحسين على هذا (أفضل وقت الأداء, أقل اعتمادا على الخيارات الأولية)?أنا أحب أن أرى الأفكار الخاصة بك.

Answer 3

وهنا سريع الخوارزمية.

While (points_left > 0) {
 Select a random point that is not already clustered
 Add point and all points within x distance 
   that aren't already clustered to a new cluster.
}

بدلا من ذلك, قراءة صفحة ويكيبيديا.K-means clustering هو خيار جيد:

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

الخوارزمية هي الخطوات:

* Choose the number of clusters, k.
* Randomly generate k clusters and determine the cluster centers, or
  directly generate k random points as cluster centers.
* Assign each point to the nearest cluster center.
* Recompute the new cluster centers.
* Repeat the two previous steps until some convergence criterion is
  met (usually that the assignment hasn't changed).

المزايا الرئيسية هذه الخوارزمية هي البساطة و السرعة التي يسمح لها أن تعمل على مجموعات كبيرة من البيانات.عيبه هو أنه لا العائد نفس النتيجة مع كل تشغيل ، منذ الناتجة مجموعات تعتمد على الأولي عشوائية المهام.ذلك يقلل داخل المجموعات التباين ، ولكن لا يضمن النتيجة العالمية الحد الأدنى من التباين.آخر العيب هو شرط مفهوم يعني أن تكون للتعريف الذي ليس هو الحال دائما.هذه البيانات ك-medoids البديل المناسبة.

Answer 4

ماذا عن هذا النهج:

1. تعيين كافة الكائنات إلى مجموعة واحدة.
2. العثور على اثنين من الكائنات ، a و ب, ، في إطار نفس المجموعة ، k, و التي هي أقصى مسافة حدة.إلى توضيح ، ينبغي أن يكون هناك واحد a و ب لمجموعة كاملة, لا أحد a و ب لكل مجموعة.
3. تقسيم المجموعات k إلى مجموعتين ، k1 و k2, مع وجوه a واحد مع كائن ب.
4. لجميع الكائنات الأخرى في المجموعة k, وإضافتها إلى إما k1 أو k2 من خلال تحديد الحد الأدنى متوسط المسافة إلى كل الكائنات الأخرى في هذه المجموعة.
5. كرر الخطوات من 2-5 حتى ن تتشكل مجموعات.

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

Answer 5

النشوء والتطور تسلسل الحمض النووي تحليل يستخدم بانتظام الهرمية تجميع على سلاسل نصية ، [محاذاة] المسافة المصفوفات.وهنا لطيفة R التعليمي لتجميع:

• http://www.statmethods.net/advstats/cluster.html

(اختصار:تذهب مباشرة إلى "الهرمية تكتلية" القسم...)

هنا هي بعض [اللغة] المكتبات :

• http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/البرامج/المجموعة/
• http://code.google.com/p/scipy-cluster/

هذا النهج يمكن أن تساعد في تحديد كيفية العديد من [ك] "الطبيعية" مجموعات هناك والتي تعترض استخدام جذور k-يعني النهج أعلاه.