Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Системи автоматизованого проектування
Інформація про роботу
Рік:
2009
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК
ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Кафедра “Системи автоматизованого проектування”
ЗВІТ
до лабораторної роботи №4
на тему
«ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ “ІСОМАД (ISODATA)”»
з курсу
«Системи штучного інтелекту»
Львів-2009
1.Мета роботи
Вивчити основні принципи роботи алгоритму розпізнавання образів ІСОМАД.
Короткі теоретичні відомості
2.1. Алгоритм ІСОМАД
Крок 1
Задаються параметри, що визначають процес кластеризації:
К - необхідна кількість кластерів;
- параметр, з яким порівнюється кількість вибіркових образів, що ввійшли в кластер;
- параметр, що характеризує середньоквадратичне відхилення;
- параметр, що характеризує компактність;
L - максимальна кількість пар центрів кластерів, які можна об’єднати;
І - допустима кількість циклів і ітерацій.
Крок 2
Задані N образів розподіляються по кластерах, що відповідають вибраним початковим цетрам за правилами
якщо i=1,2, ... , Nc ,
Крок 3
Ліквідуються підмножини образів, в склад яких входять менше елементів, т.б. якщо для деяког j виконується умова Nj< , то підмножини Sj виключається із перегляду і значення Nc зменшується
по 1.
Крок 4
Кожен центр кластера Zj , j =1,2, ... , Nc, локалізується і коректується
j=1,2, ... ,Nc
де Nj - число об’єктів, що ввійшли в підмножину Sj.
Крок 5
Обчислюється середня відстань між об’єктами, що входять в підмножину , і відповідним центром кластера за формулою:
, j=1,2,...,.
Крок 6
Обчислюється узагальнене середня відстань між об’єктами, що знаходяться в окремих кластерах, і відповідними центрами кластерів за формулою:
Крок 7
а) Якщо біжучий цикл ітерації - останній, то задається ; перехід до 11.
б) Якщо умова виконуєтьяс то перехід до кроку 8.
в) Якщо біжучий цикл ітерацій має перший порядковий номер, або виконується умова , то перехід на крок 11; інакше крок 8
Крок 8
Для кожної підмножини вибіркових образів за допомогою співвідношення:
, і=1,2,..., n; j=1,2,...,
вираховуєтьяс вектор середньоквадратичного відхилення
, де n є розмірність образа,
Хik є і-ю компонентою к-го об’єктів підмножини
Sj, Zij є і-ю компонентою вектора, що представляє центр кластера Zj , i Nj - кількість вибіркових образів, включених в підмножину Sj. Кожна компонента вектора середнього квадратичного відхилення характеризує середньоквадратичне відхилення образу, що входить в півмножину Sj, по одній із головних осей координат.
Крок 9
В кожному векторі середньоквадратичного відхилення , j=1,2,...,Nc, виконуються умови мах > і
а)
або
б) ,
то кластер з центром Zj розщеплюється на два повних кластера з центрами і відповідно, кластера із центром ліквідується, а значення збільшується на 1. Для визначення центра кластера до компонент вектора , що відповідає максимальній компоненті вектора , додається задана величина ; центр кластера визначається відніманням цієї ж величини із цієї компоненти вектора Z,
Якщо розщеплення відбувається на даному кроці, то перейти на крок 2, інакше крок 11.
Крок 11
Вираховується відстані між усіма парами центрів кластерів
Крок 12
Відстані порівнюються з параметрами . Ті < вітдалей, які виявилися меншими за ранжуються в порядку зростання
;
Причому , а L - max кількість пар центрів кластерів, які можна об’єднати.
Крок 13
Кожна віддаль Dieje вирахувано для певної пари кластерів із центрами Zil Zjl. До цих пар послідовності, що відповідає збільшенню відстані між центрами, застосовується процедура злиття:
кластери з центрами Zil і Zjl, l=1,2,...,L, об’єднуються (при умові, що в біжучому циклі ітерації процедура злиття не застосовувалася ні до того, ні до іншого кластера), причому новий центр кластера визначається за формулою
Центри кластерів Zil i Zjl ліквідуються і значення Nc зменшується по1.
Допускається лише попарне злиття кластерів і центр отриманого в результаті кластера розраховується, виходячи із позицій,що займаються центрами об’єднаних кластерів і взятих із вагами, визначеними кількістю вибіркових образів у відповідному кластері.
Крок 14
Якщо біжучий цикл ітерації - останній, то виконання алгоритма припиняється. Інакше вертається на крок 1, якщо користувач які не є один із параметрів, чи на крок 2. Завершенням циклу ітерації вважається кожен перехід до кроків 1 або 2.
Індивідуальне завдання
Варіант №11:
К = 3; = 2; = 1; =4; L = 1; І =5.
4.11. Х1(0,3), Х2(2,2), Х3(2,3), Х4(2,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(8,4), Х9(8,5), Х10(9,4), Х11(9,5), Х12(9,9).
Текст програми
function [Z, Xcluster, Ycluster, A, cluster] = isodata(X, Y, k, L, I, ON, OC, OS, NO, min);
s=size(X);
s=s(2);
cluster=zeros(1,s); % Espacio temporal interno de la funcion.
iter=0;
final=0;
vuelve3=0;
A=1; % Lo inicializamos para el primer caso.
primeravez=1; % Para en el primer cilo del while no nos pida la modificacion de parametros.
Z= inicializa_centros(X, Y, A);
while final==0, %inicio del bucle de iteraciones.
if primeravez==0,
if vuelve3==0,
[Ltemp, Itemp, ktemp, ONtemp, OCtemp, OStemp]=parametros(L, I, k, ON, OC, OS, iter);
end;
end;
primeravez=0;
vuelve3=1;
for i=1:s,
cluster(i)=cercano(X(i), Y(i), Z, A);
end;
[Z, A, cluster]=eliminar(A, cluster, Z, X, Y, ON);
Z=recalcula(cluster, X, Y, A, Z);
if (iter==I),
final=1;
next=0;
else
next=decide78(iter, k, A);
end;
if next==1,
next=2;
hubo_division=0;
A2=A;
divide=0;
[Di, D, STM]= dispersion(X, Y, Z, cluster, A);
i=0;
while (hubo_division==0) & (i < A), % Si para algun...
i=i+1;
index=find(cluster==i); % Index nos indica los valores del agrupamiento a particionar.
sindex=size(index);
sindex=sindex(2);
if (STM(i)>OS) & ( ((Di(i,1)>D(1)) & (Di(i,2)>D(2)) & (sindex>(2*(ON+1)))) | (A<=(k/2)) ),
hubo_division=1;
next=1;
[Z, cluster]=dividir(STM, A, cluster, Z, i, (A+1), X, Y); % Division.
A=A+1; % Indicamos que hay un nuevo agrupamiento.
iter=iter+1;
end;
end;
end;
if next==2,
[orden, Dij]= distancia_centros(A, Z, OC, L); %Si orden==0 --> no hay nada para mezclar.
% Union de agrupamientos.
if orden(1) > 0,
[cluster, Z, A]=union(A, orden, cluster, Z, Dij);
% Recacula los centros.
Z=recalcula(cluster, X, Y, A, Z);
end;
end;
if next==2
[iter,final,vuelve3]= termina_o_itera(iter, I, NO);
end;
for j=1:s
temp=0;
P=[X(j) Y(j)];
for i=1:A,
if distancia(P,Z(i,:)) > min,
temp=temp+1;
end;
end;
if temp==A,
cluster(j)=0;
end;
end;
Xcluster=0;
Ycluster=0;
for m=1:k
inedx=0;
index=find(cluster==m);
s2=size(index);
s2=s2(2);
for n=1:s2
Xcluster(1,n,m)= X(index(n));
Ycluster(1,n,m)= Y(index(n));
end;
end;
function [m] = cercano(x, y, Z, k)
dtemp=0;
d=0;
for j=1:k
P=[x y];
d=distancia(Z(j,:), P); % Distancia del centro al punto.
if j<2,
m=j; % La primera distancia siempre es valida.
dtemp=d;
elseif d < dtemp,
m=j; % Nos quedamos con el centro al que corresponde
dtemp=d; % la menor de las distancias.
end;
end;
function [Zout1] = recalcula(cluster, X, Y, k, Z) %Realiza la media de los puntos asigandos a cada clase corersp. a los centros
s=size(X);
s=s(2);
valor=zeros(1,k);
Zout=zeros(k,2);
for m=1:k
index=find(cluster==m);
if isempty(index)==0
sindex=size(index);
sindex=sindex(2);
Zout1(m,1)=(sum(X(index))) / sindex;
Zout1(m,2)=(sum(Y(index))) / sindex;
else
Zout1(m,:)=Z(m,:);
end;
end;
function [Ditemp, Dtemp, STMAX] = dispersion(X, Y, Z, cluster, A)
Ditemp=zeros(A,2);
Dtemp=zeros(1,2);
ST=zeros(A,2);
STMAX=zeros(1,A);
for i=1:A,
suma=[0 0];
index=find(cluster==i);
sindex=size(index);
for j=index,
P=[X(j), Y(j)];
d=distancia(Z(i,:), P );% Distancia de Xi al centro Zi.
suma(1)=suma(1) + (d * X(j)); % sumax
suma(2)=suma(2) + (d * Y(j)); % sumay
end;
% Dispersion por agrupamiento
Ditemp(i,:)=suma / sindex(2);
% Dispersion global temporal
Dtemp(1,:)=Dtemp(1,:) + (Ditemp(i,:) * sindex(2));% Sumatorio Ni*Di
%Dispersion por variable
ST(i,1)=std(X(index));
ST(i,2)=std(Y(index));
% Componente de maxima dispersion
STMAX(i)=max(ST(i,:));
end;
% Dispersion global acabada
Dtemp(1,:)=Dtemp(1,:) / A;
function [Ztemp, Atemp, clustertemp]=eliminar(A, cluster, Z, X, Y, ON)
%Asignacion.
%desplazamiento: sirve para indicar que centros y agrupaviones hay que
%eliminar
desplazamiento=zeros(1,A); % Sus posibles valores son: -1, (=0) o (>0).
for i=1:A, % Si -1: este grupo se alimina. Si 0: no varia.
cont=find(cluster==i); % Si >0: se le restan tantas posiciones como indique su valor.
scont=size(cont);
if scont(2) < ON
desplazamiento(i)=-1;
if i < A,
for j=(i+1):A
desplazamiento(j)=desplazamiento(j)+1;
end;
end;
end;
end;
%Actuacion.
[Ztemp, Atemp, clustertemp]=reduce(desplazamiento, A, cluster, Z);
% Asigna centros a los puntos que queden sueltos de la eliminacion
% anterior.
if isempty(Ztemp)==1, % Por si eliminamos todos los grupos.
Atemp=1;
Ztemp(1,1)=median(X);
Ztemp(1,2)=median(Y);
end;
vacio=find(clustertemp==0);
if isempty(vacio)==0
for i=vacio,
clustertemp(i)=cercano(X(i), Y(i), Ztemp, Atemp);
end;
end;
function [clustertemp, Ztemp, Atemp]=union(A, orden, cluster, Z, Dij)
clustertemp=cluster;
sorden=size(orden);
unidos=0;
uindex=0;
sunidos=size(unidos);
marca=zeros(1,A);
imarca=0;
for i=1:sorden(2),
yaunido=0;
temp=[0 0];
%Miram si qualque dels centre asociats ja ha estat unit.
[fcnum(1),fcnum(2)]=find(Dij==orden(i)); % fcnum(1) < fcnum(2)
for j=1:2,
if isempty( find(unidos==fcnum(j)) )==0,
yaunido=1;
else
temp(j)=fcnum(j);
end;
end;
if yaunido==0
for h=1:2; %Guardamos los centros a unir en la lista de centros unidos.
unindex=uindex+1;
unidos(unindex)=temp(h);
end
marca(fcnum(2))=-1;
selec=find(clustertemp==fcnum(2)); % Seleccinamos el grupo del centro con numero resp. mas grande y
clustertemp(selec)=fcnum(1); % lo unimos al del centro de valor respectivo mas pequeсo.
end;
end;
adicion=0; %Colocamos en el vector 'marca' la informacion de la forma que nos interesa.
for i=1:A
if marca(i) >= 0,
marca(i)=marca(i)+adicion;
else
adicion=adicion+1;
end;
end;
% Nos reduce (si hace falta) el numero de centros y de agrupamientos encontrados.
[Ztemp, Atemp]=reduce(marca, A, clustertemp, Z);
function [Ztemp, Atemp, clustertemp]=reduce(desplazamiento, A, cluster, Z)
Atemp=A;
clustertemp=cluster;
Ztemp=find(Atemp==999999);
for i=1:A
if (desplazamiento(i) < 0),
selec=find(cluster==i);
if isempty(selec)==0
clustertemp(selec)=0;
end;
Atemp=Atemp-1;
else
Ztemp( (i-desplazamiento(i)), :)= Z(i,:);
selec=find(clustertemp==i);
clustertemp(selec)=clustertemp(selec)-desplazamiento(i);
end;
end;
function [orden, Dij]= distancia_centros(A, Z, OC, L)
Dij=zeros((A-1),A);
%Calcular las distancias entre centros.
for i=1:(A-1),
for j=(1+i):A,
Dij(i,j)=distancia(Z(i,:), Z(j,:));
end;
end;
%Ordenar las L distancias menores que OC. ~
index= find( (Dij>0) & (Dij<OC) )';
if (isempty(index))==0,
orden=sort(Dij(index));
sorden=size(orden);
if sorden(2)>L
orden=orden(1,1:L);
end;
else
orden=0;
end;
function [Ztemp, clustertemp]=dividir(ST, A, cluster, Z, ncentro, Atemp, X, Y)
clustertemp=cluster;
Ztemp=Z;
k2=0.5; % 0 < k2 < 1
Yi=ST(ncentro) * k2;
Ztemp(Atemp,:)=Ztemp(ncentro,:); % nou centre i agrupament
m=find( Ztemp(ncentro,:)==max(Ztemp(ncentro,:)) ); % indice de la coordenada mayor.
Ztemp(ncentro,m)=Ztemp(ncentro,m)+Yi; % Z+=Z(ncentro)
Ztemp(Atemp,m)=Ztemp(Atemp,m)-Yi; % Z-=Z(Atemp)
% Asignamos cada punto al nuevo centro que tenga mas cercano (Z+ o Z-),
% por defecto debido a la forma de tratarlo, el centro por defecto es
% Z+.
dividendo= find(clustertemp==ncentro);
for i=(dividendo),
P=[X(i), Y(i)];
if (distancia( P, Ztemp(ncentro,:) )) >= (distancia(P, Ztemp(Atemp,:))), %d(Z+) >= d(Z-)
clustertemp(i)=Atemp;
end;
end;
function [dist]= distancia(Z1, Z2)
dist=sqrt( ((Z1(1)-Z2(1))^2) + ((Z1(2)-Z2(2))^2) );% Distancia entre dos puntos.
function [Z]=inicializa_centros(X, Y, k)
% Distribuye los centros uniformemente
dx= (max(X))-(min(X));
dy= (max(Y))-(min(Y));
dzx= dx/(k+1); % distancia entre centros coordenada X.
dzy= dy/(k+1); % distancia entre centros coordenada Y.
for i=1:k,
Z(i,1)=min(X)+(dzx*i);
Z(i,2)=min(Y)+(dzy*i);
end;
function [Ltemp, Itemp, ktemp, ONtemp, OCtemp, OStemp]=parametros(L, I, k, ON, OC, OS, iter)
Ltemp=L; Itemp=I; ktemp=k; ONtemp=ON; OCtemp=OC; OStemp=OS;
comienza=0;
while comienza==0,
preg=find(comienza==9);% Da resultado vacio.
fprintf('\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n');
fprintf('Iteracion actual: %d \n',iter);
fprintf('L=%d, I=%d, k=%d, ON=%d, OC=%d, OS=%d \n',L,I,k,ON,OC,OS);
fprintf('Que parametro deseas modificar? \n(1: L / 2: I / 3: k / 4: ON / 5: OC / 6: OS / 7: Ninguno) \n');
while isempty(preg)==1,
preg=input('Eleccion:');
end;
if preg==7
comienza=1;
else
valor=find(comienza==9);% Da resultado vacio.
while isempty(valor)==1,
valor=input('Valor:');
end;
if preg==1,
Ltemp=valor;
elseif preg==2,
Itemp=valor;
elseif preg==3,
Ktemp=valor;
elseif preg==4,
ONtemp=valor;
elseif preg==5,
OCtemp=valor;
elseif preg==6,
OStemp=valor;
end;
end;
end;
function [itertemp,FINtemp,vuelve3temp]= termina_o_itera(iter, I, NO)
itertemp=iter;
FINtemp=0;
vuelve3temp=1;
if itertemp==I,
FINtemp=1;
else
if NO==1
vuelve3temp=1;
else
preg2=find(iter==0); % Resp. vacia
fprintf('\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n');
fprintf('Iteracion actual: %d \n',itertemp);
while (isempty(preg2)==1) | ( (preg2~=2) & (preg2~=1) ),
fprintf('Desea modificar algun parametro antes de volver iterar? (SI=1 / NO=2) \n Respuesta:');
preg2=input('');
end;
if preg2==1
vuelve3temp=0; % Ve a paso2 (modifica parametros).
else
vuelve3temp=1; % Ve a paso3.
end;
end;
itertemp=itertemp+1;
end;
function [nexttemp]=decide78(iter, k, A)
nexttemp=0;
if A <= (k/2)
nexttemp=1; % Va a paso 7.
end
if ( (A>=(2*k)) | ( (iter>0) & (((iter+1)/2)>(ceil(iter/2)))) ) % Si a>=2k o la iteracion es par.
nexttemp=2; % Va a paso 8.
end
if nexttemp==0
nexttemp=1;
end;
Висновки
На цій лабораторній роботі я вивчив принципи роботи алгоритму розпізнавання образів ІЗОМАД.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора