1 Определение количества информации по Хартли и Шеннону1
|
Скачать 490.82 Kb.
|
4.5. Алгоритм BIGFORЧто делать, если массив из m точек очень велик и не помещается в оперативной памяти? При этом затраты на «поточечное» чтение координат из внешнего носителя будут неприемлемо велики. 1. Разбить исходный массив на t=m/V подмассивов, V – число точек в подмассиве m. С помощью FOREL-2 разделить каждый из подмассивов на k’ таксонов. Описание каждого j-го таксона содержит координаты его центра и количество внутренних точек m’j. В итоге получим q=tk’ точек-центров таксонов. 2. Вновь используем FOREL-2 для разбиения этих точек на k-таксонов. Только при расчете центров тяжести учитывается вес («массу») m’j. 3. Перераспределяем точки между k таксонами. 4.6. Иерархическая таксономияДля иерархической таксономии по методу «снизу-вверх» используется алгоритм BIGFOR, только с исключенной процедурой перераспределения точек. На первом шаге радиус устанавливается малым, дающим таксоны нижнего уровня. На последующих шагах таксоны укрупняются, образуя вышележащие урони иерархии. Процесс прекращается, когда в итоговый таксон войдут все точки исходного множества. Для кластеризации «сверху-вниз» используется FOREL с последовательным уменьшением радиуса сферы. 1. Определяем минимальный радиус гиперсферы R, включающей все точки m. Эти точки составляют таксон верхнего уровня. 2. Уменьшая от шага к шагу радиус, определяем таксоны i-х уровней. 3. Процесс завершается при числе таксонов нижнего уровня равного m - по точке в таксоне. 4.7. Динамическая таксономия - алгоритм DINAПри зависимости мощности кластеризуемого множества от времени результат кластеризации может меняться с появлением или исчезновением точек. Для таксономии объектов, возникающих по одному или небольшими группами применяется алгоритм DINA. Задается некоторый радиус R. Первая появившаяся точка или группа точек объявляется центром первого таксона. При появлении новой точки производится проверка, попадает ли точка внутрь гиперсферы. В зависимости от результата точка либо включается в состав таксона, а центр гиперсферы смещается в центр тяжести внутренних точек, либо новая точка объявляется центром нового таксона. Далее процесс очевиден. Можно следить за тем, чтобы таксоны не «переполнялись» - содержали по возможности одинаковое количество точек. При переполнении таксон можно разбить на два с одинаковым числом точек. Переход от описания исходных объектов к описанию таксонов эквивалентен переходу от данных к знаниям. Иерархическая таксономия отображает структуру нашего знания об изучаемом явлении. Можно строить иерархии понятий («растущие пирамидальные сети») в процессе накопления новых фактов. Могут возникать таксоны с чрезмерно большим количеством объектов и тогда их следует «таксономировать», что эквивалентно детализации знаний. 4.8. Таксономия с суперцелью. Алгоритм ROSTРассмотренные выше алгоритмы таксономии - это универсальные алгоритмы, так сказать, «на все случаи жизни». Однако, такой подход во многих конкретных случаях может оказаться неоптимальным. Например, в задачах распознавания устной речи, обычно пользуются не отдельными фонемами, а их группами (звукотипами). При этом неприемлемо, если в одну группу попадут очень похожие по своим спектральным характеристикам звуки «т», «к», «п» («ток», «кот», «кто»). Таксоны на уровне звукотипов должны строиться с учетом «суперцели»: помимо того, что таксоны должны объединять похожие элементы, количество таксонов должно быть минимальным, но достаточным для принятия решений на более высоких уровнях. Таким образом, мы четко сформулировали цель таксономии и термины типа «самообучение», «обучение без учителя» более неприемлемы. Таксономия с учетом суперцели может быть получена алгоритмом ROST. Алгоритм ROST - это вариант иерархической таксономии методом «снизу вверх». Вначале мы применяем FOREL с малым радиусом гиперсферы. Затем радиус увеличиваем и после каждого шага делаем проверку на соответствие суперцели: не возникают ли ошибки из-за укрупнения таксонов (например, звукотипов). Если нет, то процесс продолжается, в обратном случае, то точки таксона, приводящего к ошибкам подвергаются повторной таксономии с меньшим радиусом гиперсферы и из дальнейшего рассмотрения исключаются. Укрупнение продолжается до тех пор, пока из рассмотрения не будут исключены все точки. |
Похожие:
 |
Школьная газета как средство формирования Причины таких изменений вызваны резким увеличением количества информации. А на стыке веков в 2000 году на Давоском форуме Тони Блэр,... |
 |
Поиск информации в Интернет В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые... |
|
Автоматизированная система регистрации на услуги одо «Автопроспектсервис» Анализ технологии обработки информации в предметной области и определение требований к асои 4 |
|
Практическое пособие. Оглавление А. Личные мотивы выдачи информации.... Определение людей, которым с точки зрения объекта предельно нежелательно знать чернящие его данные. 82 |
|
Рейтинг-план по курсовым работам Факультет ппф курс 2-3 Группы: о-11, сдп-11, о-12, сдп-12 Поиск и определение источников информации по теме курсовой работы, составление списка литературы и других источников |
|
Конфиденциальность гарантируется получателем информации Нарушение порядка представления статистической информации, а равно представление недостоверной статистической информации влечет ответственность,... |
|
Программа Visual Graph может работать как в Unix системах, так и в Windows Визуализация информации — это процесс преобразования больших и сложных видов абстрактной информации в визуальную форму. Универсальным... |
|
План Введение. Определение и виды эксперимента. Основные принципы... К числу самых своеобразных и трудноосваиваемых методов сбора социологической информации относится эксперимент. Уже одно название... |
|
Программа междисциплинарного экзамена по специальности 075200 «компьютерная безопасность» Понятие информации. Количество информации в равновероятных и неравновероятных сообщениях |
|
Колесник В. Д., Полтырев Г. Ш. Курс теории информации Сети ЭВМ и телекоммуникации, сетевые технологии, распределенные автоматизированные системы обработки информации и управления |