Published July 1, 2022
| Version v1
Publication
Open
The effective BRKGA algorithm for the <i>k</i>-medoids clustering problem
- 1. Universidade Federal Fluminense
- 2. Brazilian Institute of Geography and Statistics
Description
This paper presents a biased random-key genetic algorithm for k -medoids clustering problem. A novel heuristic operator was implemented and combined with a parallelized local search procedure. Experiments were carried out with fifty literature data sets with small, medium, and large sizes, considering several numbers of clusters, showed that the proposed algorithm outperformed eight other algorithms, for example, the classics PAM and CLARA algorithms. Furthermore, with the results of a linear integer programming formulation, we found that our algorithm obtained the global optimal solutions for most cases and, despite its stochastic nature, presented stability in terms of quality of the solutions obtained and the number of generations required to produce such solutions. In addition, considering the solutions (clusterings) produced by the algorithms, a relative validation index (average silhouette) was applied, where, again, was observed that our method performed well, producing cluster with a good structure.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تقدم هذه الورقة خوارزمية وراثية عشوائية المفتاح متحيزة لمشكلة تجميع الكيلو ميدويدات. تم تنفيذ مشغل إرشادي جديد ودمجه مع إجراء بحث محلي موازٍ. تم إجراء التجارب باستخدام خمسين مجموعة بيانات أدبية ذات أحجام صغيرة ومتوسطة وكبيرة، مع الأخذ في الاعتبار عدة أعداد من المجموعات، أظهرت أن الخوارزمية المقترحة تفوقت على ثماني خوارزميات أخرى، على سبيل المثال، خوارزميات PAM و CLARA الكلاسيكية. علاوة على ذلك، مع نتائج صياغة برمجة الأعداد الصحيحة الخطية، وجدنا أن خوارزميتنا حصلت على الحلول المثلى العالمية لمعظم الحالات، وعلى الرغم من طبيعتها العشوائية، قدمت الاستقرار من حيث جودة الحلول التي تم الحصول عليها وعدد الأجيال المطلوبة لإنتاج مثل هذه الحلول. بالإضافة إلى ذلك، بالنظر إلى الحلول (التجميعات) التي تنتجها الخوارزميات، تم تطبيق مؤشر التحقق النسبي (متوسط الصورة الظلية)، حيث لوحظ مرة أخرى أن طريقتنا أدت أداءً جيدًا، حيث أنتجت مجموعة ذات بنية جيدة.Translated Description (French)
Cet article présente un algorithme génétique à clé aléatoire biaisé pour le problème de regroupement des k-médoïdes. Un nouvel opérateur heuristique a été mis en œuvre et combiné à une procédure de recherche locale parallélisée. Des expériences ont été menées avec cinquante ensembles de données de la littérature de petites, moyennes et grandes tailles, en considérant plusieurs nombres de grappes, ont montré que l'algorithme proposé surpassait huit autres algorithmes, par exemple, les algorithmes classiques PAM et CLARA. De plus, avec les résultats d'une formulation de programmation linéaire d'entiers, nous avons constaté que notre algorithme obtenait les solutions optimales globales pour la plupart des cas et, malgré sa nature stochastique, présentait une stabilité en termes de qualité des solutions obtenues et du nombre de générations nécessaires pour produire de telles solutions. De plus, compte tenu des solutions (regroupements) produites par les algorithmes, un indice de validation relatif (silhouette moyenne) a été appliqué, où, encore une fois, on a observé que notre méthode fonctionnait bien, produisant des regroupements avec une bonne structure.Translated Description (Spanish)
Este artículo presenta un algoritmo genético de clave aleatoria sesgado para el problema de agrupamiento de k-medoides. Se implementó un nuevo operador heurístico y se combinó con un procedimiento de búsqueda local paralelizado. Los experimentos realizados con cincuenta conjuntos de datos de literatura con tamaños pequeños, medianos y grandes, considerando varios números de clústeres, mostraron que el algoritmo propuesto superaba a otros ocho algoritmos, por ejemplo, los clásicos algoritmos PAM y CLARA. Además, con los resultados de una formulación de programación entera lineal, encontramos que nuestro algoritmo obtuvo las soluciones óptimas globales para la mayoría de los casos y, a pesar de su naturaleza estocástica, presentó estabilidad en términos de calidad de las soluciones obtenidas y el número de generaciones requeridas para producir tales soluciones. Además, teniendo en cuenta las soluciones (clusters) producidas por los algoritmos, se aplicó un índice de validación relativo (silueta media), donde, de nuevo, se observó que nuestro método funcionaba bien, produciendo un cluster con una buena estructura.Files
ro220233.pdf.pdf
Files
(24 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:7624dcbc096921e31a1da610e19a546e
|
24 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- خوارزمية BRKGA الفعالة لمشكلة تجميع <i>k</i> - medoids
- Translated title (French)
- L'algorithme BRKGA efficace pour le problème <i>de</i>clustering des k-médoïdes
- Translated title (Spanish)
- El algoritmo BRKGA eficaz para el problema <i>de</i>agrupamiento de k-medoides
Identifiers
- Other
- https://openalex.org/W4292283840
- DOI
- 10.1051/ro/2022141
References
- https://openalex.org/W1128809682
- https://openalex.org/W1481798977
- https://openalex.org/W1493454437
- https://openalex.org/W1909728859
- https://openalex.org/W1967702193
- https://openalex.org/W1975552235
- https://openalex.org/W1983492939
- https://openalex.org/W2014363926
- https://openalex.org/W2014381197
- https://openalex.org/W2017504074
- https://openalex.org/W2025142996
- https://openalex.org/W2040929534
- https://openalex.org/W2046803845
- https://openalex.org/W2074629962
- https://openalex.org/W2083620785
- https://openalex.org/W2102750402
- https://openalex.org/W2126626732
- https://openalex.org/W2133962824
- https://openalex.org/W2138652284
- https://openalex.org/W2153233077
- https://openalex.org/W2153386665
- https://openalex.org/W2172264744
- https://openalex.org/W2498486790
- https://openalex.org/W2576431436
- https://openalex.org/W2744226525
- https://openalex.org/W2758138366
- https://openalex.org/W2786121513
- https://openalex.org/W2893447042
- https://openalex.org/W2961626057
- https://openalex.org/W2972260659
- https://openalex.org/W3083628579
- https://openalex.org/W3089047025
- https://openalex.org/W3089214407
- https://openalex.org/W3092610491
- https://openalex.org/W3100987608
- https://openalex.org/W3164387821
- https://openalex.org/W3165444694
- https://openalex.org/W325597738
- https://openalex.org/W4206491718
- https://openalex.org/W4229668725
- https://openalex.org/W4237698051
- https://openalex.org/W4241768805
- https://openalex.org/W4248603332