Îïèñàíèå ïðåäëàãàåìîãî ïîäõîäà

Êàê ïîêàçàë îáçîð ëèòåðàòóðû, ñóùåñòâóþùèå ñèñòåìû íàâèãàöèè ïî êîëëåêöèÿì èçîáðàæåíèé ñòðîÿòñÿ íà îñíîâå äâóõ ðàçëè÷íûõ ãðóïï ìåòî-äîâ. Ê ïåðâîé ãðóïïå îòíîñÿòñÿ ìåòîäû êëàñòåðè-çàöèè, ïîçâîëÿþùèå ðàçáèòü âñþ êîëëåêöèþ èçîá-ðàæåíèé íà íåáîëüøèå ãðóïïû, âíóòðè êîòîðûõ ðàçíèöà ìåæäó èçîáðàæåíèÿìè íåâåëèêà. Êî âòî-ðîé ãðóïïå îòíîñÿòñÿ ìåòîäû ñíèæåíèÿ ðàçìåð-íîñòè ïðîñòðàíñòâà ïðèçíàêîâ, ïîçâîëÿþùèå ðàñ-ïîëîæèòü ýëåìåíòû êîëëåêöèè íà ïëîñêîñòè.

Äëÿ ïîñòðîåíèÿ áîëåå ýôôåêòèâíûõ ñðåäñòâ íàâèãàöèè ïðåäñòàâëÿåòñÿ öåëåñîîáðàçíûì ðàçðà-áîòêà è èññëåäîâàíèå ñðåäñòâ ñîâìåùåíèÿ ìåòî-äîâ, îòíîñÿùèõñÿ ê ðàçëè÷íûì ãðóïïàì. Îäíàêî èìåííî ýòîìó âîïðîñó èññëåäîâàòåëÿìè ïîêà íå áûëî óäåëåíî äîñòàòî÷íî âíèìàíèÿ.

 äàííîé ðàáîòå ïðîâåäåíî èññëåäîâàíèå ðÿäà êîìáèíèðîâàííûõ àëãîðèòìîâ, ôóíêöèîíèðóþùèõ íà îñíîâå øèðîêî èçâåñòíîãî ìåòîäà ñíèæåíèÿ ðàçìåðíîñòè Ñýììîíà è ìåòîäîâ êëàñòåðèçàöèè.

Êðîìå òîãî, â ðàáîòå ïðåäëàãàåòñÿ ìåòîä ñíèæå-íèÿ ðàçìåðíîñòè, ïîçâîëÿþùèé ñîõðàíÿòü ëèíåé-íóþ ðàçäåëèìîñòü êëàñòåðîâ ïðè ïîñòðîåíèè îòî-áðàæåíèÿ â äâóìåðíîå ïðîñòðàíñòâî.

4.1. Àëãîðèòìû êëàñòåðèçàöèè

Äëÿ ðåàëèçàöèè ýòàïà êëàñòåðèçàöèè êîëëåêöèè èçîáðàæåíèé è ïîñòðîåíèÿ èåðàðõèè âëîæåííûõ êëàñòåðîâ â ïðîöåññå ðàáîòû áûëè ðàññìîòðåíû êàê àëãîðèòìû èåðàðõè÷åñêîé àãëîìåðàòèâíîé êëà-ñòåðèçàöèè, òàê è íåéðîñåòåâîé àëãîðèòì WTA.

 êà÷åñòâå àëãîðèòìîâ èåðàðõè÷åñêîé êëàñòåðè-çàöèè ðàññìàòðèâàëèñü àëãîðèòìû Single Link è Complete Link [25].

Íåéðîñåòåâîé êëàñòåðèçàöèîííûé àëãîðèòì WTA ôóíêöèîíèðóåò íà áàçå íåéðîííîé ñåòè Êîõîíåíà [2], ïðåäñòàâëÿþùåé ñîáîé îäíîñëîéíóþ ñåòü, â êîòîðîé êàæäûé íåéðîí ñîåäèíåí ñî âñåìè

êîì-ïîíåíòàìè âõîäíîãî âåêòîðà. Ïðè ïîäà÷å íà âõîä ñåòè â ìîìåíò âðåìåíè t âåêòîðà x(t) â êîíêóðåí-òíîé áîðüáå ïîáåæäàåò òîò íåéðîí èç îáùåãî ÷èñ-ëà K, âåñà êîòîðîãî â íàèìåíüøåé ñòåïåíè

îòëè-÷àþòñÿ îò ñîîòâåòñòâóþùèõ êîìïîíåíò âõîäíîãî âåêòîðà. Äëÿ íåéðîíà-ïîáåäèòåëÿ n âûïîëíÿåòñÿ ñîîòíîøåíèå

d(x(t), w_ν (t)) = min_1≤i ≤Kd(x(t), w_i (t)).

Çäåñü d(x(t), w(t)) – ðàññòîÿíèå ìåæäó âõîäíûì âåêòîðîì x(t) è òåêóùèì ñîñòîÿíèåì ñèíàïòè÷åñêèõ âåñîâ w_i(t) íåéðîíà i. Âûõîäíîé ñèãíàë y_ν  âûèãðàâ-øåãî íåéðîíà óñòàíàâëèâàåòñÿ â åäèíèöó, âûõîäû îñòàëüíûõ íåéðîíîâ y_i ñòàíîâÿòñÿ ðàâíûìè íóëþ.

Íåéðîí-ïîáåäèòåëü ïîäâåðãàåòñÿ àäàïòàöèè, â õîäå êîòîðîé âåêòîðû âåñîâ èçìåíÿþòñÿ â íàïðàâëåíèè âåêòîðà x(t) ïî ïðàâèëó êîððåêöèè:

w_ν(t + 1) = w_ν(t) + η(t)[x(t) – w_ν(t)].

Çäåñü η(t) – êîýôôèöèåíò îáó÷åíèÿ â ìîìåíò âðåìåíè t, çíà÷åíèå êîòîðîãî ñî âðåìåíåì óìåíü-øàåòñÿ. Îñíîâíûå ïàðàìåòðû àëãîðèòìà ïîäðîáíî îïèñàíû â ðàáîòå [1].

 ðàáîòå áûëî ïðîâåäåíî èññëåäîâàíèå âñåõ ïðèâåäåííûõ àëãîðèòìîâ êëàñòåðèçàöèè. Ðåçóëü-òàòû èññëåäîâàíèÿ ïðèâîäÿòñÿ â ðàçäåëå 5.1.

4.2. Ëèíåéíûé è íåëèíåéíûé ìåòîäû ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà

Äëÿ ëèíåéíîãî ïðåîáðàçîâàíèÿ ïðîñòðàíñòâà â ðàáîòå èñïîëüçóåòñÿ äèñêðåòíûé âàðèàíò ïðåîáðà-çîâàíèÿ Êàðóíåíà-Ëîýâà, ðåàëèçóåìûé íåéðîííîé ñåòüþ PCA [2] ñ ïðèìåíåíèåì ïðàâèëà Ñåíãåðà.

Ïðè îáó÷åíèè ñåòè èñïîëüçóåòñÿ àäàïòèâíûé àë-ãîðèòì èçìåíåíèÿ êîýôôèöèåíòà îáó÷åíèÿ.  ïðî-öåññå îáó÷åíèÿ âõîäíàÿ âûáîðêà ïðåäúÿâëÿåòñÿ íà âõîä ñåòè ìíîãîêðàòíî, âïëîòü äî ñòàáèëèçàöèè âåñîâ.

Äëÿ íåëèíåéíîãî ïðåîáðàçîâàíèÿ ïðîñòðàíñòâà â ïðåäëàãàåìîì ìåòîäå âçÿò çà îñíîâó àëãîðèòì äâó-ìåðíîãî îòîáðàæåíèÿ, îïèñàííûé, â ÷àñòíîñòè, â [3] è âïåðâûå ïðèìåíåííûé Ñýììîíîì â 1969 ã.

Äàííûé àëãîðèòì ïîçâîëÿåò ìèíèìèçèðîâàòü îøèá-êó ïðåäñòàâëåíèÿ ìíîãîìåðíûõ äàííûõ, âûðàæàå-ìóþ â âèäå:

( )

_.

d d d d

N

j

i ij

* ij ij

j i

ij

∑

∑

_< ^{⋅ < −}

=

2

ε 1 ₍₂₎

Çäåñü d_ij è d^*_ij – ðàññòîÿíèå ìåæäó îáúåêòàìè i è j, ñîîòâåòñòâåííî, â ìíîãîìåðíîì è äâóìåðíîì ïðî-ñòðàíñòâå.

Ðàáîòà àëãîðèòìà èìååò èòåðàòèâíûé õàðàêòåð, ñâÿçàííûé ñî ñëåäóþùèì ðåêóððåíòíûì ñîîòíîøå-íèåì äëÿ êîîðäèíàò â äâóìåðíîì ïðîñòðàíñòâå y_jk:

(

^{y t y t}

)

^.

d d

d d d t y t

y

N

i j

1 j

jk

* ik ij

* ij N

j i

ij ik

ik

ij

∑

ij

∑

^≠=

<

−

⋅ ⋅

⋅ − + ⋅

=

+ 2 ( ) ( )

) ( 1)

( α

Íàñòðàèâàåìûé ïàðàìåòð a âëèÿåò íà ñêîðîñòü ðàáîòû è ñõîäèìîñòü àëãîðèòìà.

Ñëåäóåò îòìåòèòü, ÷òî âîçìîæíî

èñïîëüçîâà-íèå äâóõýòàïíîãî ìåòîäà ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà.  òàêîì ìåòîäå íà ïåðâîì ýòàïå ñ ïî-ìîùüþ íåéðîííîé ñåòè PCA íàõîäèòñÿ ãðóáîå ïðè-áëèæåíèå ðåøåíèÿ. Íà âòîðîì ýòàïå ïîëó÷åííîå ïðèáëèæåíèå óòî÷íÿåòñÿ îïèñàííûì âûøå íåëèíåé-íûì ìåòîäîì ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà.

Äâóõýòàïíûé ìåòîä îáëàäàåò ïîòåíöèàëüíî áîëåå âûñîêîé òî÷íîñòüþ è áîëåå áûñòðîé ñõîäèìîñòüþ.

Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ òàêî-ãî ìåòîäà è âõîäÿùèõ â åòàêî-ãî ñîñòàâ àëòàêî-ãîðèòìîâ ïðåä-ñòàâëåíû â ðàçäåëå 5.2.

4.3. Êîìáèíèðîâàííûé ìåòîä ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà

Ïðèâåäåííûé â ïðåäûäóùåì ðàçäåëå àëãîðèòì íåëè-íåéíîãî ñíèæåíèÿ ðàçìåðíîñòè õîðîøî ðàáîòàåò íà íåáîëüøèõ îáúåìàõ äàííûõ, îäíàêî íà áîëüøèõ îáúåìàõ äàííûõ âîçìîæíîñòè ïðèìåíåíèÿ àëãîðèò-ìà îãðàíè÷èâàåò âû÷èñëèòåëüíàÿ ñëîæíîñòü. Ïðè îáúåìå âûáîðêè N è ÷èñëå èòåðàöèé, ñðàâíèìîì ñ îáúåìîì âûáîðêè îáúåì âû÷èñëåíèé äëÿ ïîëó÷åíèÿ îòîáðàæåíèÿ ðàâåí O[N³].

Ðåøåíèåì äàííîé ïðîáëåìû ìîæåò áûòü àëãî-ðèòì, èñïîëüçóþùèé àïïðîêñèìàöèè ïðèðàùåíèé êîîðäèíàò òî÷åê íà êàæäîé èòåðàöèè. Ïðè ýòîì, åñëè âû÷èñëèòåëüíàÿ ñëîæíîñòü äëÿ ïîñòðîåíèÿ àïïðîêñèìàöèîííîé îöåíêè íà êàæäîé èòåðàöèè O[k], ãäå k<<N, òî âû÷èñëèòåëüíàÿ ñëîæíîñòü âñåãî àëãîðèòìà ìîæåò áûòü ñíèæåíà äî O[N²].

Ñðåäè ñóùåñòâóþùèõ ðåøåíèé â êà÷åñòâå òà-êîé àïïðîêñèìàöèè ìîæåò áûòü èñïîëüçîâàí ìå-òîä, ïîäîáíûé ïðåäëîæåííîìó ×àëìåðñîì â ðàáî-òå [5].  ýòîì ïîäõîäå íà êàæäîé èðàáî-òåðàöèè äëÿ êàæäîãî êîððåêòèðóåìîãî ýëåìåíòà ôîðìèðóåòñÿ 2 ìíîæåñòâà.  ïåðâîì èç ìíîæåñòâ ñîäåðæàòñÿ ýëåìåíòû, íàèáîëåå áëèçêèå ðàññìàòðèâàåìîìó â ìíîãîìåðíîì ïðîñòðàíñòâå. Âî âòîðîì ìíîæåñòâå ñîäåðæàòñÿ ýëåìåíòû, îòáèðàåìûå íà êàæäîé èòå-ðàöèè ñëó÷àéíûì îáðàçîì. Òàêîé ïîäõîä áûë èñ-ïîëüçîâàí äëÿ ìèíèìèçàöèè îøèáêè, âûðàæàå-ìîé â âèäå (1), îäíàêî îí ìîæåò áûòü ïðèìåíåí è ïðè ìèíèìèçàöèè îøèáêè Ñýììîíà (2) (äàëåå áóäåì íàçûâàòü ýòîò ìåòîä ìåòîäîì ×Ñ).

 íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ íîâûé êîì-áèíèðîâàííûé ìåòîä (ÊÌ). Îí ñîñòîèò â òîì, ÷òî-áû â êà÷åñòâå àïïðîêñèìàöèè èñïîëüçîâàòü ðå-çóëüòàòû èåðàðõè÷åñêîé êëàñòåðèçàöèè â ðàìêàõ äâóõýòàïíîé ïðîöåäóðû ñëåäóþùåãî âèäà. Íà ïåð-âîì ýòàïå äëÿ âñåõ k êëàñòåðîâ ñàìîãî âåðõíåãî óðîâíÿ ñòðîèòñÿ äâóìåðíîå îòîáðàæåíèå öåíòðîâ ýòèõ êëàñòåðîâ. Íà âòîðîì ýòàïå ñòðîèòñÿ k îòî-áðàæåíèé äëÿ ïîäêëàñòåðîâ è îáúåêòîâ âòîðîãî óðîâíÿ. Ïðè ýòîì äëÿ ïîñòðîåíèÿ îòîáðàæåíèÿ êàæäîãî ïîäêëàñòåðà ðàñïîëîæåíèå êîîðäèíàò öåí-òðîâ ñóïåðêëàñòåðîâ ôèêñèðóåòñÿ, à ïðîèçâîäèòñÿ îïòèìèçàöèÿ òîëüêî îáúåêòîâ, íàõîäÿùèõñÿ â ðàñ-ñìàòðèâàåìîì ïîäêëàñòåðå. Ïðîöåññ ïîâòîðÿåòñÿ äëÿ òðåòüåãî óðîâíÿ èåðàðõèè è òàê äàëåå, ïîêà íå áóäåò ïîñòðîåíî îòîáðàæåíèå âñåõ îáúåêòîâ.

 ñëó÷àå, êîãäà ìîùíîñòü êëàñòåðà ðàâíà k, âû÷èñëèòåëüíàÿ ñëîæíîñòü äâóìåðíîãî îòîáðàæå-íèÿ ýëåìåíòîâ êëàñòåðà ðàâíà O[k³]. Äàëåå, ÷èñëî êëàñòåðîâ ïðè èåðàðõè÷åñêîé êëàñòåðèçàöèè â

ñëó-÷àå ñáàëàíñèðîâàííîãî äåðåâà êëàñòåðîâ ñîñòàâëÿ-åò:

k . N N k

k ... N k

N k M N

N log

1 i N i

log

k

k 1

1 1

2 −

= −

⋅

= +

+ +

=

∑

₌

Òàêèì îáðàçîì, âû÷èñëèòåëüíàÿ ñëîæíîñòü â

ñëó-÷àå ñáàëàíñèðîâàííîãî äåðåâà êëàñòåðîâ ðàâíà

[ ] [ ]

^{k ~Ok N}

k O

N _{3 2}

1 1

−

− .  ñëó÷àå ñáàëàíñèðîâàííîãî äåðåâà äâóõóðîâíåâîé èåðàðõèè k= N _{. Òîãäà} ñëîæíîñòü àëãîðèòìà, êàê è â ñëó÷àå ïðåäûäóùåãî àëãîðèòìà, ðàâíà O[N²]. Îäíàêî ñ ðîñòîì êîëè÷åñòâà óðîâíåé èåðàðõèè ñáàëàíñèðîâàííîãî äåðåâà ñëîæ-íîñòü àëãîðèòìà óìåíüøàåòñÿ. Äëÿ ñëó÷àÿ ñáàëàíñè-ðîâàííîãî äåðåâà âûñîòîé L = log_kN, êîãäà â êàæäîì êëàñòåðå îêàçûâàåòñÿ k = N^1/L ýëåìåíòîâ, âûðàæåíèå ñëîæíîñòè ïðèíèìàåò âèä ⎥

⎦

⎢ ⎤

⎣

⎡ ¹⁺_L² N

O . Î÷åâèäíî, ïî ìåðå ðîñòà ÷èñëà óðîâíåé L ýòî âûðàæåíèå ñòðåìèò-ñÿ ê O[N].

 ðàáîòå òàêæå ðàññìàòðèâàåòñÿ ìîäèôèêàöèÿ êîìáèíèðîâàííîãî ìåòîäà (ÌÊÌ), â êîòîðîé ïðè ïîñòðîåíèè îòîáðàæåíèÿ äëÿ ëþáîãî êëàñòåðà (êðî-ìå êëàñòåðà âåðõíåãî óðîâíÿ) â êà÷åñòâå ôèêñèðî-âàííûõ öåíòðîâ áåðóòñÿ öåíòðû êëàñòåðîâ âåðõíå-ãî óðîâíÿ. Î÷åâèäíî, âû÷èñëèòåëüíàÿ ñëîæíîñòü êîìáèíèðîâàííîãî ìåòîäà ñ ìîäèôèêàöèåé îñòà-åòñÿ òîé æå.

Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ ïðåäñòàâëåííûõ â ýòîì ðàçäåëå ìåòîäîâ ïðèâåäå-íû â ðàçäåëå 5.2.

4.4. Êîìáèíèðîâàííûé ìåòîä ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà ñ îãðàíè÷åíèÿìè Ðàññìîòðåííûå ìåòîäû ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà èìåþò ñóùåñòâåííûé íåäîñòàòîê. À èìåííî, èõ ïðèìåíåíèå íå äàåò ãàðàíòèè òîãî,

÷òî â äâóìåðíîì ïðîñòðàíñòâå áóäåò ñîõðàíåíà òà ðàçäåëèìîñòü êëàñòåðîâ, êîòîðàÿ èìåëà ìåñòî â ìíîãîìåðíîì ïðîñòðàíñòâå. Äëÿ ïîëüçîâàòåëÿ ýòî âûðàæàåòñÿ â ïðîÿâëåíèè íåæåëàòåëüíîãî ýôôåê-òà, çàêëþ÷àþùåãîñÿ â òîì, ÷òî íåïîõîæèå èçîáðà-æåíèÿ îêàçûâàþòñÿ ðÿäîì äðóã ñ äðóãîì. ×òîáû èçáåæàòü ïîäîáíîãî ýôôåêòà ïîòðåáóåì ñîõðàíå-íèÿ ðàçäåëèìîñòè ìåæäó êëàñòåðàìè ïðè îòîáðà-æåíèè. Ñóùåñòâåííî, ÷òî ïðåäëîæåííûé â ïðåäû-äóùåì ðàçäåëå êîìáèíèðîâàííûé ìåòîä åñòåñòâåí-íûì îáðàçîì ìîæåò áûòü äîðàáîòàí äëÿ óäîâëåò-âîðåíèÿ óêàçàííîìó òðåáîâàíèþ ñîõðàíåíèÿ ðàç-äåëèìîñòè. Íàçîâåì ðàçðàáàòûâàåìûé ìåòîä êîì-áèíèðîâàííûì ìåòîäîì ñíèæåíèÿ ðàçìåðíîñòè ïðî-ñòðàíñòâà ñ îãðàíè÷åíèÿìè (ÊÌÎ).

Ñóòü ìåòîäà ÊÌÎ ñîñòîèò â ñëåäóþùåì. Àëãî-ðèòì êëàñòåðèçàöèè ðàçáèâàåò âñå ìíîæåñòâî îáúåê-òîâ â ìíîãîìåðíîì ïðîñòðàíñòâå íà íåïåðåñåêàþ-ùèåñÿ ïîäìíîæåñòâà – êëàñòåðû. Ïîòðåáóåì, ÷òî-áû îáðàçû êëàñòåðîâ â äâóìåðíîì ïðîñòðàíñòâå íàâèãàöèè áûëè ðàçäåëèìû, ïðè÷åì êàæäûé êëà-ñòåð ìîã áûòü îãðàíè÷åí ïðÿìûìè, îáðàçóþùèìè âûïóêëóþ îáëàñòü. Åñòåñòâåííûì ñïîñîáîì óäîâ-ëåòâîðåíèÿ ýòîãî òðåáîâàíèÿ ÿâëÿåòñÿ

èñïîëüçî-âàíèå îáëàñòåé Âîðîíîãî. Ïîñòðîåíèå îáëàñòåé Âî-ðîíîâà, òî åñòü ïîëó÷åíèå íàáîðà îãðàíè÷èâà-þùèõ êàæäóþ îáëàñòü ïðÿìûõ, ïðîèçâîäèòñÿ íà îñ-íîâàíèè èíôîðìàöèè î ðàñïîëîæåíèè öåíòðîâ êëà-ñòåðîâ íà ïëîñêîñòè. Èìåÿ îïèñàíèÿ ïðÿìûõ– ãðà-íèö êëàñòåðîâ äëÿ êàæäîãî óðîâíÿ - ìîæíî êîððåê-òèðîâàòü ðåçóëüòàò îòîáðàæåíèÿ â äâóìåðíîå ïðî-ñòðàíñòâî.

Ñîáñòâåííî ïðåäëàãàåìûé ìåòîä ÊÌÎ ïðåä-ñòàâèì ñëåäóþùèì îáðàçîì.

1. Îòîáðàæàåì öåíòðû x_u¹ êëàñòåðîâ Ñ_u¹ ∈ C⁰ âåð-õíåãî óðîâíÿ â âåêòîðà y_u¹ íà ïëîñêîñòè ñ èñïîëüçî-âàíèåì ìåòîäà ñíèæåíèÿ ðàçìåðíîñòè ïðîñòðàíñòâà (íåëèíåéíîãî ìåòîäà Ñýììîíà èëè äâóõýòàïíîãî ìåòîäà). Óñòàíàâëèâàåì ãðàíèöû âñåé îáëàñòè îòî-áðàæåíèÿ Ã⁰ = ∅.

2. Äëÿ êàæäîãî êëàñòåðà Ñ_u^k∈C_v^k-1 òåêóùåãî óðîâíÿ k âûïîëíÿåì ïóíêòû 3–6.

3. Ñòðîèì ãðàíèöû Ã_u^k êëàñòåðà C_u^k â äâóìåðíîì ïðîñòðàíñòâå ñ ó÷åòîì êëàñòåðîâ C_m^k, m=1..|C_v^k-1| òå-êóùåãî óðîâíÿ k, èñïîëüçóÿ äëÿ ýòîãî öåíòðû ñîîò-âåòñòâóþùèõ êëàñòåðîâ y_m^k íà ïëîñêîñòè.

4. Äîïîëíÿåì ãðàíèöû êëàñòåðà Ã_u^k ñ ó÷åòîì ãðà-íèö Ã_v^k-1 ðîäèòåëüñêîãî êëàñòåðà C_v^k-1 ïðåäûäóùåãî óðîâíÿ: Ã_u^k = Ã_u^k ∪ Ã_v^k-1.

5. Îòîáðàæàåì öåíòðû x_i^k+1 âñåõ ïîäêëàñòåðîâ Ñ_i^k+1∈Ñ_u^k (èëè êîîðäèíàòû ñàìèõ èçîáðàæåíèé O_i) óðîâíÿ k +1 â âåêòîðà y_i^k+1 íà ïëîñêîñòè, ó÷èòûâàÿ ãðàíèöû Ã_u^k êëàñòåðà, ñ èñïîëüçîâàíèåì ñëåäóþùå-ãî ðåêóððåíòíîñëåäóþùå-ãî ñîîòíîøåíèÿ:

( )

(

^(t),

)

^,

) t ( ) t d (

d d d d t t

k u 1 k i

N

i j 1 j

j 1 k

* i ij

* ij N

i j

ij 1

k i 1

k i

ij ij

à y 2 y ) ( y 1) ( y

+

≠=

+

>

+ +

−

−

−

⋅ ⋅

⋅ − + ⋅

=

+

∑

∑

ϕ

α _y

ãäå d^*_ij= ||y_i^k+1, y_j||, d_ij= ||_i^k+1, x_j||, y_j∈{y_l^k+1, l= 1..|Ñ_u^k|} ∪ {y_l¹, l= 1..|Ñ_u¹|}, x_j∈{x_l^k+1, l= 1..|Ñ_u^k|} ∪ {x_l¹, l= 1..|Ñ_u¹|}, N = |Ñ_u^k| + |Ñ_u¹|.

6. Ïðèìåíÿåì îïèñàííóþ â ïï. 3–5 ïðîöåäóðó äëÿ îòîáðàæåíèÿ äî÷åðíèõ êëàñòåðîâ C_i^k+1 â ðå-êóðñèâíîì ïîðÿäêå.

Ïðåäñòàâëåííûé ìåòîä äàí ñ òî÷íîñòüþ äî îïðåäåëåíèÿ ôóíêöèè øòðàôà çà ïðèáëèæåíèå èëè âûõîä òî÷êè çà ãðàíèöû ñîîòâåòñòâóþùåãî êëàñ-òåðà. Ôóíêöèÿ ϕ(y, Ã) vîæåò áûòü âûáðàíà èñõîäÿ èç ìèíèìèçàöèè îáùåãî ôóíêöèîíàëà, ñîñòîÿùåãî èç îøèáêè Ñýììîíà è ôóíêöèè ãðàíèöû (ãðàäèåíòíîå ïðàâèëî).

 íàñòîÿùåé ðàáîòå ðàññìàòðèâàëèñü äâà ýâðè-ñòè÷åñêèõ ïðàâèëà îïðåäåëåíèÿ ôóíêöèè ϕ(y, Ã).

Ïðàâèëî ïîëíîé êîððåêöèè (ÊÌÎ-1) – âåëè÷èíà ϕ(y, Ã) âûáèðàëàñü òàêèì îáðàçîì, ÷òîáû ïðè âûõî-äå òî÷êè çà ãðàíèöó êëàñòåðà íà ñëåäóþùåì øàãå îá-ðàç òî÷êè y_i ïîïàäàë íà ãðàíèöó;

Êóñî÷íî-ëèíåéíîå ïðàâèëî êîððåêöèè (ÊÌÎ-2)-âåëè÷èíà ϕ(y, Ã) âûáèðàëàñü òàêèì îáðàçîì, ÷òîáû îáåñïå÷èòü «ïðèòÿæåíèå» òî÷êè y_i ê öåíòðó êëàñòå-ðà, ïðîïîðöèîíàëüíîå ðàññòîÿíèþ äî öåíòðà êëàñ-òåðà èëè ãðàíèöû.

Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ

ïðåäñòàâëåííîãî â ýòîì ðàçäåëå ìåòîäà ïðèâåäåíû â ðàçäåëå 5.2.

4.5. Ìåòîä íàâèãàöèè ïî êîëëåêöèè öèôðîâûõ èçîáðàæåíèé

Èñïîëüçóÿ òåîðåòè÷åñêèå îñíîâû, èçëîæåííûå â äàí-íîì ðàçäåëå, ìîæíî ïðåäëîæèòü ñëåäóþùèé ìåòîä íàâèãàöèè ïî êîëëåêöèÿì öèôðîâûõ èçîáðàæåíèé.

Íà ïåðâîì ýòàïå äëÿ âñåé êîëëåêöèè öèôðîâûõ èçîáðàæåíèé ïðîèçâîäèòñÿ ðàñ÷åò ïðèçíàêîâ (âîï-ðîñ âûáîðà ñèñòåìû ïðèçíàêîâ ðàññìàòðèâàåòñÿ â 6 ðàçäåëå). Íà âòîðîì ýòàïå ïðîèçâîäèòñÿ èåðàðõè÷åñ-êàÿ êëàñòåðèçàöèÿ èçîáðàæåíèé â ìíîãîìåðíîì ïðî-ñòðàíñòâå ïðèçíàêîâ ñ èñïîëüçîâàíèåì àëãîðèòìà WTA, îïèñàííîãî â ðàçäåëå 4.1. Äàëåå ïðèìåíÿåòñÿ äâóõýòàïíûé ìåòîä îòîáðàæåíèÿ, ïðåäëîæåííûé â ðàçäåëå 4.4, êîòîðûé äëÿ êàæäîãî èçîáðàæåíèÿ êîë-ëåêöèè ðàññ÷èòûâàåò êîîðäèíàòû åãî ðàñïîëîæåíèÿ íà äâóìåðíîé ïëîñêîñòè îòîáðàæåíèÿ (íàâèãàöèè).

Ðåçóëüòàòîì ýòèõ òðåõ ýòàïîâ ÿâëÿþòñÿ ðàññ÷èòàí-íûå êîîðäèíàòû âñåõ èçîáðàæåíèé êîëëåêöèè íà äâóìåðíîé ïëîñêîñòè íàâèãàöèè. Íà îñíîâå ýòîé áà-çîâîé èíôîðìàöèè ïðîèçâîäèòñÿ ïðîöåññ íàâèãàöèè, èíòåðàêòèâíî óïðàâëÿåìûé ïîëüçîâàòåëåì.

Ïðîñòåéøèìè îïåðàöèÿìè íàâèãàöèè ÿâëÿþòñÿ îïåðàöèè ïåðåìåùåíèÿ ââåðõ, âíèç, âïðàâî, âëåâî, îïðåäåëÿåìûå íà äâóìåðíîì ïðîñòðàíñòâå åñòåñòâåí-íûì îáðàçîì. Êðîìå òîãî, ðåàëèçóþòñÿ îïåðàöèè óâå-ëè÷åíèÿ è óìåíüøåíèÿ ìàñøòàáà. Îïåðàöèÿ óâåëè÷å-íèÿ ìàñøòàáà (ïðèáëèæåíèå) ñîîòâåòñòâóåò ïåðåõîäó ê ïîäìíîæåñòâó èçîáðàæåíèé êîëëåêöèè, ñîîòâåò-ñòâóþùåìó ìåíüøåìó óðîâíþ ðàçëè÷èé. Îïåðàöèÿ óìåíüøåíèÿ ìàñøòàáà (óäàëåíèå) ñîîòâåòñòâóåò ïåðå-õîäó ê ïîäìíîæåñòâó èçîáðàæåíèé êîëëåêöèè, ñîîò-âåòñòâóþùåìó áîëüøåìó óðîâíþ ðàçëè÷èé. Ïðè ïå-ðåõîäå ê îòîáðàæåíèþ ñ áîëüøèì èëè ìåíüøèì óðîâ-íåì ðàçëè÷èé äëÿ ïîêàçà èñïîëüçóþòñÿ ïðåäñòàâèòå-ëè êëàñòåðîâ ñîîòâåòñòâóþùåãî óðîâíÿ èåðàðõèè.

Ïîìèìî óêàçàííûõ áàçîâûõ îïåðàöèé íàâèãàöèè ðàçðàáîòàííûé ìåòîä ïîçâîëÿåò îïðåäåëèòü îïåðà-öèþ ïåðåõîäà ê êîíêðåòíîìó êëàñòåðó â äåðåâå èåðàð-õèè.Äëÿ óñêîðåíèÿ îïåðàöèé íàâèãàöèè äàííûå ñ êîîðäèíàòàìè â äâóìåðíîì ïðîñòðàíñòâå ìîãóò áûòü ïðîñòðàíñòâåííî ïðîèíäåêñèðîâàíû.

Òàêèì îáðàçîì, ïî ïîñòðîåíèþ, ïðåäëîæåííûé ìåòîä àâòîìàòè÷åñêè óäîâëåòâîðÿåò åñòåñòâåííûì òðåáîâàíèÿì ðàçäåëà 3. Çàìåòèì, ÷òî ïîñêîëüêó êîîðäèíàòû ðàñïîëîæåíèÿ èçîáðàæåíèé êîëëåê-öèè íà ïëîñêîñòè îòîáðàæåíèÿ ìîæíî ðàññ÷èòàòü çàðàíåå è ñîõðàíèòü, òî ïðîáëåìà, ñâÿçàííàÿ ñî ñòîõàñòè÷åñêèì õàðàêòåðîì àëãîðèòìîâ (òðåáîâà-íèå îáðàòèìîñòè), ñíèìàåòñÿ.

Äîïîëíèòåëüíûì ïðåèìóùåñòâîì ïðåäëàãàåìî-ãî ìåòîäà ÿâëÿåòñÿ òî, ÷òî â íåì âîçìîæíî ÿâíîå îïðåäåëåíèå ãðàíèö êëàñòåðîâ â äâóìåðíîì íàâè-ãàöèîííîì ïðîñòðàíñòâå è ñîõðàíåíèå èõ õàðàêòå-ðèñòèê. Ýòî îòêðûâàåò øèðîêèå âîçìîæíîñòè äëÿ ïîðöèîííîé îáðàáîòêè äàííûõ è ïðîñòðàíñòâåí-íîé èíäåêñàöèè êîëëåêöèé èçîáðàæåíèé çíà÷è-òåëüíîãî îáúåìà.

Ñëåäóåò òàêæå îòìåòèòü, ÷òî èñïîëüçîâàíèå ïðåäëîæåííîãî â ï. 4.4 ìåòîäà íå ñîçäàåò ïðîáëåì

ïðè äîáàâëåíèè èëè óäàëåíèè åäèíè÷íûõ èçîáðàæå-íèé èç êîëëåêöèè.

5. Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ

ドキュメント内 untitled (ページ 146-149)