Просмотр данных на двумерной плоскости

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

В этом разделе мы ознакомимся с методом многомерного шкалирования, позволяющим найти двумерное представление набора данных. Этот алгоритм принимает на входе различие между каждой парой предметов и пытается нарисовать диаграмму так, чтобы расстояния между точками, соответствующими предметам, отражали степень их различия. Для этого сначала вычисляются желаемые расстояния (target distance) между всеми предметами. В случае набора данных о блогах для сравнения предметов применялся коэффициент корреляции Пирсона. В табл. 3.2 приведен пример.

Таблица 3.2. Пример матрицы расстояний

Затем все предметы (в данном случае блоги) случайным образом размещаются на двумерной диаграмме, как показано на рис. 3.7. Вычисляются попарные евклидовы расстояния (сумма квадратов разностей координат) между всеми текущими положениями предметов, как показано на рис. 3.8.

Рис. 3.7. Начальное размещение на двумерной проекции

 

Рис. 3.8. Попарные расстояния между предметами

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

Рис. 3.9. Силы, действующие на предмет A

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

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

def scaledown(data,distance=pearson,rate=0.01): n=len(data)

#       Настоящие расстояния между каждой парой предметов realdist=[[distance(data[i],data[]]) for j in range(n)]

for i in range(0,n)]

outersum=0.0

#       Случайным образом инициализировать начальные положения предметов на

#       плоскости

loc=[[random.random(),random.random( )] for i in range(n)] fakedist=[[0.0 for j in range(n)] for i in range(n)]

lasterror=None for m in range(0,1000): # Вычислить евклидовы расстояния for i in range(n): for j in range(n): fakedist[i][]]=sqrt(sum([pow(loc[i][x]-loc[]][x],2)

for x in range(len(loc[i]))]))

#       Переместить точки grad=[[0.0,0.0] for i in range(n)]

totalerror=0 for k in range(n): for j in range(n): if j==k: continue

#   Расхождение – это относительная разность между расстояниями errorterm=(fakedist[]][k]-realdist[]][k])/realdist[]][k]

#   Каждую точку следует отодвинуть или приблизить к другой точке

#   пропорционально вычисленному расхождению между ними grad[k][0]+=((loc[k][0]-loc[j][0])/fakedist[]][k])*errorterm grad[k][1]+=((loc[k][1]-loc[j][1])/fakedist[]][k])*errorterm

#   Следим за суммарным расхождением totalerror+=abs(errorterm)

print totalerror

#       Если после перемещения ситуация ухудшилась, завершаем операцию if lasterror and lasterror<totalerror: break lasterror=totalerror

#       Сдвинуть каждую точку на величину, равную скорости обучения,

#       умноженной на градиент for k in range(n):

loc[k][0]-=rate*grad[k][0] loc[k][1]-=rate*grad[k][1]

return loc

Чтобы визуализировать результат, можно снова воспользоваться библиотекой PIL для генерирования изображения, на котором будут нанесены метки всех предметов в точках, где они теперь оказались.

def draw2d(data,labels,]peg=’mds2d.]pg’):

img=Image.new(‘RGB’,(2000,2000),(255,255,255)) draw=ImageDraw.Draw(img) for i in range(len(data)): x=(data[i][0]+0.5)*1000 y=(data[i][1]+0.5)*1000 draw.text((x,y),labels[i],(0,0,0)) img.save(jpeg,’JPEG’)

Для прогона этого алгоритма сначала следует вызвать функцию scaledown для получения двумерного набора данных, а затем draw2d – для его отрисовки.

>> reload(clusters)

>> blognames,words,data=clusters.readfile(‘blogdata.txt’) >> coords=clusters.scaledown(data)

>> clusters.draw2d(coords,blognames,jpeg=’blogs2d.jpg’)

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

Рис. 3.10. Часть двумерного представления пространства блогов

Вы можете следить за любыми ответами на эту запись через 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