Многомерное шкалирование

Ранее к анализу блогов был применен также метод многомерного шкалирования. Как и кластеризация, это метод обучения без учителя. Он предназначен не для прогнозирования, а чтобы понять, как различные образцы связаны между собой. Алгоритм создает представление набора данных в пространстве меньшей размерности, стараясь по возможности сохранить исходные расстояния между элементами. Если речь идет о представлении на экране или на бумаге, то многомерный набор представляется в двумерном пространстве.

Возьмем, к примеру, четырехмерный набор данных, показанный в табл. 12.8 (каждый образец характеризуется четырьмя переменными).

Таблица 12.8. Простой четырехмерный набор для шкалирования

A

0,5

0,0

0,3

0,1

B

0,4

0,15

0,2

0,1

C

0,2

0,4

0,7

0,8

D

1,0__

0,3

0,6

0,0

Вычисляем евклидово расстояние между каждой парой образцов. Например, расстояние между A и B равно sqrt(0,1 ^ 2 + 0,15 ^ 2 + 0,1 ^ 2 + + 0,0 ^ 2) = 0,2. Полная матрица попарных расстояний приведена в табл. 12.9.

Таблица 12.9. Матрица расстояний

 

A

B

C

D

A

0,0

0,2

0,9

0,8

B

0,2

0,0

0,9

0,7

C

0,9

0,9

0,0

1,1

D

0,8

0,7

1,1

0,0

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

Рис. 12.15. Расстояния между образцами

Для каждой пары образцов целевое расстояние сравнивается с текущим и вычисляется расхождение. Каждый образец немного приближается к своему соседу или отодвигается от него на расстояние, пропорциональное расхождению между ними. На рис. 12.16 показаны

Рис. 12.16. Силы, действующие на образец A

силы, действующие на образец A. Расстояние между A и B на диаграмме равно 0,5, а целевое расстояние между ними составляет 0,2, поэтому A перемещается ближе к B. В то же время A отталкивается образцами C и D, потому что он оказался слишком близко. Каждый узел перемещается в соответствии с комбинацией всех других узлов, притягивающих и отталкивающих его. Каждый раз, когда это происходит, разница между текущим и целевым расстоянием слегка уменьшается. Эта процедура повторяется многократно до тех пор, пока общее количество ошибок больше нельзя будет уменьшить путем дальнейшего перемещения образцов.

Использование ранее написанного кода

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

>>> labels=[‘A’,’B’,’C’,’D’] >>> scaleset=[[0.5,0.0,0.3,0.1],

… [0.4,0.15,0.2,0.1], … [0.2,0.4,0.7,0.8], … [1.0,0.3,0.6,0.0]]

>>> twod=clusters.scaledown(scaleset,distance=euclidean) >>> twod

[[0.45, 0.54], [0.40, 0.54], [-0.30, 1.02], [0.92, 0.59]]

Вторая функция, draw2d, принимает шкалированный список и создает изображение:

>>> clusters.draw2d(twod,labels,jpeg=’abcd.jpg’) В результате создается файл abcd.jpg. Визуализировать список можно и другими способами, например загрузив данные, возвращенные scaledown, в какую-нибудь подходящую программу, скажем в электронную таблицу.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100