Главная > Математика > Прикладная статистика: Классификации и снижение размерности
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.6. Алгоритмы, основанные на методе просеивания (решета)

Общим для всего этого семейства алгоритмов является наличие следующих трех блоков [35]:

1) парное сравнение объектов и составление для каждого объекта кортежа «похожих» на него объектов;

2) упорядочение (оцифровка) выборки в соответствии с целью классификации;

3) классификация, моделирующая принцип решета Эратосфена на вход классификатора поступает выборка, упорядоченная в блоке 2. Первый объект объявляется типичным представителем первого таксона, в который включается кортеж похожих на него объектов, составленный в блоке 1, после чего этот кортеж удаляется (вычеркивается) из выборки. Типичным представителем следующего таксона объявляется первый из оставшихся объектов упорядоченной выборки, а кортеж похожих на него объектов включается во второй таксон, те же из них, которые не были удалены на предыдущем шаге, удаляются из выборки. Такая процедура классификации продолжается до тех пор, пока вся выборка или наперед заданная доля ее не будет расклассифицирована.

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

Переход внутри семейства от одного алгоритма к другому осуществляется настройкой управляющих параметров.

В блоке 1 такие параметры определяются видом входной информации. Так, если выборка характеризуется матрицей «объект — свойство», то оценка похожести происходит с помощью той или иной меры близости, которая тем самым становится параметром алгоритма. Если же входная информация представлена в виде матрицы попарных взаимных расстояний, то кортеж похожих объектов рассчитывается с использованием пороговых значений, которые либо задаются, либо оцениваются на основе анализа матрицы взаимосвязей.

В блоке 2 упорядочение элементов выборки, как правило, проводится при помощи функционала, который сопоставляет с каждым объектом выборки число, характеризующее, насколько этот объект типичен для совокупности похожих на него с точки зрения целей классификации. Для выбранного функционала полагаем если в случае если нет дополнительной информации, то полагаем при . Блок 3 не содержит управляющих параметров, поэтому далее при описании конкретных алгоритмов классификации методом Эратосфена (АКМЭ) опускаем его.

Рассмотрим более детально алгоритмы семейства, реализующие выделение таксонов при помощи поиска локальных максимумов функции плотности распределения объектов в признаковом пространстве X.

Алгоритм на основе модельной локальной плотности. Выберем в качестве модельной некоторую плотность распределения , имеющую единственный максимум в нуле, и пусть — такая область, что

Будем считать, что является носителем плотности

Возьмем оценку плотности распределения по выборке в виде

где — веса точек . Тогда первые два блока алгоритма можно описать следующим образом:

1. Для каждого выделим подвыборку составленную из всех элементов , для которых

2. Упорядочим выборку при помощи плотности т. е. считая, что если Например, возьмем модельную локальную плотность в вида

где - дисперсия случайного вектора в с плотностью распределения (см. § 20.2).

Рассмотрим семейство алгоритмов для области Это семейство имеет два управляющих параметра: и а. Похожими на элемент X; считаются все элементы выборки, отстоящие от него не более чем на , т. е. При фиксированном с ростом а в модельной плотности убывает и в упорядочении выборки все большее значение начинает иметь разброс кортежа относительно т. е. на первые места выходят с меньшим разбросом кортежа относительно

Для модельной плотности и одинаковых весов классификация проводится при помощи плотности распределения

которая с точностью до константы совпадает с функционалом качества в алгоритме Форель.

Ясно, что выделение первого таксона в алгоритме Форель представляет собой градиентный поиск локального максимума плотности .

Таким образом, если выборка представляет собой объединение сгустков, каждый из которых полностью помещается в шар радиуса , то алгоритм Форель даст практически тот же результат, что и алгоритм классификации методом Эратосфена (АКМЭ) для плотности . Следующий таксон алгоритмом Форель выделяется после того, как из выборки удалены точки первоготаксона, и т.д., что в ряде случаев (например, не угадан порог ) приводит к сильном зависимости результата классификации от выбора начальной точки, в то время как в АКМЭ вообще отсутствует необходимость выбора начальной точки.

Алгоритм на основе ближайших соседей. В этом алгоритме классификация проводится, по существу, при помощи оценки плотности распределения, получаемой по методу «ближайших соседей».

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

1. Для каждого составим кортеж из ближайших к нему элементов.

2. Пусть — разброс кортежа относительно Упорядочим выборку считая, что если

В блоке 2 можно использовать также следующий способ упорядочения выборки

2. Пусть — расстояние от до самого дальнего из ближайших к нему соседей -Упорядочим выборку считая если .

Описанные здесь блоки 1 и 2 вместе с блоком 3, общим для всех алгоритмов метода просеивания, составляют алгоритм Уишарта [332], предложенный им в качестве альтернативы агломеративной процедуры иерархической классификации по методу «ближайшего соседа» в тех случаях, когда она приводит к нехарактерным для исследуемого явления объединениям типа «цепочного эффекта».

<< Предыдущий параграф Следующий параграф >>
Оглавление