Автореферат (Разработка модели и метода линейной многокритериальной стратификации), страница 2

Даны N объектов, оцененных по M критериям, результаты записаны ввиде критериальной матрицы = || || – оценка -го объекта по -му критерию.Для того чтобы ранжировать варианты, используем взвешенный критерий ri =w1 xi1 + w2 xi2 + ⋯ + wM2 xiM . Каждый объект получен из одного из Кнепересекающихся классов ∈ {1 , 2 , … , }, для которых ищется некотороеобщее значение ранга (уровня страты) ci ∈ {с1 , с2 , … , сK }, причем с1 > с2 > ⋯ > сK .Уравнениеотдельнойстратыможетбытьзаписановвидеуравнениягиперплоскости 1 1 + 2 2 + ⋯ + = + , где – минимизируемаяошибка. Чтобы найти наилучшее разделение на классы, необходимо подобратьзначения , и , для которых сумма квадратов невязок будет минимальна:2∑ ∑ (∑ − ) →=1 {,,=1(1)∑ = 1, ≥ 0=1Решение этой оптимизационной задачи позволяет подобрать оптимальныепараметры модели линейных страт.

Метод поиска страт на основе подбораоптимальных параметров рассмотренной выше модели будем называть методомлинейной стратификации.Далее рассматриваются вопросы влияния шкалы критериев на решениезадачилинейнойстратификации.Приводится9случай,когдарешениеоптимизационной задачи не единственно и предлагается возможный способ«стабилизации» решения путем добавления регуляризатора к целевой функции.В завершении главы подчеркивается отличие между упорядочиваниемметодом линейной стратификации и популярным подходом с использованиемглавной компоненты. На первый взгляд, подход с линейными стратами кажетсяпохожим на подход метода главных компонент, потому что главная компонента какбы задает направление, «ортогональное» искомым гиперплоскостям. Однако привзгляде на математические формулировки критерия метода главных компонент:∑ ∑( − )2(2)=1 =1и критерия оптимальной стратификации:(3)∑ ∑( − )2=1 =1сразу же становится ясным существенное отличие – в методе главных компонентаппроксимируются исходные критерии (2), а в методе линейной стратификацииагрегированный критерий (3).В главе 2 предлагается алгоритм оптимизации целевой функциимногокритериальнойлинейнойстратификациинаосноверешениязадачиквадратичного программирования (1).Разрабатываютсяалгоритмыоптимизациикритериялинейнойстратификации.

Первый из предложенных алгоритмов использует принципэволюционнойоптимизации,восновепрограммирование.10второголежитквадратичноеОсновным результатом, описанным во второй главе, является алгоритмрешениязадачилинейнойстратификациинаосновеквадратичногопрограммирования. Для описания этого алгоритма введем обозначение для матрицыразбиения , элементы которой = 1, при ∈ , причем = 0, ≠ .Перепишем теперь (1) в матричном виде:‖ − ‖2 → { = 1 ≥ 0(4)Решая оптимизационную задачу относительно переменной , получаем =( )−1 .

Далее подставим значение в − . Получим −( )−1 = ( − ( )−1 ). Перепишем задачу (4):‖( − ( )−1 )‖2 → { = 1 ≥ 0(5)Алгоритм ЛинСтрат (на основе квадратичного программирования).На входе:- Объекты , = 1 … .- Число страт .На выходе:- Веса .- Центры страт .- Разбиение .Алгоритм:1. Инициализировать веса w и центры страт . Cгенерировать веса wслучайно такие, что ≥ 0, = 1 … и ∑=1 = 1. Вычислить свертку критериев с11весами. Центры страт сгенерировать случайно равномерно из диапазона отминимального значения свертки критериев до максимального.2. По заданным весам и центрам найти оптимальное разбиение:2 ∈ , где = (∑ − ) , = 1 … , = 1.

. .=13.Призаданномразбиении решитьоптимизационнуюзадачуотносительно весов :‖( − ( )−1 )‖2 → { = 1 ≥ 04. Вычислить центры страт = ( )−1 .5. Сравнить новое значение целевой функции со значением, полученным напредыдущем шаге. Завершить, когда значение перестанет меняться.Для верификации предлагаемого алгоритма и его сравнения с другимиметодами стратификации мы решили использовать как искусственные, так иреальные данные – по аналогии со сравнительными исследованиями алгоритмовкластер-анализа.Геометрия страт задается различными параметрами, к которым относятся:весовые коэффициенты w, уровни страт c, интенсивности страт θ, размах страт φ итолщина страт σ.

Различные вариации параметров представлены наглядно нарисунке 1.12Рисунок 1. Линейные страты для различных комбинаций параметров генерации в двумерномслучае M=2. Приведены следующие варианты: (1) страты в зависимости от ориентации w (a) w =(0.5, 0.5), (б) w = (0.8, 0.2), (в) w = (0.2 ,0.8); (2) страты в зависимости от толщины (г) σ=0.05,(д),σ=0.1 (е), σ=0.2; (3) страты в зависимости от интенсивности (ж) θ=(0.5, 0.3, 0.2) (з) θ=(0.7, 0.2, 0.1)(и) θ=(0.8, 0.15, 0.05); (4) страты в зависимости от размаха (к) φ=0.05,(л) φ=0. 1,(м) φ=0.5Ниже, в таблице 1, приводятся два разработанных нами алгоритмастратификации, а также методы, рассмотренные в главе 1 диссертационной работыи отобранные для экспериментального сравнения.13Таблица 1.

Список методов стратификации и их обозначений, используемых вдиссертацииМетод стратификацииАббревиатураРаздел диссертацииМетод линейной стратификацииLinstrat с использованиемLSQ2.1.2квадратичногопрограммированияМетод линейной стратификацииLinstrat на основе эволюционнойLS2.1.1минимизацииСтратификация с помощьюBC1.1.3правила Борда (Borda count)Метод ABC- классификации наоснове линейной оптимизацииLWO1.1.6весов (Linear weightsoptimization)Ранжирование по влияниюAR1.1.1(Authority ranking)Стратификация объединениемPS1.1.2границ Парето (Paretostrat)Дляоценкикачествастратификациинасинтетическихданныхиспользовалась точность восстановления стратификации.Алгоритм был верифицирован на стратах, сгенерированных со случайнымивесовыми коэффициентами, таким образом, проверяется способность алгоритмавосстанавливать параметры модели, по которой были сгенерированных страты.Далее исследуется точность стратификации в зависимости от геометрическойконфигурации страт.

Оказывается, что предложенный алгоритм приводит кнаилучшим решениям в большинстве рассмотренных случаев. Исключениемявляется случай «толстых» страт (см. рисунок 1(е)), однако это лишь подтверждаетправильность работы алгоритма линейной стратификации, поскольку алгоритмподбирает оптимальные параметры для модели, в которой страты образуют«тонкие» слои.14Алгоритм был верифицирован на реальных данных, полученных с порталаhttp://www.scimagojr.com. Для этого были взяты библиометрические показателинаучных журналов за 2012 год из раздела Artificial Intelligence. Всего 118 журналов,оцененные по трем библиометрическим показателям:1) Индекс SJR (Scientific Journal Ranking).2) Индекс Хирша (H).3) Импакт-фактор журнала (I).Также были взяты данные о публикационной активности 102 стран за 2012год, в предметной области – искусственный интеллект (Artificial intelligence).Критерии, используемые для оценки стран, следующие:1) Общее число документов, опубликованных за 2012.2) Число цитируемых документов, опубликованных в 2012 году.3) Общее количество цитирований 2012 году.4) Самоцитирование.5) Среднее число цитирований в 2012 году.6) H-индекс.К реальным данным применялись два основных типа нормировки: изстатистики (z-скоринг) и теории принятия решений (мин-макс).На реальных данных качество стратификации оценивается традиционнымкритерием степени согласованности полученного ранжирования с ранжированиямипо отдельно взятым критериям (нормированное расстояние Кемени-Снелла).Применение алгоритма к реальным данным приводит к достаточно хорошоинтерпретируемым и адекватным результатам.

В случае журналов в первую стратувошли высоко ценимые в научном сообществе журналы, в случае стран первуюстрату составили страны, вносящие наибольший вклад в мировую публикационнуюактивность. Кроме того, предлагаемый метод линейной стратификаций в обоихслучаях приводит к ранжированию, наиболее согласованному с отдельно взятымикритериями по сравнению с остальными методами, см. таблицы 2, 3.15Таблица 2. Средние значения расстояний Кемени-Снелла между стратификациямижурналов по отдельным критериям и стратификациями, найденными методамимногокритериальной стратификацииМетодLSQLSBCLWOARPSСреднее расстояние.0.1198 0.1198 0.1714 0.1317 0.1194 0.2340(Стандартная нормировка)Среднее расстояние.(Статистическая0.1199 0.1185 0.1714 0.1486 0.2024 0.2340нормировка)Таблица 3.

Средние значения расстояний Кемени-Снелла между стратификациямистран по отдельным критериям и стратификациями, найденными методамимногокритериальной стратификацииМетодLSQLSBCLWO ARPSСреднее расстояние.0.1036 0.1036 0.2607 0.2145 0.1629 0.1765Стандартная нормировкаСреднее расстояние.0.1036 0.1036 0.2607 0.1659 0.1172 0.1765Статистическая нормировкаВ разделе 2.5 описанырезультаты примененияметода линейнойстратификации для решения проблемы приоритизации базовых станций (БС) в сетисотовой связи на примере компании ПАО «МТС». Применение разработанного вдиссертации метода позволяет:- обосновать выбор весов и разбиение множества БС на группы поприоритету;- сформировать более однородные группы в разрезе показателейфункционирования БС;-получитьэкономическийэффектзасчетснижениячиславысокоприоритетных БС и сокращения капитальных затрат.В главе 3 метод ЛинСтрат применяется для анализа актуальнойпроблематики оценки научного вклада ученого.

Среди рассмотренных показателей,прежде всего, характеристики уровня цитируемости и авторитетности научногоработника.Кроме того, рассматривается способ оценки уровня научных16результатов, основанный на использовании таксономии предметной области, то естьиерархии её понятий. Уровень результатов при таком подходе оценивается всоответствии с таксономическими рангами тех понятий, которые возникли или былисущественно преобразованы благодаря этим результатам.Подход, рассматриваемый в диссертации, выходит за рамки традиционногоспособа оценки научного вклада по публикационным показателям. Деятельностьученого рассматривается в разрезе следующих аспектов: (а) таксономический ранг,(б) цитируемость, и (в) авторитетность (по другим значимым аспектам деятельностиученого не удается собрать информация).Таксономический ранг ученого определяется рангами понятий, которыевозникли или были существенно преобразованы благодаря этому ученому.Рассмотрим в качестве примера таксономию, изображенную на рисунке 2.Допустим, что работы ученого серьезно повлияли на таксон, отмеченный A.1.2,тогда его таксономический ранг будет равен 3.DomainRank 1ARank 2Rank 3A.1.1.1BA.1A.2A.1.1A.1.1.2A.1.2A.1.1.3A.1.2.1B.1A.2.1A.1.2.2Рисунок 2.

Пример таксономии предметной области и таксономическогоранга17Однако у одного ученого могут быть результаты, отображаемые сразу нанесколько таксонов, причем разного уровня. В таком случае самый высокий уровеньрезультата выбирается в качестве базового ранга, и его значение уменьшается (чемменьше, тем лучше) на число, пропорциональное числу работ на затронутом уровнетаксономии, умноженному на некоторый коэффициент, соответствующий данномууровню.

Естественно считать, что вклад следующего, более низкого, уровня долженбыть меньше на порядок, таким образом, коэффициент для наивысшего уровняможно взять порядка 0.1, для следующего 0.01 и так далее. Например, еслирезультаты некоторого ученого существенно затрагивают 4 таксона уровня 4 и тритаксона уровня 3, то базовый ранг будет равен 3; при этом 3 работы на уровне триуменьшат значение ранга на 3*0.1=0.3 и 4 работы на 4 уровне еще уменьшат его на4*0.01.