Алгоритм выбора характеристического элемента множества в задаче кластеризации

  • Трофимов Б.И. Кубанский государственный университет, Краснодар, Россия
  • Кольцов Ю.В. Кубанский государственный университет, Краснодар, Россия
  • Гарнага В.В. Кубанский государственный университет, Краснодар, Россия
УДК: 004.424.4, 004.93.14, 004.021, 004.023, 004.912

Аннотация

В статье предложен алгоритм выбора характеристического элемента множества в задаче кластеризации, разработан эмпирический критерий сходимости предлагаемого алгоритма. Также предложены два алгоритма генерации исходных данных для проведения экспериментальных исследований по сравнению результатов работы и быстродействия предлагаемого алгоритма, и на их основе проведено сравнение с алгоритмом полного перебора.

Ключевые слова: метод ветвей и границ, текстовый поиск, графовые модели, метрика Дамерау-Левенштейна

Информация об авторах

Богдан Игоревич Трофимов
аспирант кафедры информационных технологий Кубанского государственного университета
e-mail: bogdan.i.trofimov@mail.ru
Юрий Владимирович Кольцов
канд. физ.-мат. наук, заведующий кафедрой информационных технологий Кубанского государственного университета
e-mail: dean@fpm.kubsu.ru
Валерий Владимирович Гарнага
канд. физ.-мат. наук, доцент кафедры информационных технологий Кубанского государственного университета
e-mail: Garnaga.Valeriy@fpm.kubsu.ru

Литература

  1. Сокэл Р.Р. Кластер-анализ и классификация: предпосылки и основные направления. В кн.: Классификация и кластер / Под ред. Дж. Вэн Райзина. М.: Мир, 1980. С. 7-19.
  2. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов // ДАН СССР. 1965. Т. 163. № 4. С. 845-848.
  3. Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Econometrica. 1960. С. 497-520. doi: 10.1.1.308.7332.
  4. Bard G.V. Spelling-error tolerant, order-independent pass-phrases via the Damerau-Levenshtein string-edit distance metric // Proc. of ACSW '07 Proceedings of the Fifth Australasian symposium on ACSW frontiers. 2007. Vol. 68. P. 117-124.
  5. Гарнага В.В., Кольцов Ю.В., Трофимов Б.И. Построение механизма нейросетевого поиска на основе алгоритма расширяющегося нейронного газа // Известия вузов. Северо-Кавказский регион. Технические науки. 2014. Вып. 6. С. 12-17. doi: 10.17213/0321-2653-2014-6-12-17

Финансирование

Работа выполнена при поддержке РФФИ (13-01-00807).

Выпуск
Страницы
69-74
Прислано
2015-10-19
Опубликовано
2015-12-28