GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (5)След. > >>   Поиск:  
 Автор Тема: Иерархическая кластеризация
varvara
Сообщений: 29
Иерархическая кластеризация
Добавлено: 11 май 08 10:50
Здравствуйте. Помогите, пожалуйста, с реализацией этого алгоритма. Сперва нужно взять область, потом разбить ее на квадраты (сперва на 4, потом на 16 и т.д.). Нужно задать точки. Определить принадлежность точки квадрату(т.е. создать матрицу, состоящую из нулей и единиц). Начать обход матрицы: если ноль, то создаем динамический массив и сохраняем туда адрес элемента, если 1, то сохраняем 1 в другой динамический массив и начинаем проверять соседей для 1. Если среди них есть нули, то записываем их координаты в массив с нулями, а единицы во второй массив. Затем обход продолжаем со второго элемента массива единиц. Обходим ее соседей и т.д. Пока не закончатся единицы. Единичные элементы содержат точки, их нужно записать в первый кластер.
Я разбила область на 16 квадратов и сделала матрицу из нулей и единиц. Помогите, пожалуйста, реализовать обход на Delphi.
Вот то, что у меня получилось
http://ifolder.ru/6509383

Заранее благодарю.
[Ответ][Цитата]
гость
81.176.22.*
На: Иерархическая кластеризация
Добавлено: 12 май 08 21:19
* (admin: если нечего сказать, то незачем грубить)
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 12 май 08 21:26
фууу как не красиво.

Если бы не делфи, я наверное постарался бы помочь.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Иерархическая кластеризация
Добавлено: 13 май 08 15:26
Я вообще не очень понял что из этого должно получиться...
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 13 май 08 20:22
Нужно получить отдельные островки(кластеры) и вывести входящие в них точки.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 13 май 08 20:59
проблема в самом алгоритме? или в его реализации на Дельфи?
Если в алгоритме, то пишите его на псевдокоде и тогда можно попробовать разобраться.
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 16 май 08 17:25
Проблема в реализации на Дельфи. Я выделила квадраты входяцие в кластер. А как теперь выделить точки? Помогите, пожалуйста, с обходом.
http://ifolder.ru/6590127
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Иерархическая кластеризация
Добавлено: 17 май 08 3:23
Опишите нормально сам метод кластерзации, а то с алгоритма мало что понятно. У вас получаеться что кластер формируеться границами квадрата и не будет выходить за его пределы?
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 17 май 08 8:31
Обход начинается так:
Берем первую строку при y=0. Увеличиваем х от 0 до n-1 (т.е. до 3).
(*) If x=0 then создаем динамический массив пустых кубов (записываем номера элементов матрицы). Продолжаем это, пока x не станет равен 1. Если 1, то записываем адрес ячейки в массив с единицами. Теперь начинаем проверять все восемь соседних ячеек. Если ячейка равна 1, то записываем ее адрес в массив с единицами, если 0, то в массив с нулями. Теперь начинаем обход динамического массива с адресами единичных квадратов. Проверяем, нет ли уже этого элемента в массиве, если находим 1, то обходим ее соседей и добавляем ее соседние единичные элементы в массив, а нули – в массив с нулями (без повторений). Продолжаем этот процесс, пока не закончатся элементы в массиве. Теперь определяем точки, входящие в квадраты, адреса которых находятся в массиве единиц, и создаем первый кластер. Теперь обнуляем массив единиц. Возвращаемся к ячейке с первой 1 и переходим на следующую ячейку. Затем наращиваем y, и возвращаемся к (*).Так обходим все ячейки и выделяем кластеры.

Сам метод заключается в разбиении области, в которой расположены точки. Если квадраты с точками соприкасаются, то эти точки входят в один кластер. Если они отделены друг от друга пустыми ячейками, то это разные кластеры.
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 17 май 08 11:55
А зачем так сложно? Можно ведь за один проход сделать. Создать динамический массив кластеров Кластер(). Создать массив НомерКластер(0 to n-1) (вначале там нули). Создать переменную ТекКластер (начальное значение ноль).
for y=0 to n-1
for x=0 to n-1
if (куб нулевой) then
ТекКластер=НомерКластер(x)
НомерКластер(x)=0
else
if ТекКластер>0 then
Записать все точки куба в текущий кластер
if НомерКластер(x+1)>0 and НомерКластер(x+1)<>ТекКластер
Объеденить все точки кластера с номером, хранящимся
в НомерКластер(x+1) с точками кластера с текущим номером;
в массисе номеров поменять все номера со значением,
равным ТекКластер на значение НомерКласте(х+1);
ТекКластер=НомерКластер(x+1);
в масиве кластеров удалить последний кластер
end if
else
if НомерКластер(x)>0 then
ТекКластер=НомерКластер(x)
elseif x<n-1 then
if НомерКластер(x+1)>0 then
ТекКластер=НомерКластер(x+1)
НомерКластер(x)=ТекКластер
tnd if
end if
if ТекКластер>0 then
Записать все точки куба в текущий кластер
else
Добавить в массив кластеров новый кластер
и записать все точки куба в него;
в ТекКластер записать номер этого нового кластера;
НомерКластер(x)=ТекКластер
end if
end if
end if
next x
ТекКластер=0
next y

[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 17 май 08 11:57
Блин, все отступы съело.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 17 май 08 15:03
Цитата:
Автор: Алхимик

Блин, все отступы съело.

если не ошибаюсь, работает таг [_code][/_code] ("_" убрать), а так же, можно ставить точки
if xxxxxxx then
....xxxxxxxxx
....xxxxxxxxx
end_if

или с тагом
if xxxxxxx then
xxxxxxxxx
xxxxxxxxx
end_if
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 17 май 08 19:05
А как же с обходом соседних клеток? Ведь некоторые точки могут соединиться через несколько строк.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 17 май 08 19:12
Цитата:
Автор: varvara

А как же с обходом соседних клеток? Ведь некоторые точки могут соединиться через несколько строк.

просто интересно а вот такой узор, сколько кластеров из себя представляет? Два или Один?

00000000000000
01111000011110
01111000011110
01111111111110
01111000011110
01111000011110
00000000000000
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 17 май 08 20:05

Цитата:
Автор: varvara

А как же с обходом соседних клеток? Ведь некоторые точки могут соединиться через несколько строк.

Так для того и нужен массив номеров.Он содержит номера кластеров для предыдущей строки. Допустим, вы разбираете картинку, которую нарисовал Данер.После первой строки у вас два кластера, образуемые ножками буквы Н. Когда вы доходите до перекладинки, то все еще есть два кластера. Значение ТекКластер равно 1 (первый кластер). Когда вы доходите до того места, где перекладинка сливается со второй ножкой, значение ТекКластер по прежнему 1, а значение НомерКластер(x+1)=2 (второй кластер- вторая ножка). В этом случае по алгоритму вы сливаете второй кластер с первым и удаляете второй. А также меняете все двойки на единицы в массиве НомерКластер. И то, что затем ножки буквы н опять расходятся, не приводит к появлению нового кластера - единицы в массиве НомерКластер заставят вас отнести все единицы в один кластер. Получается, что вы образуете новый кластер только тогда, когда появляется изолированная единица - нет соседа слева и по диагонали сверху слева (ТекКластер=0) и соседа сверху (НомерКластер(x)=0); соседа сверху справа (НомерКластер(x+1)=0). Этот новый кластер будет существовать, пока не соприкоснется с другим (текущий номер отличен от номера соседа сверху справа). В этом случае произойдет слияние кластеров. (Если он соприкоснется сам с собой, ничего не происходит, но появляется возможность существования внутренних областей). Или кластер ограничиваесся нулями (соответствующие элементы массива НомерКластер получаю значение 0). В этом случае кластер остается в конечном списке.
Надеюсь, так понятние. Если нет, спрашивайте.
PS. Вышеприведеный алгоритм выделяет только области с единицами. Если нужно выделять и кластеры с нулями, то нужно ввести еще один массив НомерКластер и Тек Кластер для нулей и аналогичные действия для нулей при пом же самом проходе по клеткам.
[Ответ][Цитата]
 Стр.1 (5): [1]  2  3  4  5След. > >>