Бинарные метрические деревья и иерархия вложенных кластеров
DOI:
https://doi.org/10.21638/spbu10.2024.405Аннотация
Методы машинного обучения используют деревья данных для организации и хранения информации. Каждая из таких структур обладает определенными преимуществами и позволяет улучшить качество конкретного алгоритма. Если у всех узлов дерева не более двух потомков, то оно называется бинарным; главное его преимущество — высокая эффективность реализации алгоритмов поиска и сортировки. В связи с этим важно отметить, что дендрограммы иерархических агломеративных методов кластеризации также относятся к бинарным деревьям и отражают таксономию элементов множества данных. Любой кластер, не являющийся синглетоном, можно разделить на подкластеры, что позволяет сформировать иерархическую структуру в метрическом пространстве (метрическое дерево) с дополнительными свойствами, например, автоматически задать высоту дерева, считая, по определению, что число уровней, на которых располагаются его узлы, совпадает с количеством вариантов разбиения выборочного множества на кластеры, подкластеры, подкластеры подкластеров и т. д. Такую задачу можно решить, используя аппроксимационно-оценочные критерии, изменение чувствительности которых при помощи коэффициента тренда дает возможность получить различные варианты кластеризации. При проведении вычислительных экспериментов использовалось синтетическое множество точек на евклидовой плоскости и изучались результаты его разбиения на кластеры центроидным методом. Марковские моменты остановки процесса кластеризации определялись посредством параболического аппроксимационно-оценочного критерия, построенного по четырем точкам. Верификация результатов, полученных при численном моделировании, производилась за счет изменения величины шага коэффициента тренда.
Ключевые слова:
метрическое дерево, агломеративная кластеризация, марковский момент, метод наименьших квадратов
Скачивания
Библиографические ссылки
Mwangi D. 5 common data structures and algorithms used in machine learning. URL: https://dzone.com/articles/5-common-data-structures-and-algorithms-used-in-ma (дата обращения: 19 сентября 2024 г.).
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to algorithms. 4th ed. Cambridge, Massachusetts, US: MIT Press and McGraw-Hill, 2022. 1312 p.
Quinlan J. R. Induction of decision trees // Machine Learning. 1986. Vol. 1. P. 81–106. https://doi.org/10.1007/BF00116251
Uhlmann J. K. Satisfying general proximity/similarity queries with metric trees // Information Processing Letters. 1991. Vol. 40. Iss. 4. P. 175–179. https://doi.org/10.1016/0020-0190(91)90074-R
Samet H. Foundations of multidimensional and metric data structures (The Morgan Kaufmann series in data management systems). San Francisco, US: Morgan Kaufmann Publ. Inc., 2006. 1024 p.
Bozkaya T., Ozsoyoglu Z. M. Indexing large metric spaces for similarity search queries // ACM Trans. Database Systems. 1999. Vol. 24. N 3. P. 361–404. https://doi.org/10.1145/328939.328959
Brin S. Near neighbor search in large metric spaces // 21th International Conference on Very Large Data Bases (VLDB 1995). September 11–15, 1995. Zurich, Switzerland, 1995. P. 574–584.
Жамбю М. Иерархический кластер-анализ и соответствия / пер. с фр. М.: Финансы и статистика, 1988. 344 с.
Calirnski T., Harabasz J. A dendrite method for cluster analysis // Communications in Statistics. 1974. N 3. P. 1–27.
Орехов А. В. Марковский момент остановки агломеративного процесса кластеризации в евклидовом пространстве // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2019. Т. 15. Вып. 1. С. 76–92. https://doi.org/10.21638/11701/spbu10.2019.106
Orekhov A. V. Agglomerative method for texts clustering // Lecture Notes in Computer Science. 2019. Vol. 11551 LNCS. P. 19–32. https://doi.org/10.1007/978-3-030-17705-8_2
Everitt B. S. Cluster analysis. Chichester, West Sussex, John Wiley & Sons Ltd. Press, 2011. 330 p.
Duda R. O., Hart P. E., Stor D. G. Pattern classification. New York, Chichester: Wiley Press, 2001. 654 p.
Lance G. N., Williams W. T. A general theory of classificatory sorting strategies. 1. Hierarchical systems // The Computer Journal. 1967. Vol. 9. P. 373–380.
Milligan G. W. Ultrametric hierarchical clustering algorithms // Psychometrika. 1979. Vol. 44. P. 343–346.
Thorndike R. L. Who belongs in the family? // Psychometrika. 1953. Vol. 18. P. 267–276. https://doi.org/10.1007/BF02289263
Олдендерфер М. С., Блэшфилд Р. К. Кластерный анализ // Факторный, дискриминантный и кластерный анализ / пер. с англ.; под ред. И. С. Енюкова. М.: Финансы и статистика, 1989. C. 139–209.
Orekhov A. V. Quasi-deterministic processes with monotonic trajectories and unsupervised machine learning // Mathematics. 2021. Vol. 9. Art. N 2301. https://doi.org/10.3390/math9182301
Левин Б. Р. Теоретические основы статистической радиотехники. М.: Радио и связь, 1989. 656 с.
Bodrunova S. S., Orekhov A. V., Blekanov I. S., Lyudkevich N. S., Tarasov N. A. Topic detection based on sentence embeddings and agglomerative clustering with Markov moment // Future Internet. 2020. Vol. 12. Art. N 144. https://doi.org/10.3390/fi12090144
Мазалов В. В. Математическая теория игр и приложения. СПб.: Лань, 2017. 448 с.
Булинский А. В., Ширяев А. Н. Теория случайных процессов. М.: Физматлит, 2003. 400 с.
Ширяев А. Н. Статистический последовательный анализ. 2-е изд. М.: Наука, 1976. 272 с.
Граничин О. Н., Шалымов Д. С., Аврос Р., Волкович З. Рандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика. 2011. № 4. С. 86–98.
Иерархическая кластеризация. URL: https://neerc.ifmo.ru/wiki/index.php?title=Иерархическая_кластеризация (дата обращения: 19 сентября 2024 г.).
Rousseeuw P. J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis // Journal of Comput. Appl. Math. 1987. Vol. 20. P. 53–65. https://doi.org/10.1016/0377-0427(87)90125-7
Kaufman L., Rousseeuw P. J. Finding groups in data: An introduction to cluster analysis. New York: John Wiley & Sons Inc., 1990. 342 p. https://doi.org/10.1002/9780470316801
Fisher R. A. The use of multiple measurements in taxonomic problems // Annals of Eugenics. 1936. Vol. 7. P. 179–188. http://dx.doi.org/10.1111/j.1469-1809.1936.tb02137.x
Snell-Hornby M. Translation studies: An integrated approach. Amsterdam: John Benjamins Publ., 1988. 172 p.
References
Mwangi D. 5 common data structures and algorithms used in machine learning. Available at: https://dzone.com/articles/5-common-data-structures-and-algorithms-used-in-ma (accessed: September 19, 2024).
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to algorithms. 4th ed. Cambridge, Massachusetts, US, MIT Press and McGraw-Hill Publ., 2022. 1312 p.
Quinlan J. R. Induction of decision trees. Machine Learning, 1986, vol. 1, pp. 81–106. https://doi.org/10.1007/BF00116251
Uhlmann J. K. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 1991, vol. 40, iss. 4, pp. 175–179. https://doi.org/10.1016/0020-0190(91)90074-R
Samet H. Foundations of multidimensional and metric data structures (The Morgan Kaufmann series in data management systems). San Francisco, US, Morgan Kaufmann Publ. Inc., 2006, 1024 p.
Bozkaya T., Ozsoyoglu Z. M. Indexing large metric spaces for similarity search queries. ACM Trans. Database Systems, 1999, vol. 24, no. 3, pp. 361–404. https://doi.org/10.1145/328939.328959
Brin S. Near neighbor search in large metric spaces. 21th International Conference on Very Large Data Bases (VLDB 1995), September 11–15, 1995. Zurich, Switzerland, 1995, pp. 574–584.
Jambue M. Iyerarkhicheskiy klaster-analiz i sootvetstviya [Hierarchical cluster analysis and correspondences]. Moscow, Finance and Statistics Publ., 1988, 344 p. (In Russian)
Calirnski T., Harabasz J. A dendrite method for cluster analysis. Communications in Statistics, 1974, no. 3, pp. 1–27.
Orekhov A. V. Markovskii moment ostanovki aglomerativnogo protsessa klasterizatsii v evklidovom prostranstve [Markov moment for the agglomerative method of clustering in Euclidean space]. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2019, vol. 15, iss. 1, pp. 76–92. https://doi.org/10.21638/11701/spbu10.2019.106 (In Russian)
Orekhov A. V. Agglomerative method for texts clustering. Lecture Notes in Computer Science, 2019, vol. 11551 LNCS, pp. 19–32. https://doi.org/10.1007/978-3-030-17705-8_2
Everitt B. S. Cluster analysis. Chichester, West Sussex, John Wiley & Sons Ltd. Press, 2011, 330 p.
Duda R. O., Hart P. E., Stor D. G. Pattern classification. New York, Chichester, Wiley Press, 2001, 654 p.
Lance G. N., Williams W. T. A general theory of classificatory sorting strategies. 1. Hierarchical systems. The Computer Journal, 1967, vol. 9, pp. 373–380.
Milligan G. W. Ultrametric hierarchical clustering algorithms. Psychometrika, 1979, vol. 44, pp. 343–346.
Thorndike R. L. Who belongs in the family? Psychometrika, 1953, vol. 18, pp. 267–276. https://doi.org/10.1007/BF02289263
Oldenderfer M. S., Blashfield R. K. Klasterniy analiz [Cluster analysis]. Faktorniy, diskriminantniy i klasterniy analiz [Factor, discriminant and cluster analysis]. Moscow, Finance and Statistics Publ., 1989, pp. 139–209. (In Russian)
Orekhov A. V. Quasi-deterministic processes with monotonic trajectories and unsupervised machine learning. Mathematics, 2021, vol. 9, art. no. 2301. https://doi.org/10.3390/math9182301
Levin B. R. Teoreticheskiye osnovy statisticheskoy radiotekhniki [Theoretical foundations of statistical radio engineering]. Moscow, Radio and Communication Publ., 1989, 656 p. (In Russian)
Bodrunova S. S., Orekhov A. V., Blekanov I. S., Lyudkevich N. S., Tarasov N. A. Topic detection based on sentence embeddings and agglomerative clustering with Markov moment. Future Internet, 2020, vol. 12, art. no. 144. https://doi.org/10.3390/fi12090144
Mazalov V. V. Matematicheskaya teoriya igr i prilozheniya [Mathematical game theory and applications]. St. Petersburg, Lan’ Publ., 2017, 448 p. (In Russian)
Bulinsky A. V., Shiryaev A. N. Teoriya sluchaynykh protsessov [Theory of random processes]. Moscow, Fizmatlit Publ., 2003, 400 p. (In Russian)
Shiryaev A. N. Statisticheskiy posledovatel'nyy analiz. 2-ye izd. [Statistical sequential analysis. 2nd ed.]. Moscow, Nauka Publ., 1976, 272 p. (In Russian)
Granichin O. N., Shalymov D. S., Avros R., Volkovich Z. Randomizirovannyy algoritm nakhozhdeniya kolichestva klasterov [Randomized algorithm for finding the number of clusters]. Automation and Telemechanics, 2011, no. 4, pp. 86–98. (In Russian)
Hierarchical clustering. Available at: https://neerc.ifmo.ru/wiki/index.php?title=Иерархическая_кластеризация (accessed: September 19, 2024). (In Russian)
Rousseeuw P. J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Comput. Appl. Math., 1987, vol. 20, pp. 53–65. https://doi.org/10.1016/0377-0427(87)90125-7
Kaufman L., Rousseeuw P. J. Finding groups in data: An introduction to cluster analysis. New York, John Wiley & Sons Inc. Publ., 1990, 342 p. https://doi.org/10.1002/9780470316801
Fisher R. A. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 1936, vol. 7, pp. 179–188. http://dx.doi.org/10.1111/j.1469-1809.1936.tb02137.x
Snell-Hornby M. Translation studies: An integrated approach. Amsterdam, John Benjamins Publ., 1988, 172 p.
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
