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

В настоящее время не существует эффективного алгоритма для решения этой задачи, «и в практических приложениях используются простые в вычислительном отношении алгоритмы, которые отыскивают покрытия хотя и не минимальные, но достаточно близкие к минимальным. К таким алгоритмам относятся градиентные алгоритмы или алгоритмы наикратчайшего спуска.... На каждом шаге такой алгоритм выбирает элемент е множества Е, покрывающий наибольшее число элементов множества 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. Что такое b в разделе «Множественная линейная регрессия» пакета “Statistica for Windows? Как величины b_j могут быть использованы при сравнении характеристических признаков по их влиянию на значение зависимого (целевого) признака?

 

Раздел 4

1. В чём заключается экспликация на этапе формирования списка исходных признаков?

2. Каким образом штрафы за ошибки и отказы позволяют регулировать оценку качества распознавания?

3. Какое из двух линейных решающих правил, имеющих одинаковую оценку качества распознавания, предпочтительнее: использующее 5 признаков или 7?

4. Если метод распознавания используется для уточнения границ (по латерали) геологического объекта в осадочной толще, то некоторый процент отказов или даже ошибок в узлах сетки может и не повлиять на прогнозируемое расположение его границы. В результате решения задачи распознавания образов для узлов сетки на принадлежность локального участка (центром которого является узел) к моделируемому объекту появляется предварительная версия границы. Обычно, в результате анализа полученной версии, геологическая ситуация, в целом, становится ясной, так что исследователь уже в состоянии «самостоятельно» провести границу объекта.

5. В результате решения задач распознавания с использованием признаков, рассчитанных по сеткам реперных геофизических поверхностей и данным глубокого бурения (разбивки по стратиграфическим уровням, толщины горизонтов и пр.), в ИНГГ СО РАН были уточнены границы (по латерали) основных стратиграфических горизонтов в нижне-среднеюрских отложениях Западной Сибири, что, в свою очередь, позволило уточнить оценки ресурсов УВ юры ряда крупных регионов.

6. Читая работы по применению методов распознавания в геологии нефти и газа, следует иметь в виду, что, обычно, исследователь опирается на свой опыт решения аналогичных задач и литературные данные; при этом использует не «самое лучшее» программное обеспечение, а то, которым располагает и умеет пользоваться.

7. Опыт решения многочисленных практических задач в области моделирования геологических объектов в слоистой толще позволяет сформулировать нижеследующие требования к алгоритмам и программному обеспечению распознавания образов применительно к моделированию региональных, зональных и локальных объектов в осадочном бассейне:

- «уметь» работать с признаками, заданными на сетках;

- отыскивать простые и легко интерпретируемые решающие правила;

- обеспечивать эффективное снижение размерности описания n;

- работать с зависимыми и разнотипными признаками;

- учитывать сложный характер разделения классов (по латерали).

 

Раздел 5

Множественный линейный регрессионный анализ предназначен для отыскания линейной зависимости признака Y от признаков X₁,…,X_n

Y≈ a ₁X₁ +…+ a_nX_n + b =L(X₁,..., X_n). (4)

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

Решение линейной регрессионной задачи по нахождению минимума функционала (4) может не привести к нахождению приемлемой аппроксимации решения задачи упорядочения. Однако, можно попытаться провести преобразование целевого признака X_n+1 монотонной функцией Ψ таким образом, чтобы для Ψ(X_n+1) методом наименьших квадратов можно было получить искомую аппроксимацию. Поскольку Ψ монотонна, это даёт решение задачи упорядочения.

«Универсального» способа выбора Ψ, скорее всего, не существует. Однако можно привести некоторые практические рекомендации по его подбору.

Монотонная функция Ψ, как правило, используется в том случае, когда «обычный» коэффициент парной корреляции r (Дёмин, 2005, с. 42-44) между значениями целевого признака X_n+1 и соответствующими значениями, рассчитанными по уравнению множественной линейной регрессии, «мал». При этом содержательные соображения позволяют предполагать, что упорядочить объекты по убыванию целевого признака X_n+1 по значениям X₁,..., X_n всё-таки можно. Чаще всего множественная линейная регрессия с «удачно подобранным» Ψ успешно применяется, когда распределение значений в последовательности X_n+1(S_m), X_n+1(S_m-1),…, X_n+1(S₁) имеет ярко выраженный нелинейный характер, сопоставимый, например, с экспонентой. Функция Ψ, обычно, выбирается таким образом, чтобы, по возможности, устранить резкую нелинейность. Логарифм – типичный пример подобной функции, неоднократно использованный в подобных ситуациях при решении практических задач

Раздел 6

1.Пусть A_l={(0,1), (2,0), (2,3)}, A_q={(5,1), (6,2), (8,3), (9,5), (10,7)}. Рассчитайте расстояния (а –ж).

2. Полагая S= A_l ÈA_q решите задачу кластеризации совокупности объектов S методом Чоудари

3. На локальном уровне для отдельной площади или скопления площадей («малой» зоны) кластер-анализ успешно применяется при корреляции дизъюнктивных нарушений по данным 3D-сейсморазведки (Кашик и др, 2004).

Опыт применения кластер-анализа на региональном и зональном уровне показал, что эти методы могут давать полезную информацию об истории развития изучаемых толщ и тектонических процессах, типах геологических разрезов, их раcпространении по латерали, зонах развития коллекторов в них, нефтегазоносности. Однако для этого, как выяснилось, нужны достаточно «густые» регулярные сетки толщин отложений, поэтому главный фактор, сдерживающий его применение при региональных и зональных построениях (в случае «больших» территорий), – необходимость хранения и пересчётов матрицы расстояний для всей совокупности объектов.

Если исходить из оценки трудоёмкости вычислений, то на локальном уровне, за исключением обработки данных 3D-cейсморазведки, вполне можно использовать практически любые алгоритмы кластер-анализа. При региональных и зональных построениях с использованием сеточных моделей (в случае «больших» территорий), а также при обработке данных 3D-сейсморазведки (даже на уровне отдельной площади или «малой зоны»), целесообразно выбирать алгоритм, не требующий пересчёта матрицы расстояний, например, метод Чоудари.

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

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

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

6. Замечательной особенностью метода Чаудари, на наш взгляд, является то, что при заданном максимальном числе разбиений он позволяет без искажения результата «загрубить» исходные данные и, вследствие этого, существенно уменьшить объем обрабатываемой выборки за счет удаления повторяющихся объектов.

Однако, применительно к региональным и зональным построениям, и он уязвим с точки зрения возникновения большого числа несущественных кластеров, образуемых «аномальными», «уникальными», «переходными» и т.п. объектами.

Кроме того, результаты кластеризации существенно зависят от выбранных пользователем минимальных и максимальных значений признаков. Это могут быть как выборочные минимумы и максимумы, так и значения, меньшие выборочного минимума и большие максимума. Выбор таких значений может быть обусловлен какими-либо теоретическими или практическими соображениями.

 

Раздел 7

Предложите способы заполнения одиночного пропуска сведением к решению задач (а-в) с учётом шкалы, в которой замерен признак с пропуском, без потери исходной информации.

 

Раздел 8

1. Объясните, почему стохастические константы можно рассматривать как частный случай решающих правил распознавания.

2. Следует учесть, что по коэффициенту Спирмена связь между двумя количественными признаками X и Y может оказаться недостоверной, будучи, с содержательных позиций, вполне очевидной. Это может быть связано с малым объёмом выборки, наличием грубых единичных ошибок и т.д. При этом программный продукт Statistica for Windows будет давать достоверную связь при вычислении коэффициента Пирсона. Однако, если не выполнены жёсткие вероятностно-статистические предположения о совместном распределении двух признаков (см. раздел 3), опираться в геологическом анализе на установленную достоверность связи по Пирсону некорректно.

Раздел 9

Приведем пример решения задачи о покрытии градиентным методом. Пусть покрываемое множество V состоит из 10 элементов v ₁,…, v ₁₀, а покрывающее множество Е – из девяти: e ₁,…, e ₉, где

e ₁={1,4,6,8,9,10},

e ₂={3,5,7,8},

e ₃={2,4,6,8,9},

e ₄={2,3,5,7},

e ₅={1,7,8},

e ₆={2,3,9},

e ₇={4,6,8,9,10},

e ₈={3,4,6,8,9},

e ₉={5,6,7,8,9}.

Отношение инцидентности I зададим следующим образом: v _i Ie _j если и только если i Î e _j.

Первый шаг градиентного алгоритма заключается в выборе e ₁ как инцидентного максимальному числу элементов множества V. После этого шага остались не покрытыми v ₂, v ₃, v ₅, v ₇,. Все они инцидентны элементу e ₄. Таким образом множество C={ e ₁, e ₄} – покрытие. Покрытий, состоящих из одного элемента, как легко видеть, нет. Поэтому С – минимальное покрытие.