WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Построение кодовой книги 1 Построение кодовой книги Для каждого Составление словаря слова:

Предварительная обработка и параметризация сигнала Кодовая книга Запись характерных признаков в БД Кластеризация БД БД 2 Построение кодовой книги Кодовая книга - упорядоченный набор наиболее характерных элементов речи -предназначена для кодирования речи - замены многомерных характерных признаков числами (номером признака в кодовой книге) S(t) Речевой сигнал Кодовая Характерные признаки книга X1 X2 X N Номера эталонных признаков из кодовой книги 125 34 396 7 89 715 173 19 nN n2 n1 3 Кодовая книга Позволяет:

- снизить избыточность информации - повысить надежность распознавание - создать спикер-независимую распознающую систему - конструировать более сложные элементы (в видесмесей) Кластеризация Кодовая книга Исходный набор характерных признаков Конструирование более 4 сложных элементов Х Кластеризация Кластеризация (англ. Data clustering) — задача машинного обучения, в которой требуется разбить заданную выборку объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались (Википедия — свободная энциклопедия http://ru.wikipedia.org/wiki/) cluster - кисть, пучок, гроздь Процесс кластеризации 1. Выбрать метрику:

- расстояние между объектами - расстояние между классами 2. Выбрать метод кластеризации - при известном числе классов - при неизвестном числе классов 3. Провести кластеризацию 4. Сохранить центроиды кластеров (кодовая книга) Расстояние между объектами dij 0 - свойство неотрицательности расстояния dij = dji - свойство симметрии dij + djk dik - неравенство треугольника Если dij 0, то i j - различимость нетождественных объектов Если dij = 0, то i = j - неразличимость тождественных объектов n p p i - обобщенное расстояние Минковского dij = xk - xkj k = n 2 i - евклидово расстояние - при p = dij = (xk - xkj ) k = n i p = - Manhattan расстояние ( или - city-block ) - при dij = xk - xkj k = i dij = max xk - xkj p - расстояние Чебышева - при k =1..n T 2 - - расстояние Махаланобиса dij =(Xi - X ) S (Xi - X ) j j Расстояние между объектами Б евклидово расстояние Y d = X + Y ( ) ( ) А X Б Manhattan расстояние Y d = X + Y А X Примеры кластеризации для различных метрик евклидово расстояние Manhattan расстояние расстояние Минковского P= расстояние Махаланобиса Расстояние между кластерами - по принципу «ближнего соседа» (nearest neighbor) ij = min d(Xk, Xl) X i k X l j - по принципу «дальнего соседа» (furthest neighbor) ij = max d(Xk, Xl) X i k X l j - между «центрами тяжести» (центроидами) кластеров ij = d(Ci,C ) j ij ij С С Агломеративный метод кластеризации (от латинского agglomero – присоединяю, накапливаю) 1. Инициализация. Каждый элемент множества образует свой кластер 2. Последовательное объединение двух наиболее близких кластеров C1 C2 C3 C4 C5 C Отображение результатов в виде дендрограммы(от латинского dendron- дерево) Междукластерное расстояние Алгоритм К-средних (K-mean) (при известном числе кластеров) 1. Инициализация.

Выбираем К произвольных попарно несовпадающих векторов и назначаем их центрами кластеров (центроидами) - Ci 2. Поиск ближайших соседей.

X Для каждого вектора из обучающего множества находим ближайший j центроид Ci i = arg min d X, Ci ( ) j 1iK 3. Уточнение положений центроидов Ci = X i X i j j 4. Проверка условия окончания итераций K = Ci (t) - Ci (t -1) i= Если, то СТОП;

иначе возврат к пункту 2.

Алгоритм ART - Adaptive Resonance Theory (при неизвестном числе кластеров) - ограничение на MAX удаленность объектов, принадлежащих одному кластеру 1. Произвольным образом выбирается один объект, X, который назначается центром первого кластера: C1 = X1.

2. Далее для всех остальных объектов выполняется следующая процедура:

2.1. Находится ближайший кластер (среди всех найденных к текущему времени) dm = min d Xi,Ck ( ) k Cm dm 2.2. Если, то корректируется положение центра кластера Cm = Cm + 1- ) Xi ( Иначе образуется новый, K+1 кластер с центром в Xi Ck +1 = Xi Построение кодовой книги По сути – запоминание центроидов кластеров и их размеров Кодовая Di книга 0. C 0. • 0. • C.

•.

C.

•.

C 0. - диаметр (размер) кластера Di = max d(X, Xk) j X i j X i k Кодирование с помощью кодовой книги 1. Для каждого вектора характерных признаков X находим ближайший j элемент из кодовой книги:

i = arg min d X, Ci ( ) j 1iK 2. Заменяем вектор X номером найденного ближайшего элемента:

j X i j Кодовая Характерные признаки книга X1 X X N Номера ближайших элементов из кодовой книги 125 34 396 7 89 715 173 nN n n Конструирование более сложных элементов M V - вектор из кодовой книги ( -Vjm X ) jm bj (X ) = C exp jm m=1 - размер соответствующего кластера jm jm 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.35 0. 0.35 0. 0.35 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 V1 = 2, 1 = 1 V2 = 4, = 1.6 V3 = 6, 3 = 0. V1 = 2, 1 = 1 V2 = 4, = 1.6 V3 = 6, 3 = 0. 1 1.4 4. 1 1.4 4. 1 1.4 4. 0. 0. 0. 1. 1. 1. 0. 0. 0. 3. 3. 3. 0. 0. 0. 0. 0. 0. 0. 0. 0. 2. 2. 2. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 C1 = C2 = C3 = 1 C1 = C3 = 1, C2 = 2 C1 = 10, C2 = 4, C3 = C1 = C2 = C3 = 1 C1 = C3 = 1, C2 = 2 C1 = 10, C2 = 4, C3 = C1 = C2 = C3 = 1 C1 = C3 = 1, C2 = 2 C1 = 10, C2 = 4, C3 =




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.