Диссертации, представленные на защиту и подготовленные в НИУ ВШЭ

В диссертации рассмотрена актуальная проблема выявления сообществ в графах, вершины которых охарактеризованы какими-то признаками, количественными или качественными. Автор формулирует проблему как задачу аппроксимации данных искомым разбиением с использованием критерия наименьших квадратов. Им сформулировано два подхода к (локальной) оптимизации критерия – последовательный и параллельный, а также введены две модификации: (а) конвертация признаковых данных в матрицу связей между объектами и (б) два способа использования связей, возникающие при глобальной их суммируемости, а также при отсутствии таковой. Эти модификации приводят к формированию нескольких методов выявления сообществ, для которых проведено широкое экспериментальное исследование, как на реальных, так и сгенерированных данных, показавшее и их валидность, и их эффективность в сравнении с методами, разработанными ведущими исследователями проблемы.

Диссертационная работа посвящена изучению фонологии и фонетики адыгских идиомов (абхазо-адыгская языковая семья). Так как основным предметом исследования является разнообразие адыгских идиомов, в первой главе представлена подробная социолингвистическая картина расселения адыгов и среднего и высшего образования на адыгских языках. Исследование направлено как на сегментную, так и на супрасегментную сторону языков. В диссертации впервые предлагается единообразное описание вокалических и консонантных систем, вводятся в научный оборот новые данные, собранные в ходе полевых исследований в 21 адыгском ауле, а также представлены исследования системы ударения, слоговой структуры и скорости речи в отдельных адыгских идиомах. Данные о звуковых инвентарях собраны автором в базу данных «The Circassian Consonant Correspondences Database», которая стала основой для кластеризации идиомов на основании фонологических инвентарей и регулярных соответствий, во многом совпавшая с традиционной классификацией адыгских языков. Для анализа слоговой структуры был разработан и применен алгоритм, который позволяет полуавтоматически проводить исследования слоговой структуры.

Диссертационная работа посвящена теме оптимизации производства с помощью решения задачи бикластеризации множеств производственных мощностей и производимых деталей. Данная задача в литературе называется задачей о формировании производственных ячеек (cell formation problem). В последние годы ее решению было посвящено большое количество работ, включающих множество различных эвристических алгоритмов (в частности метаэвристик) и несколько точных подходов. В качестве основных результатов исследования в диссертации доказан сложностной статус задачи для нескольких используемых в литературе целевых функций, разработаны два точных подхода для формулировки задачи с произвольным числом кластеров и дробной целевой функцией эффективности группировки (grouping efficacy), а также предложен эвристический алгоритм поиска во многих окрестностях с рестартами (variable neighborhood search). Еще одним вкладом работы стала корректировка имеющегося набора данных 35 GT и формирование нового набора данных из более редких задач в литературе. Вычислительные эксперименты с точными подходами позволили найти глобально оптимальные решения для 63 из 67 задач, представленных матрицами с размерами от 5х7 до 50х150. Предложенный эвристический алгоритм позволил найти лучшие результаты для целевой функции производительность группировки (grouping efficiency) в 23 из 24 тестовых примерах.

В диссертационном исследовании рассматривается подход к разработке комплексной модели управления клиентскими кластерами компании сектора розничной торговли, в рамках которой перемещение клиентов между кластерами описывается как стохастический процесс, представляемый в виде марковской цепи. В отличие от предыдущих исследований, в данной работе учитывается динамика изменения ключевых показателей покупательского поведения клиентских кластеров, таких как частота покупок, средний чек, давность покупки и время сотрудничества клиента с компанией. В работе проведен анализ влияния проводимых маркетинговых мероприятий на поведение отдельных клиентских кластеров и определен характер зависимости покупательского поведения кластеров клиентов от проводимых маркетинговых мероприятий компании. Также в работе разработана информационно-логическая модель оптимизациивыбора оптимальной маркетинговой стратегии компании и сформулирована задача оптимизации управления клиентской базой компании, где в качестве критерия оптимального управления выступает максимизация показателя долгосрочной стоимости клиентской базы на заданном горизонте планирования. Предлагаемая динамическая модель управления клиентской базой компании была апробирована на компании сектора розничной торговли на выборке из 181 927 клиентов за период с 10.2007 по 03.2012. Модель оценки динамики изменения показателей покупательского поведения показала высокую точность прогнозирования. Полученное решение задачи оптимизации управления клиентской базой компании позволило значительно увеличить долгосрочную стоимость клиентской базы компании на интервале 12 месяцев

Научная новизна работы определяется полученными в ходе решения задач исследования новыми результатами.   1. Предложены оригинальная математическая модель и метод бикластеризации на основе объектных и признаковых замкнутых множеств, позволяющие сохранить объектно-признаковое описание бикластеров не “потеряв” (в смысле отношения вложения покомпонентного вложения) при этом формальные понятия, построенные по входным данным. Исследованы его полезные свойства, сформулированы и доказаны соответствующие утверждения. Приведена теоретическая оценка сложности алгоритма по времени выполнения и оценен размер выхода. 2. Впервые формально описана связь между бикластерами и ассоциативными правилами. Даны теоретические оценки мер плотности и разреженности бикластеров, получаемых на основе ассоциативных правил. Выявлена эквивалентность определений бикластера в некоторых методах бикластеризации из биоинформатики и АФП. 3. Предложена математическая модель сходства текстовых документов, сформулированная в терминах частых замкнутых множеств признаков и АФП. 4. Предложена математическая модель построения таксономий групп пользователей веб-сайтов на основе решеток формальных понятий. Указаны наилучшие способы отбора релевантных формальных понятий для построения таких таксономий. 5. Предложена математическая модель рекомендательной системы на основе использования морфологической структуры словосочетаний (признакового пространства). Предложена модель рекомендательной системы на основе бикластеризации и  метода ближайшего соседа, а также методика оценки качества результатов таких систем.   Объектом исследования являются модели бикластеризации на основе замкнутых множеств для решения различных задач анализа данных, в которых возможен переход к объектно-признаковому описанию данных.   Предметом исследования являются методы, эффективные алгоритмы и программные средства бикластеризации на основе замкнутых множеств для решения различных задач анализа объектно-признаковых данных.   Цели исследования. 1. Выявление взаимосвязи существующих моделей и методов бикластеризации, построение их классификации и таксономии. 2. Разработка оригинальных моделей, методов и алгоритмов бикластеризации на основе решеток замкнутых множеств. 3. Программная реализация эффективных алгоритмов поиска бикластеров для решения практических задач анализа данных.