1 Определение количества информации по Хартли и Шеннону1

Скачать 490.82 Kb.

Название	1 Определение количества информации по Хартли и Шеннону1
страница	8/13
Дата публикации	18.09.2014
Размер	490.82 Kb.
Тип	Литература

literature-edu.ru > Информатика > Литература

1 ... 5 6 7 8 9 10 11 12 13

4. Таксономия. Алгоритмы класса FOREL

Человек, группируя объекты, руководствуется некоторым критерием (F). Следовательно, гипотеза более сильная, чем гипотеза компактности (H), должна быть сформулирована с учетом этого критерия. Тестовый алгоритм должен допускать только такую группировку, которая удовлетворяет критерию F. Иными словами, следует конкретизировать понятие сходства, «схожести» объектов.

Считаем, что признаки объектов заданы в сильных шкалах и мы можем работать в метрических пространствах. В частности, можем в евклидовом многомерном пространстве признаков ввести расстояние между точками.
Пусть
C_j=(x_j,1,x_j,2,..,x_j,i,..,x_j,n) - координаты центра тяжести j-го таксона,
(напомню, что координаты центра тяжести системы материальных точек определяются по формуле:
x_j,i =, где - i-я координата k-ой точки j-го таксона, N_j – число точек j-го таксона. В нашем случае все «массы» равны 1, и получаем:
x_j,i =.)

Ρ_j,i - расстояние между центром тяжести и произвольной точкой a_i,
ρ_j=Σ_i Ρ_j,i - сумма таких расстояний j-го таксона.
F=ρ_j.
Смысл критерия похожести на центр состоит в том, чтобы найти такое разбиение m объектов на k таксонов, при котором F минимальна.

4.1. Алгоритм Forel

1. Признаки объектов нормируются так, чтобы их значения находились между нулем и единицей.

2. Строим гиперсферу минимального радиуса R₀, охватывающую все m точек.

3. Полагаем R’₀=0.9R₀

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

5. Переносим центр сферы в центр тяжести и снова находим внутренние точки.
Таким образом, центр сферы перемещается в область локального сгущения точек. Когда сфера остановится, внутренние точки объявляем принадлежащими таксону № 1 и исключаем их из рассмотрения.

Повторяем процедуру с оставшимися точками, и так до тех пор, пока все точки не будут распределены по таксонам.

Если начальную точку на шаге 4 менять случайным образом, может получиться несколько вариантов таксономии, из которых выбирается тот, на котором достигается min(F).

4.2. Forel-2

Эта модификация исходного алгоритма используется в случае, когда нужно получить в точности t-таксонов. Радиус сферы по мере надобности уменьшается или увеличивается на величину R, которая от итерации к итерации уменьшается, например, вдвое.

Наилучшему варианту таксономии отвечает min(F) при числе таксонов равном t.

4.3. SKAT

В результате работы алгоритма FOREL могут образоваться неустойчивые таксоны, случайные сгустки, тяготеющие к одному из полученных таксонов. Это может произойти в результате недостаточной «корректности» исходных данных.

Один из эвристических приемов для учета неустойчивых таксонов реализован в алгоритме SKAT.

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

4.4. Алгоритм KOLLAPS

Алгоритм KOLLAPS применяется в задачах выделения локальных сгустков точек из фона. Например, выделения ярких созвездий на фоне неба.

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

1. Прежде всего задается некоторое значение порога плотности - количества точек m_j в таксоне (d). Если m_j >d, то запоминается центр таксона, а его точки из дальнейшего рассмотрения исключаются. В противном случае центр не запоминается, но точки таксона из рассмотрения исключаются.

2. Затем центр переносится в любую из оставшихся точек и процесс продолжается до исчерпания всех точек.

3. Восстанавливаем все множество точек, выбираем таксон с максимальным значением d, помещаем сферу в его центр.

4. Начинаем сжимать сферу.

5. На каждом шаге сжатия определяем число внутренних точек. Если начальный радиус был слишком велик, то изменение d будет медленным. По мере вхождения в более плотные области, темп изменения будет увеличиваться, что и служит сигналом к остановке сжатия. Фиксируется число внутренних точек таксона m’_j.

6. Процедура повторяется для всех запомненных центров таксонов.

7. Выбирается k таксонов с наибольшим количеством точек.

1 ... 5 6 7 8 9 10 11 12 13

Похожие:

	Школьная газета как средство формирования Причины таких изменений вызваны резким увеличением количества информации. А на стыке веков в 2000 году на Давоском форуме Тони Блэр,...		Поиск информации в Интернет В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые...
	Автоматизированная система регистрации на услуги одо «Автопроспектсервис» Анализ технологии обработки информации в предметной области и определение требований к асои 4		Практическое пособие. Оглавление А. Личные мотивы выдачи информации.... Определение людей, которым с точки зрения объекта предельно нежелательно знать чернящие его данные. 82
	Рейтинг-план по курсовым работам Факультет ппф курс 2-3 Группы: о-11, сдп-11, о-12, сдп-12 Поиск и определение источников информации по теме курсовой работы, составление списка литературы и других источников		Конфиденциальность гарантируется получателем информации Нарушение порядка представления статистической информации, а равно представление недостоверной статистической информации влечет ответственность,...
	Программа Visual Graph может работать как в Unix системах, так и в Windows Визуализация информации — это процесс преобразования больших и сложных видов абстрактной информации в визуальную форму. Универсальным...		План Введение. Определение и виды эксперимента. Основные принципы... К числу самых своеобразных и трудноосваиваемых методов сбора социологической информации относится эксперимент. Уже одно название...
	Программа междисциплинарного экзамена по специальности 075200 «компьютерная безопасность» Понятие информации. Количество информации в равновероятных и неравновероятных сообщениях		Колесник В. Д., Полтырев Г. Ш. Курс теории информации Сети ЭВМ и телекоммуникации, сетевые технологии, распределенные автоматизированные системы обработки информации и управления

Литература