GotAI.NET

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

 

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

 Все темы | Новая тема Стр.2 (5)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Иерархическая кластеризация
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 17 май 08 20:58
на сколько я понимаю НомерКластер несколько лишний, Эту информацию легко получить, просто обратившись к точки [х,у-1] и проверив какой у нее класстер.

я правильно понял ваш алгоритм (а то в нем без отступов не могу разобраться)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
function MAIN
classterCounter=1;
for x in XRange do
for y in YRange do
if point[x][y] then
otherClassters = otherClasstersOfNeighbors(x,y)
if otherClassters is empty then
classter = classterCounter = classterCounter + 1
setToClasster(classter,x,y)
else
classter = min(otherClassters)
setToClasster(classter,x,y)
for otherClasster in otherClassters do
mergeClassters(classter,otherClasster)
done
end_if
end_if
done
done
renumberingOfClassters()
done
function otherClasstersOfNeighbors(x,y)
return Array(
classterOf(x-1,y),
classterOf(x,y-1)
)
end
function mergeClassters(classterA,classterB)
// зависит от структиры данных
end
function setToClasster(classter,x,y)
// зависит от структуры данных
end
function classterOf(x,y)
// зависит от структуры данных
end
function renumberingOfClassters()
// зависит от структуры данных
end
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 17 май 08 21:45
У меня идеосинкразия на аглицкий
Видите ли, Варвара не очень ясно описала задачу. Из того, что она обследует восемь соседей, я сделал вывод, что соседние по диагонали тоже входят в один кластер. У вас, как я понял, соседствуют только по вертикали - горизонтали. Наверное, это непринципиально, исправляется в функции otherClasstersOfNeighbors (если я все правильно понял). Но есть другой момент. Вполне возможно, что в одну клетку попадает несколько точек и важно, что они там есть. И в кластер требуется записать координаты именно точек. У меня в итоге получается готовый список кластеров, каждый из списка точек. А у вас массив с номерами, которые еще выбирать надо. Вобщем, от точной формулировки того, что требуется танцевать надо.
ps. а еще есть маленькая экономия при слиянии кластеров: мне менять надо только одну строку, а у вас всю уже пройденную часть массива.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 17 май 08 22:11
QUOTE Автор: Алхимик
Цитата:
У вас, как я понял, соседствуют только по вертикали - горизонтали. Наверное, это непринципиально, исправляется в функции otherClasstersOfNeighbors (если я все правильно понял)

Верно

Цитата:
Вполне возможно, что в одну клетку попадает несколько точек и важно, что они там есть. И в кластер требуется записать координаты именно точек.

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

Цитата:
У меня в итоге получается готовый список кластеров, каждый из списка точек. А у вас массив с номерами, которые еще выбирать надо.

Нет. видите у меня несколько функций отмеченные как "зависит от структуры данных".
Вот эта структура данных, может быть полностью динамической матрицей (т.е. массивом, массивов, или даже списком списков).
Впрочем, вы правы, я вижу, что нет необходимости, в хранении всего массива, и достаточно сделать то, что сделали вы, т.е. хранить только текущую и предыдущую строку этого массива.
Но у меня и небыло цели написать, что-то более эфективное, я просто вообще, задачу пытался понять.

Цитата:
а еще есть маленькая экономия при слиянии кластеров: мне менять надо только одну строку, а у вас всю уже пройденную часть массива.

Да нет, в остальном, все так же как у вас. Т.е. все зависит от структуры данных. Если это список-списков, то вообще, надо поменять несколько указателей, и только текущих соседей, не более. Это тот же алгоритм что и у вас, только чуть больше памяти тратит, очем я уже с вами согласился.
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 17 май 08 23:28
Цитата:
Автор: daner
А вот это я вообще не понял. Т.е. точки сами по себе меньше квадратов? Другими словами, мы не пиксели обходим?

Я так понял из первого поста, что есть некая область с точками (или изображением). Мы произвольно делим эту область на квадраты. Вполне вероятно, что в один квадрат могут попасть несколько точек. Затем строится 0.1 матрица в зависимости от того, есть ли вообще точки в квадрате. Хотя возмозно это я недопонял. Может, меня сбило " разбить область на квадраты (сперва на 4, потом на 16 и т.д.)". Такое сложное сложное деление предполагает, что в области уже что-то есть, какой-то рисунок. Пожоже, что квадрат явно не один пиксель. Хотя может быть отмечается только она точка на квадрат. Тогда действительно нет особой разницы.
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 18 май 08 10:38
В каждом квадрате может быть от одной до нескольких точек. Нужно делить область до тех пор, пока не увеличится требуемая функция F.
00000000
01000110
01000010
01000010
01000010
11111110
00000000
00000000 Здесь один кластер.

А здесь 2
0010
1001
1001
0001
[Ответ][Цитата]
гость
89.208.11.*
На: Иерархическая кластеризация
Добавлено: 18 май 08 12:40
*
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 18 май 08 12:46
Я вывела точки первого кластера, а остальные выдаются неправильно. Помогите, пожалуйста, исправить ошибку
http://ifolder.ru/6611162
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 19 май 08 9:23
Не, я пас. Вижу, что вы все равно по своему хотите сделать. А я не настолько помню Паскаль( с Делфи вообще дела не имел), чтобы без коментариев разобраться во всем этом. Слишком много переменных. Вот мне просто любопытно: для чего служат x0 и y0 в следующей функции
procedure TfrmMain.Button5Click(Sender: TObject);
var x,i,j,y,x0,y0,h:word;
begin
n:=4;
x0:=0;
y0:=0;
h:=image1.Width div n;
for j:=0 to n-1 do begin
x:=x0+j*h;
for i:=0 to n-1 do begin
y:=y0+i*h;
//showmessage(inttostr(pts.points(l).xx)+'';''+inttostr(pts.points(l).yy)+'';''+inttostr(x)+'';''+inttostr(y)+'';h ''+inttostr(h)+'' ''+inttostr(PInR(pts.points(l).xx,pts.points(l).yy,x,y,h)));
a[j,i]:=PInR(x,y,h);
//showmessage(inttostr(a[j,i]));
end;
end;
{for i:=0 to n-1 do
for j:=0 to n-1 do begin
showmessage(''(''+inttostr(i)+'';''+inttostr(j)+'')=''+inttostr(a[j,i]));
end;}
end;
Может, я не понимаю их смысла из-за незнания языка программирования? Объясните.
[Ответ][Цитата]
Corwin
Сообщений: 1324
На: Иерархическая кластеризация
Добавлено: 19 май 08 15:26
>а остальные выдаются неправильно.

Ну при беглом просмотре выдаются действительно неправильно поскольку ссылаетесь не к тому элементу массива (собственно зачем там вообще массив?)
У Вас:
C[k].x:=Pts.Points(l).xx;
C[k].y:=Pts.Points(l).yy;
frmMain.memF.Lines.Add(''X=''+inttostr(C[0].x)+''; Y=''+inttostr(C[0].y));
Должно быть (наверное)
frmMain.memF.Lines.Add(''X=''+inttostr(C[k].x)+''; Y=''+inttostr(C[k].y));

Всеравно не понимаю метод которым Вы хотите добиться кластеризации...
[Ответ][Цитата]
varvara
Сообщений: 29
На: Иерархическая кластеризация
Добавлено: 19 май 08 17:36
Я убрала x0 и y0. Они, действительно, были не нужны: http://ifolder.ru/6628200 Спасибо огромное за алгоритм. Извините, что пока его не использую, просто я хочу попробовать свой. Я уже столько над ним мучаюсь. А как можно собрать полученные результаты в отдельные массивы, чтобы вычислить функцию F=F1+F2+F3?

function F1(ClsNo: Byte): single;
var
i,j: word;
s: single;

begin
s := 0;
for i := 1 to Cl.Clusters(ClsNo).Count-1 do
for j := i+1 to Cl.Clusters(ClsNo).Count-1 do
s := s + Cl.Clusters(ClsNo).Points(i).Dist(Cl.Clusters(ClsNo).Points(j));
Result := s;
end;

function F2(ClsNo: Byte): single;
var
i: word;
s: single;

begin
s := 0;
for i := 1 to Cl.Clusters(ClsNo).Count-1 do
s := s + Cl.Clusters(ClsNo).Points(0).Dist(Cl.Clusters(ClsNo).Points(i));
Result := s;
end;

function F3: single;
var
i,j: word;
s: single;

begin
s := 0;
for i := 0 to Cl.Count-1 do
for j := i+1 to Cl.Count-1 do
begin
if Cl.Clusters(j).Count = 1 then continue;
s := s + Cl.Clusters(i).Points(0).Dist(Cl.Clusters(j).Points(0));
end;
Result := s;
end;
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 19 май 08 21:55
Похоже, я разобрался, как ты хочешь организовать поиск кластеров.
По моему надо так:

for y=0 to n-1
...for x=0 to n-1
......if a(x,y)=1 then
.........записать a(x,y) в массив единиц pt
.........k:=1
.........do while k<= length(pt)
............добавить в массив pt тех соседей pt(k) из матрицы a, которые
............равны 1 и еще не входят в pt (только просматривать соседей
............по четырем направлениям (вправо,вправо-вниз, вниз, влево-вниз);
............по остальным бесмысленно - придут к уже просмотренным. Массив
............для нулей fc вообще не нужен
............k:=k+1
.........loop
.........записать точки в очередной кластер
.........все элементы pt в матрице a приравнять к 2 (то, что ты и делала)
.........очистить pt
......end if
...next x
next y

Тебя запутал масив для нулей, не нужен он вообще. У тебя все части есть в TfrmMain.Button3Click, осталось только перекомпановать и лишнее выбросить.

О функциях f1 и пр. объясни подробней, для чего они, что ты хочешь получить.

ps. function PInR - забавен exit в конце функции. Там вобще не нужна ветка else: или будет выход по еденице в теле цикла; или в в конце значение функции приравнять к 0. Для этого переменная c тоже не нужна, зачем эта двухэтажность.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 20 май 08 3:24
>>>>Алхимик
С отступами, ваш алгоритм выглядит куда читабельнее (шутка, хотя и не совсем)

Ну на сколько я понял, алгоритм который вы описали, это просто обход всех точек и если точка еще не принадлежит кластеру, устроить полный обход кластера методом BFS.
Что получается накладно с точки зрения complexity. (хотя... считать надо, может быть и нет...хотя, нет, все-же больше из-за дополнительных проверок на вхождение в pt).

я только не пойму, а где здесь деление вначале на 4 квадрата, потом на 8 и т.д.
или я что-то не правильно понял?

[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 20 май 08 8:05
Цитата:
Автор: daner
Ну на сколько я понял, алгоритм который вы описали, это просто обход всех точек и если точка еще не принадлежит кластеру, устроить полный обход кластера методом BFS.
Что получается накладно с точки зрения complexity. (хотя... считать надо, может быть и нет...хотя, нет, все-же больше из-за дополнительных проверок на вхождение в pt).

Я в курсе, экономичнее того, что я предлагал раньше, наверное, нет (имхо). Но я просто иду навстречу желанию Варвары. Это в духе того, что она пыталась написать. Минут за десять копипастом можно перекроить то, что у нее уже написано и будет работать.
Цитата:
Автор: daner

я только не пойму, а где здесь деление вначале на 4 квадрата, потом на 8 и т.д.
или я что-то не правильно понял?


А оно в другой функции, где матрица a изединиц и нулей образуется. Пока делится только на 16 квадратов, Варвара застряла на обходе этих 16 квадратов. Я как раз у нее и пытаюсь выяснить, какова конечная идея всего этого, что в конечном итоге должно получиться.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Иерархическая кластеризация
Добавлено: 20 май 08 12:55
Цитата:
Автор: Алхимик
А оно в другой функции, где матрица a из единиц и нулей образуется. Пока делится только на 16 квадратов, Варвара застряла на обходе этих 16 квадратов.

т.е. получается несколько кластеризаций между собой не связанных? кластеры от деления на 4, на 8 и т.д. Как то с трудом улавливаю. Получается, что даже теоретически у деления на 4 и 8, обязательно будет только 1 кластер.
[Ответ][Цитата]
Алхимик
Сообщений: 315
На: Иерархическая кластеризация
Добавлено: 20 май 08 15:43
Цитата:
Автор: daner
т.е. получается несколько кластеризаций между собой не связанных? кластеры от деления на 4, на 8 и т.д. Как то с трудом улавливаю. Получается, что даже теоретически у деления на 4 и 8, обязательно будет только 1 кластер.


Все зависит от плотности точек, если густо то кластер не распадется, если редко, то может распасться на несколько мелких. А связываться разбиения будут поведением некой функции F, считаемой на кластерах разбиения. Как я понимаю, это проба - пока без начала и без конца. Человек хочет посмотреть, как будет вести себя некая сложная функция, оправдаются ли его предположения или нет. Нас просто попросили помочь решить частный вопрос. А что должно получится в итоге - может узнаем, может нет.
[Ответ][Цитата]
 Стр.2 (5)1  [2]  3  4  5<< < Пред. | След. > >>