Microsoft Word Master thesis of Petar Kormushev in Medical Informatics doc
Изтегляне 2.9 Mb. Pdf просмотр
|
Свързани:
1601561030 Dobrinka Bogdanova
| 3.2. Основа на визуализацията Клъстеризацията е основен елемент в много подходи за извличане на закономерности от данни. За съжаление, резултатите от нея трудно могат да се възприемат от човек, когато данните са многомерни и разнородни. Това се случва когато обектите, които се клъстеризират, имат много характеристики, едни от които непрекъснати, а други – номинални и без наредба. Възниква необходимостта от визуално представяне на множеството от обекти и клъстерите, към които те принадлежат. За основа на визуализацията в настоящата дипломна работа е избран алгоритъмът FastMap. Той е много удобен за визуализация и клъстерен анализ на многомерни данни. В този конкретен случай целта ни е оригиналните медицински данни да се проектират в двумерното пространство, като принадлежността към всеки клъстер да се маркира с фиксиран цвят по избрана цветова легенда. Други допълнителни ползи, които могат да се извлекат от една такава визуализация, са: • Да се визуализира удобно резултатът от работата на някой алгоритъм за клъстеризация, за да се оцени от човек неговото качество. • Да се прогнозира принадлежността на нов обект към вече съществуващите клъстери. • Да се визуализират подходящо некласифицирани данни, за да може човек интуитивно да определи на колко клъстера ще е удачно да се клъстеризират данните от друг алгоритъм. За основа на реализацията е използвано оригиналното описание на алгоритъма FastMap от авторите Zhexue Huang и Tao Lin. Описанието е взето от тяхната статия „A Visual Method of Cluster Validation with FastMap”. 3.3. Алгоритъм FastMap Алгоритъмът FastMap решава задачата за проектиране на N обекта, за които е известна N x N матрицата на взаимните разстояния, в N точки в k-мерно пространство по начин, запазващ (до голяма степен) съответствията в разстоянията между обектите. Решаването на задача за проектиране на N n-мерни обекта в N k-мерни обекта, където k ≤ n, е частен случай на тази по-обща задача. Вместо матрица на взаимните разстояния може да бъде използвана някаква мярка за разстояние между два обекта, дефинирана като функция D(A, B) := разстоянието между обектите A и B. В оригиналната версия на алгоритъма се използва Евклидово разстояние, но за нашите нужди ще дефинираме по-различни мерки за разстояние, които са съобразени с типовете на атрибутите от медицинските извадки. При условие, че разполагаме с изчислени взаимни разстояния между обектите в оригиналното n-мерно пространство, намирането на проекциите на обектите в редуцирано k-мерно пространство се осъществява рекурсивно за k стъпки. На всяка стъпка се осъществяват следните действия: 41 1. Избират се два опорни (pivot) обекта O a и O b . Линията, която минава през тях, се разглежда като първата ос на търсеното k-мерно пространство. 2. За всеки обект O i неговата координата x i по тази ос се изчислява по следната формула: (1) където d a,b е разстояние между O a и O b , d a,i и d b,i са разстояния между O i и O a и O b , съответно, които са вече изчислени (предварително или на предишната стъпка от рекурсията). Тази формула следва от косинусовата теорема и е илюстрирана на фигура 3.1. Фигура 3.1. Прилагане на косинусовата теорема за проектиране върху правата O a O b 3. За да бъдат изчислени координатите на обекти по следващата (в примера - втора) ос е необходимо предварително да бъдат преизчислени взаимните разстояния между всички обекти в намаленото (в случая n-1-мерно) пространство. Тези разстояния се изчисляват на базата на разстоянията в текущото пространство (в примера n-мерното) и координатите на обектите върху предишната (в случая – първата) ос по следната формула, която е следствие от Питагоровата теорема: (2) където е разстояние между обектите O i и O j в редуцираното пространство, е разстоянието между обектите O i и O j в оригиналното (от предишната стъпка) пространство, а x i и x j са координати на съответните обекти върху първата (предишната) ос. По същество тази стъпка представлява проектиране на n-мерните обекти върху (n-1)-мерна хипер-равнина H, така както е илюстрирано на фигура 3.2. 42 Фигура 3.2. Проектиране върху хипер-равнина H, перпендикулярна на правата O a O b Описаните три точки се повтарят рекурсивно докато не бъдат изчислени координати на всички обекти върху k-тата координатна ос. Опорните обекти O a и O b се избират по такъв начин, че да максимизират разстоянието D(O a , O b ). За да намали броя на необходимите за тази цел изчисления, които са O(N 2 ), авторите използват следния евристичен алгоритъм със сложност O(N) само за избор на опорни обекти: Алгоритъм избери_обекти(O, D()) Изтегляне 2.9 Mb. Сподели с приятели:
|