Найти

Результаты поиска

• МЕТОДЫ И АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ ТЕКСТОВЫХ ДАННЫХ (ОБЗОР)

  В.В. Бова , Ю.А. Кравченко , С.И. Родзин

  2022-11-01

  Аннотация ▼

  Рассматривается одна из важных задач искусственного интеллекта – машинная об-
  работка естественного языка. Решение данной задачи на основе кластерного анализа по-
  зволяет выявлять, формализовывать и интегрировать большие объемы лингвистической
  экспертной информации в условиях информационной неопределенности и слабой структу-
  рированности исходных текстовых ресурсов, полученных из различных предметных облас-
  тей. Кластерный анализ является мощным средством разведочного анализа текстовых
  данных, позволяющий провести объективную классификацию любых объектов, которые
  охарактеризованы рядом признаков и имеют скрытые закономерности. Проведен обзор и
  анализ современных модифицированных алгоритмов агломеративной кластеризации CURE,
  ROCK, CHAMELEON, неиерархической кластеризации PAM, CLARA и алгоритма аффинно-
  го преобразования, используемых на различных этапах кластеризации текстовых данных,
  эффективность которых проверяется экспериментальными исследованиями. В работе
  обоснованы требования к выбору наиболее эффективного метода кластеризации для ре-
  шения задачи повышения эффективности интеллектуальной обработки лингвистической
  экспертной информации. Также в работе рассмотрены способы визуализации результатов
  кластеризации для интерпретации кластерной структуры и зависимостей на множестве
  элементов текстовых данных и графические средства их представления в виде дендо-
  грамм, диаграмм рассеивания, диаграмм сходства VOS и карт интенсивности. Для сравне-
  ния качества работы алгоритмов использовались внутренние и внешние метрики эффек-
  тивности: «V-мера», «Adjusted Rand index», «Силуэт». На основании проведенных экспери-
  ментов выявлено, что необходимо использовать гибридный подход, в котором для перво-
  начального выбора числа кластеров и распределения их центров использовать иерархиче-
  ский подход, основанный на последовательном объединении и максимизации близости дан-
  ных ограниченной выборки, когда нет возможности выдвинуть гипотезу о начальном ко-
  личестве кластеров. Далее подключать алгоритмы итерационной кластеризации, обеспе-
  чивающие высокую устойчивость по отношению к шумовым признакам и наличию выбро-
  сов. За счет гибридизации повышается эффективность работы алгоритмов кластериза-
  ции. Результаты исследований показали, что для повышения вычислительной эффективно-
  сти и преодоления чувствительности при инициализации параметров алгоритмов класте-
  ризации для оптимизации параметров модели обучения и поиска глобального оптимального
  решения необходимо использовать метаэвристические подходы.

• АНАЛИЗ ВОЗМОЖНОСТЕЙ СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ ДЛЯ РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК

  А.К. Мельников , И.И. Левин , А.И. Дордопуло , И.В. Писаренко

  6-19

  2021-10-05

  Аннотация ▼

  В статье рассматривается решение вычислительно-трудоемкой задачи – расчета распределений вероятностей значений статистик – с помощью современных вычисли-тельных технологий. Для сокращения вычислительной сложности при обеспечении достаточного уровня эффективности критериев не ниже заданного порога предложено использование Δ-точных приближений. Для расчета точных приближений используется метод второй кратности, основанный на решении системы линейных уравнений, который позволяет при заданном вычислительном ресурсе рассчитывать точные приближения для максимальных значений параметров выборок. Наиболее трудоемкая часть метода второй кратности состоит в процедуре последовательного получения векторов возможных решений и их проверки на принадлежность к самим решениям. Проверка векторов возможных решений на принадлежность к решениям системы информационно независима, поэтому алгоритм расчета можно распараллелить по данным. Приведена формула определения алгоритмической сложности расчета точных приближений распределений вероятностей значений статистик, на основе которой получены оценки сложности современных практических задач для выборок со следующими значениями (N, n) мощности алфавита и объёма выборки: (256,1280), (128,640), (128, 320) и (192,3200) при точности расчета =10-5. Вычислительная сложность расчета составляет от 9,68·1022 до 1,60·1052 операций, средняя порядка 4,55·1025 операций, число проверяемых векторов – от 6,50·1023 до 1,39·1050, а число решений – от 4,67·1012 до 5,60·1025 соответственно. Общее время решения при круглосуточном режиме вычислений не должно превышать 30 дней или 2,592·106 сек. Для полученных оценок сложности проанализированы возможности современных кластерных вы-числительных систем на основе универсальных процессоров, графических ускорителей и реконфигурируемых вычислительных систем на основе программируемых логических интегральных схем. Для каждой технологии определено число вычислительных узлов, требуемых для расчета точных приближений с указанными параметрами в заданное время. Показано, что ни одна из рассмотренных вычислительных технологий на современном уровне развития техники не позволяет получить решение для необходимых параметров расчета точных приближений распределений вероятностей значений статистик. В заключении сделан вывод о необходимости анализа возможностей перспективных вычислительных технологий на основе квантовых и фотонных компьютеров, а также гибридных вычисли-тельных систем для расчета точных приближений распределений вероятностей значений статистик с заданными параметрами в оперативно-приемлемое время