Formalization of the Problem and Development of an Algorithm for Selecting a Data Normalization Method for Decision Making Support

Full Text

Введение

Принятие решений – важнейший процесс в различных сферах человеческой деятельности – от технологического обслуживания токарных станков [1], проектирования сети общеобразовательных школ [2], развития сети газовых заправочных станций [3], управления качеством функционирования структурных элементов в организационно-технических системах [4] до производства катализаторов для синтеза углеродных нанотрубок [5]. Для повышения эффективности результатов принятия решений необходимо постоянное исследование вопросов, возникающих при реализации данного процесса, в целях их преодоления.

Одной из ключевых проблем в процессе принятия решений является выбор подходящего метода нормализации данных. Нормализация используется для преобразования данных в стандартный формат для устранения шумов и разнородности размерностей, что обеспечивает сопоставимость данных и возможность их последующего анализа. Для ее реализации применяются такие методы, как линейная нормализация по Вейтендорфу, векторная, логарифмическая и пр. [6] Матрица решений, полученная после применения различных методов нормализации, расчетные формулы которых отличаются, будет оказывать первостепенное влияние на результат принятого решения.

В ряде работ проведены исследования по применению методов нормализации данных. Так, например, в работе [7] приводится анализ влияния линейной нормализации по Вейтендорфу на решение многокритериальных экономических задач при помощи максиминных критериев, в ходе которого установлена невозможность использования данного метода из-за неустойчивости к изменениям ограничений. Применение метода нормализации, обеспечивающего представление гиперпространства частных критериев близким к единичному гиперкубу, описывается в работе [8]. Выбор метода нормализации путем оценки значения функции расстояния между данными рассматривается в работе [9]. Использование метода нормализации, который обеспечивает данным равную важность с точки зрения их изменчивости, предлагается в работе [10]. Однако отсутствует формализованный единый подход к выбору метода нормализации не только от имеющихся данных в матрице решений, но и от применяемого метода выбора лучшей альтернативы (решения задачи многокритериальной оптимизации), что обуславливает актуальность приведенного исследования.

Цель работы – формализация задачи и разработка алгоритма выбора метода нормализации данных для принятия решений.

Формализация задачи выбора метода нормализации данных

Для формализации задачи выбора метода нормализации данных воспользуемся методологией IDEF0, позволяющей привести системно-структурное описание данного процесса [11]. Вначале при помощи методологии IDEF0 рассмотрим сам процесс принятия решений, декомпозиция контекстной диаграммы которого показана на рис. 1.

Рис. 1. Декомпозиция контекстной IDEF0-диаграммы процесса принятия решений

В таком случае процесс принятия решений предполагает три основных процесса: A1 – нормализация данных; А2 – расчет весовых коэффициентов значимости критериев; А3 – выбор лучшей альтернативы. Механизмом для всех процессов A1 – A3 является лицо, принимающее решение. Процесс ограничен методами принятия решений, которые можно разделить на три категории: методы нормализации (для А1), методы расчета весовых коэффициентов значимости критериев (для А2) и методы выбора лучшей альтернативы (для А3).

Входная информация для процесса А1 включает в себя матрицу решения и типы критериев, в то время как выходной информацией является нормализованная матрица решений. Для процесса А2 входная информация – нормализованная матрица решений и типы критериев, а выходная – весовые коэффициенты значимости критериев. Для процесса А3 входная информация содержит нормализованную матрицу решений, типы критериев и весовые коэффициенты значимости критериев, а в качестве выходной информации выступает лучшая альтернатива.

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

Для описания предлагаемой реализации процесса А1 воспользуемся его декомпозицией. На рисунке 2 показана декомпозиция диаграммы процесса нормализации данных по методологии IDEF0.

Рис. 2. Декомпозиция IDEF0-диаграммы процесса нормализации данных

Процесс А1 состоит из пяти подпроцессов: А1.1 – создание матрицы с вариантами значений весовых коэффициентов значимости критериев; А1.2 – нормализация данных; А1.3 – расчет матриц лучших альтернатив и частот их появления; А1.4 – расчет весовых коэффициентов значимости методов нормализации данных; А1.5 – выбор метода нормализации данных. Общей выходной информацией для всех подпроцессов А1.1 – А1.5 является длительность расчета.

Подпроцесс А1.1 основывается на начальных значениях весовых коэффициентов значимости критериев, а выходной информацией выступает матрица с вариантами весов. Комбинаторные алгоритмы используются в качестве механизма для данного подпроцесса.

Подпроцесс А1.2 принимает в качестве входной информации матрицу решений с типами критериев и формирует нормализованные матрицы решений, полученные при помощи методов нормализации, являющихся механизмом.

Подпроцесс А1.3 использует нормализованные матрицы решений, матрицу с вариантами весовых коэффициентов значимости критериев и типы критериев для расчета матриц лучших альтернатив и частот их появления. Механизмом являются методы выбора лучшей альтернативы.

Подпроцесса А1.4 на основе матрицы частот появления лучших альтернатив (входная информация) формирует весовые коэффициенты значимости методов нормализации данных (выходная информация).

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

Разработка алгоритма выбора метода нормализации данных

Сформулируем математическую постановку данной задачи следующим образом: для заданной матрицы решений S необходимо использовать такой метод нормализации M_t* и ему соответствующую матрицу решений ${\overline{S}}_{t*}=M_{t*}\left(S\right)$, которые для метода выбора лучшей альтернативы G(${\overline{S}}_{t*}$, ω) обеспечивают получение наиболее часто встречаемой лучшей альтернативы при различных B сочетаниях значений весовых коэффициентов значимости критериев ω, то есть:

$t*=\underset{t=\mathrm{1,...,}T}{\mathrm{argmax}}{\gamma }_t=\underset{t=\mathrm{1,...,}T}{\mathrm{argmax}}\frac{{\displaystyle \sum _{b=1}^B{\nu }_{b,t}}}{{\displaystyle \sum _{b=1}^B\sum _{t=1}^T{\nu }_{b,t}}}$, (1)

где γ_t – весовой коэффициент значимости t-го метода нормализации; T – число методов нормализации; ν_b,t – частота появления лучшей альтернативы при b-м сочетании весовых коэффициентов значимости критериев в t-м методе нормализации.

Рассмотрим алгоритм решения задачи (1). Первым шагом является создание матрицы с B вариантами значений весовых коэффициентов значимости критериев ω. Это делается с помощью комбинаторных алгоритмов, которые позволяют перебрать все возможные комбинации весовых коэффициентов для каждого критерия. Затем происходит нормализация данных ${\overline{S}}_t$ с использованием различных методов M_t. После этого посредством соответствующего метода выбора G(${\overline{S}}_{t*}$, ω) проводится расчет матриц лучших альтернатив и частот их появления ν_b,t путем подсчета количества раз, когда каждая альтернатива была выбрана как лучшая. Далее происходит расчет весовых коэффициентов значимости методов нормализации данных γ_t. Такие коэффициенты отражают выбор наиболее часто встречаемой лучшей альтернативы. Таким образом, метод с наибольшим весовым коэффициентом будет считаться наиболее предпочтительным для нормализации данных. Если требуемая точность расчета ε коэффициента значимости метода нормализации не достигнута, то значения весовых коэффициентов значимости критериев ω могут быть изменены и процесс повторяется снова до ее достижения.

Вычислительный эксперимент

Реализацию предлагаемого подхода к выбору метода нормализации данных рассмотрим на примере задачи принятия решения по определению лучших параметров (концентрации веществ в электролите С_i,1, С_i,2, …, температуры t_i, кислотности pH, плотности тока j_i, длительности процесса T_i) для гальванического процесса среди возможных альтернатив A_i (i = 1, …, m), которые обеспечивают оптимальные значения m критериев качества получаемого покрытия (K₁ – толщина, мкм; K₂ – микротвердость, кг/мм²; K₃ – шероховатости, мкм; K₄ – удельное сопротивление, Ом/м; K₅ – коэффициент отражения, %; K₆ – адгезия, Н/м²; K₇ – пористость, см^–2; K₈ – коррозионная стойкость, %; K₉ – износ, г/с). Критерии K₁, K₂, K₅, K₆ и K₈ имеют тип максимизации, а K₃, K₄, K₇ и K₉ – минимизации.

Для гальванического процесса нанесения цинкового покрытия значения альтернатив по критериям из матрицы решений, по которой проводится выбор, показаны на рис. 3.

Рис. 3. Значения альтернатив A₁ – А₂₄ по критериям K₁ – K₉ (соответственно а – и)

Пусть в качестве метода выбора лучшей альтернативы выступает взвешенный аддитивный критерий качества. В таком случае, математическая постановка задачи принятия решений будет звучать следующим образом: выбрать альтернативу A_i*, которая максимизирует взвешенный аддитивный критерий качества:

$i*=\underset{i=\mathrm{1,...,}m}{\mathrm{argmax}}{G}_i\left(S_{t*},\omega \right)=\underset{i=\mathrm{1,...,}m}{\mathrm{argmax}}\sum _{j=1}^{n=9}{\omega }_j{\overline{K}}_{i,j}^{t*}$, (2)

где ω_j –весовой коэффициент значимости j-го критерия;  – нормализованное с использованием t*-го метода значение j-го критерия по i-й альтернативе.

Определение весовых коэффициентов значимости критериев ω_j в (2) проводится по методу из [12]. Данный метод предполагает формирование матрицы весовых коэффициентов (с использованием количественных подходов), которой сопоставляется матрица рангов (качественный подход). Для получения заданного значения согласованности с помощью матрицы рангов решается задача бинарной оптимизации. Согласованность результатов (найденных ранговых значений весовых коэффициентов) оценивается с помощью коэффициента Кендалла W при заданном уровне значимости a. Расчет весовых коэффициентов значимости критериев ω_j выполнялся для согласованности W = 0,9 при заданном уровне значимости a = 0,05 при помощи разработанного программного обеспечения [13].

В качестве методов нормализации значений j-го критерия по i-й альтернативе в (1) использовались [14]: линейный по Вейтендорфу M₁; max-линейный M₂; линейный по сумме M₃; векторный M₄; логарифмический M₅; min-max-линейный M₆; min-max-нелинейный M₇; улучшенной точности M₈; Завадскаса и Турского M₉. Выбор метода нормализации данных по предлагаемому подходу проводился при помощи разработанного программного обеспечения [15]. Расчет коэффициентов значимости γ₁ – γ₉ для методов M₁ – M₉ выполнялся для точности ε = 0,001 при начальных весовых коэффициентах значимости критериев ω от 0 до 1 с шагом 0,2.

Анализ полученных результатов и их обсуждение

Рассчитанные весовые коэффициенты значимости критериев K₁ – K₉ показаны на рис. 4, а. Наибольшую значимость (0,193) имеет критерий K₄, а наименьшую (0,029) – K₆. Данные коэффициенты обладают согласованностью по коэффициенту Кендалла W_расч = 0,911 при полученном уровне значимости a_расч = 0,005 с расчетной величиной 21,87 критерия χ-квадрат, превышающей табличное значение 15,5. Весовые коэффициенты значимости методов нормализации приведены на рис. 4, б.

Рис. 4. Весовые коэффициенты значимости критериев (а) и методов нормализации (б)

Наибольшую значимость (0,134) имеют два метода нормализации – M₂ и M₆. Данные коэффициенты получены на 2-й итерации при весовых коэффициентах значимости критериев от 0 до 1 с шагом 0,05. Для методов M₂ и M₆ нормализованные матрицы решений (см. рис. 3) показаны на рис. 5.

Рис. 5. Нормализованные матрицы решений по методам M₂ (а) и M₆ (б)

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

Рис. 6. Взвешенный аддитивный критерий качества, рассчитанный с использованием нормализованных матриц решений по методам M₂ (а) и M₆ (б)

Наибольшее значение аддитивного критерия в обоих случаях имеет альтернатива A₁₀, которая предполагает использование для гальванического процесса нанесения цинкового покрытия следующих параметров: концентрации цинка C_10,1 = 10 г/л и гидроксида натрия C_10,2 = 110 г/л; температура t₁₀ = 25 °С; кислотность pH₁₀ = 4,2; плотность тока j₁₀ = 1 А/дм²; длительность процесса T₁₀ = 60 мин. Таким образом, совпадение лучшей альтернативы свидетельствует о надежности и достоверности применения выбранных методов нормализации (M₂ или M₆) в контексте решения задачи (2) для имеющейся матрицы решений.

Заключение

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

About the authors

D. S. Solovyev

Author for correspondence.
Email: solovjevdenis@mail.ru

кандидат технических наук, доцент кафедры «Математическое моделирование и информационные технологии»

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. 1. Decomposition of the contextual IDEF0 diagram of the decision-making process

Download (150KB)

Indexing metadata

3. Fig. 2. Decomposition of the IDEF0 diagram of data normalisation process

Download (294KB)

Indexing metadata

4. Fig. 3. Values of alternatives A1 - A24 according to criteria K1 - K9 (a - i, respectively)

Download (304KB)

Indexing metadata

5. Fig. 4. Weighting coefficients of significance of criteria (a) and normalisation methods (b)

Download (50KB)

Indexing metadata

6. Fig. 5. Normalised decision matrices by methods M2 (a) and M6 (b)

Download (67KB)

Indexing metadata

7. Fig. 6. Weighted additive quality criterion calculated using normalised decision matrices using M2 (a) and M6 (b) methods

Download (70KB)

Indexing metadata