9. Нахождение покрытий и градиентный алгоритм приближённого решения этой задачи

В настоящее время не существует эффективного алгоритма для решения этой задачи, «и в практических приложениях используются простые в вычислительном отношении алгоритмы, которые отыскивают покрытия хотя и не минимальные, но достаточно близкие к минимальным. К таким алгоритмам относятся градиентные алгоритмы или алгоритмы наикратчайшего спуска... . На каждом шаге такой алгоритм выбирает элемент е множества Е, покрывающий наибольшее число элементов множества V, не покрытых на предыдущих шагах» (Сапоженко, Асратян, Кузюрин, 1977, с. 51).

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

Задача о покрытии тесно связана с вышеперечисленными типовыми постановками а - д. В частности, задачи кластер – анализа, связанные с нахождением разбиений, при некоторых дополнительных, достаточно общих предположениях можно трактовать как задачи на нахождение покрытий.

10. Учебно-методические рекомендации, контрольные вопросы, комментарии

Раздел 2

1. Решающая функция в распознавании образов – это отображение, переводящее набор значений разнотипных признаков X₁(S),…,X_n(S) в число. Это число – значение решающей функции F на объекте S. Решающее правило в распознавании образов – это высказывание, которое содержит значения решающей функции и управляющих параметров и, с учётом этих значений, либо относит пробу к одному из классов, либо отказывается от распознавания.

2. Сформулируйте понятие решающей функции применительно к задаче упорядочения.

3. Может ли целевой признак применительно к сформулированной в разделе 2 версии задачи упорядочения быть а) логическим; б) номинальным?

4. Почему на начальных этапах развития кластер - анализа его (в противовес распознаванию образов) называли «обучением без учителя»?

5. Зависимость между признаками может быть представлена как в виде, разрешённом относительно того или иного признака, например, X_j ≈ f(X_i,X_k,…,X_l), так и без такого разрешения. Например, (ln(X_j))² + ln(X_j+X_k) -1≈0.

6. Сформулируйте задачу распознавания как задачу заполнения единичного пропуска.

7. Сформулируйте задачу заполнения единичного пропуска в бинарном или номинальном признаке как задачу распознавания.

Раздел 3

1. В каких случаях и почему для оценки связи между количественными признаками рационально использовать ранговый коэффициент Спирмена?

2. Всегда ли множественная линейная регрессия будет точно решать задачу упорядочения?

3. Можно ли применять линейную регрессионную модель из раздела 3, если Y- ранговый признак?

4. Можно ли применять линейную регрессионную модель из раздела 3, если Y- номинальный признак?

5. Можно ли применять линейную регрессионную модель из раздела 3, если хотя бы один признак из списка X₁,…,X_n – ранговый или номинальный?

6. Можно ли без предварительной нормировки признаков сопоставлять веса, с которыми они входят в уравнение регрессии, с целью их упорядочения по влиянию на значение прогнозируемого показателя?

7. Что такое  в разделе «Множественная линейная регрессия» пакета “Statistica for Windows? Как величины _j могут быть использованы при сравнении характеристических признаков по их влиянию на значение зависимого (целевого) признака?