Оценка эффективности природоохранных программ (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Полностью удалено содержимое страницы)
 
(7 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
Описан способ построения интегральных индикаторов качества объектов с использованием экспертных оценок и измеряемых данных. Каждый объект описан набором признаков в линейных шкалах. Используются экспертные оценки качества объектов и важности признаков, которые корректируются в процессе вычисления. Предполагается, что оценки выставлены в ранговых шкалах. Рассматривается задача получения таких интегральных индикаторов, которые не противоречили бы экспертным оценкам. Предложено два алгоритма уточнения экспертных оценок.
 +
{{tip|Полный текст этой статьи находится [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Kuznetsov2010Nature/doc/Kuznetsov10Estimation.pdf здесь].}}
 +
== Постановка задачи ==
 +
Интегральный индикатор - линейная комбинация вида
 +
<tex>\mathbf{q} = A\mathbf{w},</tex> где <tex> A = \{a_{ij}\}_{i=1,j=1}^{n,m}</tex> - матрица объекты-признаки, <tex> \mathbf{w} </tex> - вектор весов признаков. Заданы в ранговых шкалах экспертные оценки: <tex> \mathbf{q_0}, \mathbf{w_0}</tex>, допускающие произвольные монотонные преобразования. Пусть на наборах экспертных оценок
 +
введено отношение порядка такое, что
 +
<tex>q_1\geq q_2 \geq ... \geq q_n \geq 0;\ w_1\geq w_2\geq ... \geq w_n \geq 0.</tex> Множество всех таких векторов задается системой линейных неравенств <tex>J\mathbf{q}\geq 0,</tex> где
 +
<tex>\underset{n\times n}J =
 +
\left(
 +
\begin{array}{rrrrrr}
 +
1 & -1 & 0 & \cdots & 0 & 0 \\
 +
0 & 1 & -1 & \cdots & 0 & 0 \\
 +
\vdots & \vdots & \vdots &\ddots & \vdots & \vdots\\
 +
0 & 0 & 0 & \cdots & 1 & -1 \\
 +
0 & 0 & 0 & \cdots & 0 & 1 \\
 +
\end{array}
 +
\right).
 +
</tex>
 +
Таким образом, заданным <tex> \mathbf{q}, \mathbf{w}</tex> можно поставить в соответствие матрицы <tex>J_q</tex> и <tex>J_w</tex> размеров соответственно <tex>n\times n</tex>
 +
и <tex>m\times m</tex>.
 +
Определим <tex>\mathcal{Q}</tex> — конус, задаваемый
 +
матрицей <tex>J_q</tex> в пространстве интегральных индикаторов; <tex>\mathcal{W}</tex> — конус, задаваемый матрицей <tex>J_w</tex> в пространстве весов признаков.
 +
ЗАДАЧА 1. Требуется найти в конусах <tex>\mathcal{W}</tex> и <tex> \mathcal{Q} </tex> векторы <tex> \mathbf{p} </tex> и <tex>\mathbf{q}</tex>, такие, что:
 +
 +
<tex>
 +
\begin{equation}
 +
\min\limits_{\mathbf{p},\mathbf{q}}||\mathbf{q}-A\mathbf{p}||:\ \mathbf{q} \in \mathcal{Q}, \mathbf{p} \in \mathcal{W}, ||\mathbf{q}|| = 1, ||\mathbf{p}|| = 1,
 +
\end{equation}
 +
</tex>
 +
 +
где <tex>||.||</tex> --- евклидова метрика в пространстве <tex>\mathbb{R}^n</tex>.
 +
 +
ЗАДАЧА 2. Найти вектор весов, который максимизирует коэффициент
 +
корреляции между интегральными индикаторами:
 +
 +
<tex>\mathbf{w_1} = \arg \underset{\mathbf{w} \in \mathcal{W}}{max} C(\mathbf{q_0}, A\mathbf{w}),</tex>
 +
 +
по этому вектору весов построить уточненный интегральный индикатор
 +
 +
<tex>\mathbf{q_1} = A\mathbf{w_1}.</tex>
 +
 +
Здесь <tex> C </tex> - коэффициент ранговой корреляции Спирмена.
 +
 +
== Пути решения задач ==
 +
 +
РЕШЕНИЕ ЗАДАЧИ 1.
 +
 +
Построим итерационный алгоритм, последовательно находящий приближения векторов <tex>q^{(2k)}, p^{(2k+1)}</tex> на четном и нечетном шаге. Векторы <tex>\mathbf{x}=q^{(2k)}</tex> и <tex>\mathbf{y}=p^{(2k+1)}</tex> будем считать решениями двух последовательно решаемых
 +
оптимизационных задач, полагая вектор <tex>p^{(0)}=w_0</tex> на шаге <tex>k=0</tex>.
 +
 +
Задача 2k:
 +
 +
minimize <tex>|| \mathbf{x}- Ap^{(2k)}||</tex>
 +
 +
subject to <tex>\mathbf{x}^T\mathbf{x} = 1, J_n \mathbf{x} \geq 0. </tex>
 +
 +
Задача 2k+1:
 +
 +
minimize <tex>||q^{(2k+1)}-A\mathbf{y}||</tex>
 +
 +
subject to <tex>\mathbf{y}^TA^TA\mathbf{y} = 1, J_m \mathbf{y} \geq 0. </tex>
 +
 +
При решении задач, на каждом шаге значения констант <tex>p^{(2k)}</tex> и <tex>q^{(2k+1)}</tex>. при-
 +
нимаются равными значениям соответствующих решений <tex>x</tex> и <tex>y</tex> предыдущего шага.
 +
 +
РЕШЕНИЕ ЗАДАЧИ 2.
 +
 +
Поскольку в условии задачи 2 фигурируют ранги, нельзя решать эту задачу стандартными методами выпуклой оптимизации. Предлагается использовать стандартный генетический алгоритм.
 +
 +
== Смотри также ==
 +
 +
* [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Kuznetsov2010Nature/doc/ Ссылка на текст статьи]
 +
* [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Kuznetsov2010Nature/code/ Ссылка на код]
 +
 +
{{ЗаданиеВыполнено|Михаил Кузнецов|В.В.Стрижов|24 декабря 2010|Ivanov|Strijov}}
 +
[[Категория:Практика и вычислительные эксперименты]]

Текущая версия

Описан способ построения интегральных индикаторов качества объектов с использованием экспертных оценок и измеряемых данных. Каждый объект описан набором признаков в линейных шкалах. Используются экспертные оценки качества объектов и важности признаков, которые корректируются в процессе вычисления. Предполагается, что оценки выставлены в ранговых шкалах. Рассматривается задача получения таких интегральных индикаторов, которые не противоречили бы экспертным оценкам. Предложено два алгоритма уточнения экспертных оценок.

Полный текст этой статьи находится здесь.


Постановка задачи

Интегральный индикатор - линейная комбинация вида \mathbf{q} = A\mathbf{w}, где A = \{a_{ij}\}_{i=1,j=1}^{n,m} - матрица объекты-признаки, \mathbf{w} - вектор весов признаков. Заданы в ранговых шкалах экспертные оценки: \mathbf{q_0}, \mathbf{w_0}, допускающие произвольные монотонные преобразования. Пусть на наборах экспертных оценок введено отношение порядка такое, что q_1\geq q_2 \geq ... \geq q_n \geq 0;\ w_1\geq w_2\geq ... \geq w_n \geq 0. Множество всех таких векторов задается системой линейных неравенств J\mathbf{q}\geq 0, где \underset{n\times n}J = \left( \begin{array}{rrrrrr} 1 & -1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & -1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots &\ddots & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & -1 \\ 0 & 0 & 0 & \cdots & 0 & 1 \\ \end{array} \right). Таким образом, заданным \mathbf{q}, \mathbf{w} можно поставить в соответствие матрицы J_q и J_w размеров соответственно n\times n и m\times m. Определим \mathcal{Q} — конус, задаваемый матрицей J_q в пространстве интегральных индикаторов; \mathcal{W} — конус, задаваемый матрицей J_w в пространстве весов признаков.

ЗАДАЧА 1. Требуется найти в конусах \mathcal{W} и \mathcal{Q} векторы \mathbf{p} и \mathbf{q}, такие, что:

\begin{equation} \min\limits_{\mathbf{p},\mathbf{q}}||\mathbf{q}-A\mathbf{p}||:\ \mathbf{q} \in \mathcal{Q}, \mathbf{p} \in \mathcal{W}, ||\mathbf{q}|| = 1, ||\mathbf{p}|| = 1, \end{equation}

где ||.|| --- евклидова метрика в пространстве \mathbb{R}^n.

ЗАДАЧА 2. Найти вектор весов, который максимизирует коэффициент корреляции между интегральными индикаторами:

\mathbf{w_1} = \arg \underset{\mathbf{w} \in \mathcal{W}}{max} C(\mathbf{q_0}, A\mathbf{w}),

по этому вектору весов построить уточненный интегральный индикатор

\mathbf{q_1} = A\mathbf{w_1}.

Здесь C - коэффициент ранговой корреляции Спирмена.

Пути решения задач

РЕШЕНИЕ ЗАДАЧИ 1.

Построим итерационный алгоритм, последовательно находящий приближения векторов q^{(2k)}, p^{(2k+1)} на четном и нечетном шаге. Векторы \mathbf{x}=q^{(2k)} и \mathbf{y}=p^{(2k+1)} будем считать решениями двух последовательно решаемых оптимизационных задач, полагая вектор p^{(0)}=w_0 на шаге k=0.

Задача 2k: 

minimize    || \mathbf{x}- Ap^{(2k)}||  
     
subject to \mathbf{x}^T\mathbf{x} = 1,  J_n \mathbf{x} \geq 0.

Задача 2k+1: 

minimize ||q^{(2k+1)}-A\mathbf{y}||          

subject to \mathbf{y}^TA^TA\mathbf{y} = 1,  J_m \mathbf{y} \geq 0.

При решении задач, на каждом шаге значения констант p^{(2k)} и q^{(2k+1)}. при- нимаются равными значениям соответствующих решений x и y предыдущего шага.

РЕШЕНИЕ ЗАДАЧИ 2.

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

Смотри также


Данная статья была создана в рамках учебного задания.
Студент: Михаил Кузнецов
Преподаватель: В.В.Стрижов
Срок: 24 декабря 2010


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9E%D1%86%D0%B5%D0%BD%D0%BA%D0%B0_%D1%8D%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BF%D1%80%D0%B8%D1%80%D0%BE%D0%B4%D0%BE%D0%BE%D1%85%D1%80%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»
Личные инструменты