Диссертация (1137055), страница 5
Текст из файла (страница 5)
Геометрически, страты можно представлять как параллельныегиперплоскости, ортогональные вектору r и пересекающие его в точках ck. Этигиперплоскости, или, что то же самое, ортогональный вектор r=Xw снанесёнными на него уровнями ck и составляют модель линейной стратификации.Задача состоит в том, чтобы найти такую модель линейной стратификации,которая наилучшим образом аппроксимирует данные, так что объектыгруппируются как можно ближе к гиперплоскостям, а значит, и друг к другувнутри всех страт вдоль оси взвешенного критерия r. Для примера рассмотримданные из таблицы 1.1. Данные содержат топ-10 городов из рейтингастуденческих городов QS Best Student Cities index за 2015 год [42]. Длярассмотрения были взяты два критерия.
Критерий «доступность» отражаетвозможные расходы на обучение и проживание студентов и их семей. Критерий«желательность» дает представление о привлекательности города с точки зрениябезопасности проживания и возможностей. Каждый из критериев являетсякомпозитным и включает в себя целый ряд других метрик. Более подробнее ометодологии получения этих критериев можно узнать на сайте рейтинга [43].25Таблица 1.1.
Топ-10 городов из рейтинга QS Best Student Cities 2105, в разрезекритериев доступность-желательностьГородДоступность ЖелательностьСтратаПариж61.480.12Мельбурн48.891.72Токио62.797.81Сидней44.01001Лондон15.382.83Сингапур56.091.32Монреаль56.891.42Гонконг56.783.82Берлин81.691.61Сеул55.767.73В идеальном случае значения свертки критериев с весами для одногокласса должны совпадать. Значения свертки – это ранги объектов и, такимобразом, объекты из одного класса разделяют общее значение ранга, которыйназовем центром или уровнем страты . Чтобы представить данные в видезаданного числа параллельных гиперплоскостей, будем искать такое направление и разбиение на классы, чтобы ранги т. е.
значения интегрального критерияобъектов группировались как можно ближе к центрам своих страт. На рис. 1.1графически представлены данные из таблицы 1.1 Вектор весовых коэффициентов = (0.27, 0.73) задает направление гиперплоскостей, центры 1 , 2 , 3 задаютвзаимное расположение гиперплоскостей относительно друг друга, а разбиениезадет принадлежность объекта той или иной страте. Для изображенного примерапараметры гиперплоскостей были подобраны таким образом, чтобы исходныеточки имели как можно меньшее отклонение от своих страт. Далее будетсформулирована аппроксимационная задача формирования линейной комбинациикритериев.26C3(9)100C2w=(0.27, 0.73)80C120406080Рисунок 1.1.
Объекты из таблицы 1 и направление, заданное вектором весовыхкоэффициентов = (. , . )1.2.2. Аппроксимационная задача формирования линейной комбинациикритериевЗадача аппроксимации данных моделью линейной стратификации можетбыть сформулирована следующим образом. Даны N объектов, оцененных по Mкритериям, результаты записаны в виде критериальной матрицы = || || оценка -го объекта по -му критерию. Для того чтобы ранжировать варианты,используем взвешенный критерий ri = w1 xi1 + w2 xi2 + ⋯ + wM2 xiM .
Каждыйобъект получен из одного из К непересекающихся классов ∈{1 , 2 , … , }, для которых ищется некоторое общее значение ранга (уровнястраты) ci ∈ {с1 , с2 , … , сK }, причем с1 > с2 > ⋯ > сK . Уравнение отдельной стратыможет быть записано в виде уравнения гиперплоскости 1 1 + 2 2 + ⋯ + = + , где – минимизируемая ошибка. Чтобы найти наилучшееразделение на классы, необходимо подобрать значения , и , для которыхсумма квадратов невязок будет минимальна:272∑ ∑ (∑ − ) →=1 {=1,,(10)∑ = 1, ≥ 0=1Решение сформулированной выше оптимизационной задачи позволяетподобрать оптимальные параметры модели линейных страт. Метод поиска стратна основе подбора оптимальных параметров рассмотренной выше модели будемназывать методом линейной стратификации.1.2.3.
Влияние шкалы критериев на веса в задаче линейноймногокритериальной стратификацииОдним из вырожденных случаев применения модели является случай, когдаодин из признаков принимает конечное число значений, равное числу страт. Втаком случае тривиальным решением будет присвоить нули всем весовымкоэффициентам кроме коэффициента при этом признаке, а значениями центровназначить значения, принимаемые этим признаком.
При этом значение критерияоптимальности стратификации ∑=1 ∑ (∑=1 − )2будет равно 0.Действительно, в таком случае страты представляют собой гиперплоскости,перпендикулярные рассматриваемому критерию, а значения уровней и есть тесамые значения критерия. Так, например, данные в таблице 1.2 могут бытьстратифицированы тремя различными способами, полагая векторы весовравными: 1 = (0, 1), или 2 = (1, 0), или 3 = (0.5, 0.5). Все три набора весовприводят к глобальному минимуму целевой функции со значением 0.
Для того,чтобы выбрать одно из этих решений, можно ввести дополнительное ограничениена веса. По аналогии с 2 -регуляризацией можно требовать, чтобы вектор весовыхкоэффициентов имел наименьшую норму, тогда из трех рассмотренных наборов28весов будет выбран 3 = (0.5, 0.5), норма которого ‖ 3 ‖2 =1√2. Хотя данныйпример может показаться слишком искусственным, и добавление еще хотя быодной точки сделает стратификацию однозначной, но можно предположить, что вслучае высокой размерности данных соизмеримой с числом объектов, такиеситуации все таки будут встречаться довольно часто.
Однако, в диссертационномисследовании вопрос регуляризации весов не рассматривается и остается длябудущей работы.Таблица 1.2. Пример неединственности решения задачи линейной стратификацииK1K21K1+0K2Страт0K1+1K2Страта0.5K1+0.5K2Страта0103120.531012030.531112121202032112202103122121121.511212211.51Также следует отметить, что изменение значений одного критерия длянекоторых объектов может привести к изменению весов на полностьюпротивоположные.
Таблица 1.3 содержит данные шести объектов оцененных подвум критериям K1 и K2, агрегированный критерий полученный методомЛинСтрат получается 0.09K1+0.91K2. В столбце K2’ значения второго критериядля объектов 1, 2, 3 были увеличены, и в этом случае агрегированный критерийполучился 0.90K1+0.10K2’. Веса поменялись на противоположные и при этомобъект 3 перешел из первой страты в 3-ю, хотя ранжирование критериев этомуобъектов осталось неизменным.29Таблица 1.3. Пример изменения весов при увеличении значений критерияОбъект K1K2 K2’ 0.09K1+0.91K2 Страта 0.90K1+0.10K2’ Страта101800.9137.793202901.8228.7733031002.7319.743410000.9039.033520001.82218.052630002.73127.0811.2.4.
Отличие линейной стратификации от задачи кластер анализаЗадача стратификации напоминает задачу кластер анализа. И в том и в этомслучае ищется разбиение множества объектов на подмножества. Существенноеразличие заключается в том, что кластеры формируются как компактныеобразования вокруг своих «центроидов», тогда как страты – это гиперплоскости.В отличие от кластеров в страту могут попадать объекты далекие друг от друга иот центроидов. То есть страты образуют слои сколь угодно вытянутые вдользаданного направления.
И кроме того страты, в отличие от кластеров, можноупорядочить по значениям уровней страт. На рисунке 1.2 продемонстрированоразличие кластеров и страт. Для примера взяты данные из таблицы 1.1, нарисунке 1.2 слева кластеры получены применением алгоритма к-средних, истраты методом линейной стратификации справа.3010010080802040608020406080Рисунок 1.2.
Кластеры полученные методом к-средних (слева), линейные страты(справа)1.2.5. Отличие линейной стратификации от упорядочения по главнойкомпонентеОдним из самых популярных подходов поиска весов критериев для сверткив агрегированный критерий является метод главных компонент (МГК) [44, 45].Подход с линейными стратами кажется похожим на подход метода главныхкомпонент, потому что главная компонента как бы задает направление,«ортогональное» искомым гиперплоскостям. Остановимся более подробно насравнении этих двух методов и продемонстрируем на примере как могутразличаться решения полученные этими методами. Критерий метода главныхкомпонент (для случая одной компоненты) выглядит следующим образом:∑ ∑( − )2=1 =1(11)31По методу линейной стратификации минимизируется критерий:∑ ∑( − )2(12)=1 =1Таким образом, в методе главных компонент аппроксимируются исходныекритерии (11), а в методе линейной стратификации – агрегированный критерий(12).
Кроме того, в методе линейных страт принимает значения из конечногомножества ci ∈ {с1 , с2 , … , сK }.Рассмотрим пример, демонстрирующий различие между методом главныхкомпонент и линейной стратификацией. Данные примера приведены в таблице1.4.Таблица 1.4. Множество объектов для примера сравнения ЛинСтрат и МГКОбъектКритерий 1Критерий 2ЛинСтратМГКС1200.671.54С2010.670.23B1602.004.63B250.52.003.97B331.52.002.66B412.52.001.34A1422.673.54A2232.672.23На рисунке 1.3 продемонстрированы различия в весовых коэффициентаполученных методом главных компонент и линейной стратификации. Визображенном примере оказывается, что точки в точности ложатся на три страты,если взять весовые коэффициент = (0.48, 0.52).
В тоже время веса,вычисленные по методу главных компонент и нормированные на сумму значений,получаются = (0.77, 0.23), при этом доля ошибки в общем разбросе составляет13.4%. Стоит отметить, что для расчета главных компонент и вычисления ошибки32использовался метод главных компонент без центрирования данных на основесингулярного разложения описанный в [46]. Значения агрегированных критериевприведены в таблице 1.4.
Кроме того, методы дают разные ранжирования, такнапример объекты B1 и B2 по методу главных компонент получают ранги вышечем два объекта из первой страты A1, A2.432100123456Рисунок 1.3. Примеры решений методом главных компонент и методом линейнойстратификацииНа рисунке 1.4 и в таблице 1.5 показан другой пример, когда метод главныхкомпонент и метод линейной стратификации дают схожие и различныерезультаты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
