В задачах кластеризации требуется разбить данное множество объектов на несколько подмножеств (кластеров) только на основе сходства объектов друг с другом. Рассматривается вариант задачи кластеризации графа, являющийся одной из формализаций задачи кластеризации с частичным обучением. Доказано, что эта задача является NP-трудной. Для одного варианта задачи предложен полиномиальный 3-приближённый алгоритм.
Скачать электронную версию публикации
Загружен, раз: 219
- Title Об одной задаче кластеризации графа с частичным обучением
- Headline Об одной задаче кластеризации графа с частичным обучением
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 42
- Date:
- DOI 10.17223/20710410/42/5
Ключевые слова
граф, кластер, кластеризация с частичным обучением, graph, cluster, semi-supervised clusteringАвторы
Ссылки
Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения. М.: ФАЗИС, 2005.
Kulis B., Basu S., Dhillon I., and Mooney R. Semi-supervised graph clustering: a kernel approach // Mach. Learn. 2009. V. 74. No. 1. P. 1-22.
Schaeffer S. E. Graph clustering // Comput. Sci. Rev. 2005. V. 1. No. 1. P. 27-64.
Bair E. Semi-supervised clustering methods // Wiley Interdisciplinary Reviews: Computational Statistics. 2013. V. 5. No. 5. P. 349-361.
Chapelle O, Scholkopf B., and Zein A. Semi-supervised Learning. Cambridge, Massachusets: MIT Press, 2006.
Ильев А. В., Ремесленников В. Н. Исследование совместности систем уравнений над графами и нахождение их общих решений // Вестник Омского университета. 2017. №4(86). С. 26-32.
Shamir R., Sharan R., and Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144. No. 1-2. P. 173-182.
Zahn C. T. Approximating symmetric relations by equivalence relations // J. Soc. Indust. Appl. Math. 1964. V. 12. No. 4. P. 840-847.
Tomescu I. La reduction minimale d'un graphe a une reunion de cliques // Discrete Math. 1974. V. 10. No. 1-2. P. 173-179.
Фридман Г. Ш. Исследование одной задачи классификации на графах // Методы моделирования и обработка информации. Новосибирск: Наука, 1976. С. 147-177.
Ильев В. П., Фридман Г. Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. 1982. Т. 264. №3. С. 533-538.
Bansal N., Blum A., and Chaw la S. Correlation clustering // Mach. Learn. 2004. V. 56. No. 1-3. P. 89-113.
Ben-Dor A., Shamir R., and Yakhimi Z. Clustering gene expression patterns // J. Comput. Biol. 1999. V. 6. No. 3-4. P. 281-297.
Ильев В. П., Навроцкая А. А. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикладная дискретная математика. 2011. №3(13). С. 80-84.
Krivanek M. and Moravek J. NP-hard problems in hierarchical-tree clustering // Acta Inform. 1986. V. 23. P. 311-323.
Giotis I. and Guruswami V. Correlation clustering with a fixed number of clusters // Theory Comput. 2006. V.2. No. 1. P. 249-266.
Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13. №1. С. 3-11.
Coleman T., Saunderson J., and Wirth A. A local-search 2-approximation for 2-correlation clustering // ESA 2008. LNCS. 2008. V.5193. P. 308-319.
Ильев В. П., Ильева С. Д., Навроцкая А. А. Приближенные алгоритмы для задач аппроксимации графов // Дискрет. анализ и исслед. операций. 2011. Т. 18. №1. С. 41-60.
Charikar M., Guruswami V., and Wirth A. Clustering with qualitative information // J. Comput. Syst. Sci. 2005. V.71. No.3. P. 360-383.
Ailon N., Charikar M., and Newman A. Aggregating inconsistent information: Ranking and clustering // J. ACM. 2008. V. 55. No. 5. P. 1-27.
Il'ev V., Il'eva S., Kononov A. Short survey on graph correlation clustering with minimization criteria // DOOR 2016. LNCS. 2016. V.9869. P. 25-36.
Об одной задаче кластеризации графа с частичным обучением | Прикладная дискретная математика. 2018. № 42. DOI: 10.17223/20710410/42/5
Скачать полнотекстовую версию
Загружен, раз: 535