GotAI.NET

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

 

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

 Все темы | Новая тема Стр.3 (5)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Иерархическая кластеризация
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 20 май 08 16:14
Цитата:
Автор: Алхимик
Все зависит от плотности точек, если густо то кластер не распадется, если редко, то может распасться на несколько мелких.

Это как? Как у вас может получиться при разбиение на 4 клетки несколько кластеров.
Ну только если учитывать, что по диагонали не считать соседями... тогда да.
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 20 май 08 17:22
Мне нужно при каждом делении вычислять функцию. Если ее значение при последующем делении стало больше предыдущего, то прекращаем процесс. Функция равна сумме квадратов расстояний между точками внутри каждого кластера, т.е. sqr(x[i]-x[j]), + сумма квдратов расстояний между цетрами кластеров и точками этих же кластеров sqr(x[i]+o[i]) и сумме квадратов расстояний между центрами кластеров sqr(o[i]-o[j]). Центр кластера-это среднее арифметическое точек кластера.
Помогите, пожалуйста, с отделением каждого кластера в отдельный массив для вычисления функции.
А при делении на 4 может получиться только один кластер, а при 16 - не более 4.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 20 май 08 17:30
Цитата:
и сумме квадратов расстояний между центрами кластеров sqr(o[i]-o[j])

А это зачем?
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 20 май 08 17:31
Я сама не знаю, но мне сказали, чтобы вычислялась именно эта функция.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 20 май 08 17:41
ну вообще, теперь алгоритм более или менее встал на свои места (в моей голове). правда это нельзя назвать Иерархическая Кластеризация... скорее Кластеризация с Повышением Резолюции. Да и результат, не особо качественный получится,... хотя буду приятно удивлен, если ошибаюсь.

Жаль не могу помочь в прикладном плане... не знаком с Delphi. Но в принципе, если у вас есть кластер и вы можете его распечатать, в чем проблема перевести его в массив?
[Ответ][Цитата]
гость
89.208.11.*
На: Иерархическая кластеризация
Добавлено: 20 май 08 21:25
варвара, поищите помощь в ругом месте. сть куча профессиональных форумов. здесь народ

* (admin: гость, если вам нечего сказать, - это не повод для употребления нецензурной лексики)

Ничего ценного они вам не могут сообщить по определению.
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 21 май 08 12:59
Не знаю как вам, но на этом форуме мне во многом помогли. Пожалуйста, посмотрите мой код, что я делаю не так?

procedure TfrmMain.Button3Click(Sender: TObject);
var
x1,y1:byte;
x,y,i,j,l,k,m:integer;
begin
memF.Clear;
y := 0; k:=1; m:=1;
setlength(pt,1);
repeat
for x:=0 to n-1 do begin

if (a[x,y]=1) and (PInM(x,y,pt)=FALSE)then begin
pt[length(pt)-1].X:=x;
pt[length(pt)-1].y:=y;

if (a[x-1,y-1]=1) and (PInM(x-1,y-1,pt)=FALSE) then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x-1;
pt[length(pt)-1].y:=y-1; end;
if (a[x+1,y-1]=1) and (PInM(x+1,y-1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x+1;
pt[length(pt)-1].Y:=y-1; end;
if (a[x-1,y]=1) and (PInM(x-1,y,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x-1;
pt[length(pt)-1].y:=y; end;
if (a[x+1,y]=1) and (PInM(x+1,y,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x+1;
pt[length(pt)-1].Y:=y; end;
if (a[x-1,y+1]=1) and (PInM(x-1,y+1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x-1;
pt[length(pt)-1].y:=y+1; end;
if (a[x,y+1]=1) and (PInM(x,y+1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].x:=x;
pt[length(pt)-1].y:=y+1; end;
if (a[x+1,y+1]=1) and (PInM(x+1,y+1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x+1;
pt[length(pt)-1].y:=y+1; end;
end;
end;
for i:=0 to pts.Count-1 do begin
x1:=pt[i].X; y1:=pt[i].Y;
if (a[x1-1,y1-1]=1) and (PInM(x1-1,y1-1,pt)=FALSE) then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1-1;
pt[length(pt)-1].y:=y1-1; end;
if (a[x1+1,y1-1]=1) and (PInM(x1+1,y1-1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1+1;
pt[length(pt)-1].Y:=y1-1; end;
if (a[x1-1,y1]=1) and (PInM(x1-1,y1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1-1;
pt[length(pt)-1].y:=y1; end;
if (a[x1+1,y1]=1) and (PInM(x1+1,y1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1+1;
pt[length(pt)-1].Y:=y1; end;
if (a[x1-1,y1+1]=1) and (PInM(x1-1,y1+1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1-1;
pt[length(pt)-1].y:=y1+1; end;
if (a[x1,y1+1]=1) and (PInM(x1,y1+1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].x:=x1;
pt[length(pt)-1].y:=y1+1; end;
if (a[x1+1,y1+1]=1) and (PInM(x1+1,y1+1,pt)=FALSE)then begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1+1;
pt[length(pt)-1].y:=y1+1; end;
end;
frmMain.memF.Lines.Add(''Cluster #''+IntToStr(k));

for l:=0 to pts.count-1 do begin
for i:=0 to length(pt)-1 do
if PInR1(pts.points(l).xx,pts.points(l).yy,(pt[i].X)*h,(pt[i].Y)*h,h)=true then begin
cl.Clusters(0).Add(Pts.Points(m-1));
end;
inc(m);
end;
for i:=0 to m do begin
showmessage(''X=''+inttostr(cl.Clusters(k).points(i).xx)+''; Y=''+inttostr(cl.Clusters(k).points(i).yy));
end;
for i:=0 to length(pt)-1 do begin
a[pt[i].X,pt[i].Y]:=2; end;
setlength(pt,1);
inc(k);
pt[length(pt)-1].X:=0;
pt[length(pt)-1].y:=0;
y:=y+1;
until y>n-1;
end;
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 21 май 08 14:39
>>>>varvara
почему бы вам не выделить свою программу тагами
[code]
А здесь программа.
[/code]


Смотреться будет удобней, быстрее ответ получите.
[Ответ][Цитата]
Mad_God
Сообщений: 545
На: Иерархическая кластеризация
Добавлено: 21 май 08 16:17
Теперь объясните и для меня, нерадивого.

Насколько я понял нужно сделать следующее:

1. Разбросать по массиву [Х,У] нули и единицы
2. проверять массив на наличие единиц
3. создать массив с координатами нулей
4. создать массив с координатами единиц
5. проверять, какому кластеру принадлежит каждая единица в массиве единиц
5.1 создать вспомогательный массив единиц
5.2 проверить, есть ли у данной точки соседи
5.3 если есть соседи - все они принадлежат одному кластеру
6. повторять пункт 5 пока в массиве неповеренных точек не останется елементов
7. повторить то же самое если нужно для массива нулей

есть ли у данной точки соседи:
1 создаём динамически заполняемый массив из координат восьми точек, которые окружают данную
2 Проверяем, принадлежат ли координаты этих восьми точек массиву единиц.
3 Если хоть одна координата принадлежит - кластер продолжается
4 Включаем всех соседей в один кластер
5 Исключаем проверенные точки из вспомогательного массива единиц
6 Берём следующую точку из вспомогательного массива единиц из которого исключили добавленные точки


создать несколько диапазонов - 4, 8, 16
проверять, в какой из диапазонов входит кластер
если кластер куда-то входит - исключить его из списка проверяемых в дальнейшем.
Хотя тут возможны варианты: кластер может входить в несколько диапазонов-квадратов

я прав?
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 21 май 08 17:05
Цитата:
Автор: Mad_God
создать несколько диапазонов - 4, 8, 16
проверять, в какой из диапазонов входит кластер
если кластер куда-то входит - исключить его из списка проверяемых в дальнейшем.


если я правильно понял, то никакой связи между 4, 8, 16 и т.д. нет.
т.е. сделали на 4, проверили, все ли кластеры устраивают (делаем это по заданной функции), если нет, то увеличиваем резолюцию и начинаем все с самого начала.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Иерархическая кластеризация
Добавлено: 21 май 08 17:26
Е.Тарасов> поищите помощь в ругом месте. сть куча профессиональных форумов.

Конечно есть Вот Вы Е.Тарасов и валили бы туда.... Вам бы больше всего подошли (проф места) "Я и моя паранойя", "Завладеть миром за 10 дней", "ИИ чужими руками".

П.С.
Есть один довольно неплохой и простенький пример 2Д кластеризации написанный на Делфи:
Cluster
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 21 май 08 18:54
Спасибо за программу. А почему же не создаются массивы cl.clusters(i).pts.points(j)? А где нужно наращивать k, чтобы правильно выводилась надпись Cluster #...
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 21 май 08 19:35
Цитата:
Автор: varvara

Спасибо за программу. А почему же не создаются массивы cl.clusters(i).pts.points(j)? А где нужно наращивать k, чтобы правильно выводилась надпись Cluster #...


На сколько можно понять ваш код в котором даже отступов нет!!!!
Вы все это делаете для каждой строчки заново. ну и даже если так, то надо отдельный цикл для прохода по кластерам.

Кроме того, откуда берется массив pts???? Может я конечно не понимаю delphi, но инициализация то должна быть.

Было бы не плохо, если бы кроме отступов, вы еще и комментарии (причем подробные) писали, чуть ли не на каждую строку. Тогда было бы сразу видно, где паскаль расходиться с желаемым.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Иерархическая кластеризация
Добавлено: 21 май 08 22:19
Немножко модифицировал Ваш код
Varvara cluster
Несколько замечаний
1. Следите чтобы индексы массива не вылезали за размер массива, поскольку формальной ошибки Вы не получите, а в алгоритме полный бардак будет.
2. расставляйте переносы, а то у вас Енды от циклов иногда не в тех местах стояли.
3. У вас в коде используется что-то типа:
var i:word;
begin
for i:=0 to n-1 do

Смысл в том что i - не может быть отрицательным (тип word (unsigned)) поэтому если n=0 тогда цикл "for i:=0 to n-1 do" буде считаться как "for i:=0 to 65535 do" Так что либо используйте signed числа (тип Integer (signed)) либо проверяйте условие цикла:
if n>0 then
for i:=0 to n-1 do
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 22 май 08 0:51
Варвара, извините, я в прошлом посте зарапортовался. Действительно, надо всех восемь соседей просматривать. Но Данер прав, незачем их столько раз писать, оформите в виде цикла

procedure TfrmMain.Button3Click(Sender: TObject);
var
x1,y1:byte;
x,y,i,k,l,m,n:integer;
begin
memF.Clear;
y := 0;
k:=0;{это номер очередного кластера, который будет заполнятся}
setlength(pt,1);
repeat
for x:=0 to n-1 do
begin
if (a[x,y]=1) and (PInM(x,y,pt)=FALSE)then
begin
pt[length(pt)-1].X:=x;
pt[length(pt)-1].y:=y;
i:=0
repeat
x1:=pt[i].X; y1:=pt[i].Y;
for l=-1 to 1
for m=-1 to 1
if not(l=0 and m=0) then
if (a[x1+l,y1+m]=1) and (PInM(x1+l,y1+m,pt)=FALSE)then
begin
setlength(pt,length(pt)+1);
pt[length(pt)-1].X:=x1+l;
pt[length(pt)-1].Y:=y1+m
end;
inc(i);
until i=length(pt);
{в массиве pt собраны все квадраты очередного кластера;
теперь нужно переписать точки из этих квадратов в кластер
с номером k. И также записать точки в memF. Тут я вряд ли помогу,
потому что с трудом понимаю твои классы}
ink(k)
for i:=0 to length(pt)-1 do a[pt[i].X,pt[i].Y]:=2;
setlength(pt,1);
end;
end;
y:=y+1;
until y>n-1;
end;

А зачем вообще классы вводились? Можно же было обойтись динамическими массивами , понятней было бы. А то не пойму никак. Прокоментируй этот кусок:
for l:=0 to pts.count-1 do begin
for i:=0 to length(pt)-1 do
if PInR1(pts.points(l).xx,pts.points(l).yy,(pt[i].X)*h,(pt[i].Y)*h,h)=true then begin
cl.Clusters(0).Add(Pts.Points(m-1));
end;
inc(m);
end;


[Ответ][Цитата]
 Стр.3 (5)1  2  [3]  4  5<< < Пред. | След. > >>