تحديد عدد المجموعات في مجموعة البيانات
المنهج المعلوماتي النظري

تم تطبيق نظرية تشوه المعدل على اختيار K والتي تسمى طريقة "القفزة"، والتي تحدد عدد المجموعات التي تزيد من الكفاءة مع تقليل الخطأ وفقًا لمعايير نظرية المعلومات.  تتمثل استراتيجية الخوارزمية في إنشاء منحنى تشويه لبيانات الإدخال عن طريق تشغيل خوارزمية التجميع القياسية مثل الخوارزمية التصنيفية لجميع قيم k بين 1 وn، وحساب التشويه (الموصوف أدناه) للتجميع الناتج. ويتم بعد ذلك تحويل منحنى التشوه بقوة سلبية يتم اختيارها بناءً على أبعاد البيانات. ثم تشير القفزات في القيم الناتجة إلى خيارات معقولة لـ k، حيث تمثل القفزة الأكبر الخيار الأفضل.
يتم تعريف تشوه تجميع بعض بيانات الإدخال رسميًا على النحو التالي: دع مجموعة البيانات يتم نمذجتها كمتغير عشوائي X ذو p بعد، يتكون من توزيع خليط من مكونات G مع تغاير مشترك، Γ . إذا كانت  c_{1}\ldots c_{K} مجموعة من مراكز المجموعة K، مع  c_{X} أقرب مركز لعينة معينة من X، فإن الحد الأدنى للتشوه المتوسط لكل بعد عند ملاءمة مراكز K للبيانات هو:
وهذا أيضًا هو متوسط مسافة ماهالانوبيس لكل بُعد بين X وأقرب مركز مجموعة  c_{X} . نظرًا لأن التقليل إلى أدنى حد على جميع مجموعات مراكز المجموعة الممكنة معقد للغاية، يتم حساب التشوه عمليًا عن طريق إنشاء مجموعة من مراكز المجموعة باستخدام خوارزمية تجميع قياسية وحساب التشوه باستخدام النتيجة.
اختيار قوة التحويل  Y=(p/2) يتم تحفيزه من خلال التحليل المقارب باستخدام نتائج من نظرية تشوه المعدل. دع البيانات X لها توزيع غاوسي واحد تعسفي ذو p بعج، ودع البيانات الثابتة  K=\lfloor \alpha ^{p}\rfloor ، لبعض α أكبر من الصفر. ثم يكون تشوه مجموعة من K مجموعة في الحد عندما تتجه p إلى ما لا نهاية هو  \alpha ^{-2}. يمكن أن نرى أنه بشكل مقارب، تشويه التجميع إلى القوة  (-p/2) يتناسب مع  \alpha ^{p}، والذي بحكم التعريف يساوي تقريبًا عدد المجموعات K. بعبارة أخرى، بالنسبة لتوزيع غاوسي واحد، فإن زيادة K بما يتجاوز العدد الحقيقي للمجموعات، والذي يجب أن يكون واحدًا، يسبب نموًا خطيًا في التشويه. يعد هذا السلوك مهمًا في الحالة العامة لمزيج من مكونات التوزيع المتعددة.
ليكن X مزيجًا من توزيعات غاوسية ذات p بعد ذات تباين مشترك. ثم بالنسبة لأي قيمة ثابتة K أقل من G، فإن تشوه التجميع عندما يتجه p إلى ما لا نهاية يكون لانهائيًا. بديهيًا، هذا يعني أن التجميع الذي يحتوي على عدد أقل من العدد الصحيح من التجمعات غير قادر على وصف البيانات عالية الأبعاد بشكل مقارب، مما يتسبب في زيادة التشوه دون حدود. إذا، كما هو موضح أعلاه، تم جعل K دالة متزايدة لـ p ، أي،  K=\lfloor \alpha ^{p}\rfloor ، يتم تحقيق نفس النتيجة المذكورة أعلاه، مع قيمة التشويه في الحد مع انتقال p إلى ما لا نهاية مساوية لـ  \alpha ^{-2}. وعليه، هناك نفس العلاقة التناسبية بين التشوه المحول وعدد المجموعات، K.
من خلال جمع النتائج أعلاه معًا، يمكننا أن نرى أنه بالنسبة للقيم المرتفعة بدرجة كافية لـ p، فإن التشوه المحول  d_{K}^{-p/2} تكون تقريبًا صفرًا بالنسبة لـ K < G، ثم تقفز فجأة وتبدأ في الزيادة خطيًا بالنسبة لـ K ≥ G. تستخدم خوارزمية القفز لاختيار K هذه السلوكيات لتحديد القيمة الأكثر احتمالية للعدد الحقيقي للمجموعات.
وعلى الرغم من أن الدعم الرياضي للطريقة يتم تقديمه من حيث النتائج المقاربة، فقد تم التحقق تجريبياً من أن الخوارزمية تعمل بشكل جيد في مجموعة متنوعة من مجموعات البيانات ذات الأبعاد المعقولة. بالإضافة إلى طريقة القفزة الموضعية الموضحة أعلاه، توجد خوارزمية ثانية لاختيار K باستخدام نفس قيم التشوه المحولة والمعروفة باسم طريقة الخط المكسور. تحدد طريقة الخط المكسور نقطة القفزة في رسم التشويه المحول عن طريق إجراء ملاءمة خطية بسيطة لخطأ المربعات الصغرى لقطعتي خط، والتي من الناحية النظرية ستقع على طول المحور السيني لـ K < G، وعلى طول الطور المتزايد خطيًا لمخطط التشويه المحول لـ K ≥ G. تعتبر طريقة الخط المكسور أكثر قوة من طريقة القفزة في أن قرارها عالمي وليس محليًا، لكنها تعتمد أيضًا على افتراض مكونات الخليط الغاوسي، في حين أن طريقة القفزة غير معيارية تمامًا وقد ثبت أنها قابلة للتطبيق لتوزيعات الخليط العامة.