Îïèñàíèå ìåòîäîâ, àëãîðèòìîâ è ýêñïåðèìåíòîâ

4.1. Ìåòðèêè

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

Èñïîëüçóåìûå îáîçíà÷åíèÿ:

a êîëè÷åñòâî íàéäåííûõ ïàð äóáëèêàòîâ, ñî-âïàäàþùèõ ñ «ðåëåâàíòíûìè» ïàðàìè;

b êîëè÷åñòâî íàéäåííûõ ïàð äóáëèêàòîâ, íå ñîâïàäàþùèõ ñ «ðåëåâàíòíûìè» ïàðàìè;

c êîëè÷åñòâî íå íàéäåííûõ ïàð äóáëèêàòîâ, ñîâïàäàþùèõ ñ «ðåëåâàíòíûìè» ïàðàìè;

d êîëè÷åñòâî íå íàéäåííûõ ïàð äóáëèêàòîâ, íå ñîâïàäàþùèõ ñ «ðåëåâàíòíûìè» ïàðàìè.

Òî÷íîñòü (Precision). Ïðåäñòàâëÿåò ñîáîé îòíî-øåíèå îáùåãî ÷èñëà íàéäåííûõ ðåëåâàíòíûõ ïàð

äóáëèêàòîâ ê îáùåìó ÷èñëó íàéäåííûõ ïàð. Â íà-øåì ñëó÷àå îíà áóäåò õàðàêòåðèçîâàòü ñïîñîáíîñòü íàõîäèòü òîëüêî ðåëåâàíòíûå ïàðû.

b a P a

= +

Ïîëíîòà (Recall). Âû÷èñëÿåòñÿ êàê îòíîøåíèå îáùåãî ÷èñëà íàéäåííûõ ðåëåâàíòíûõ ïàð äóáëè-êàòîâ ê îáùåìó ÷èñëó «ðåëåâàíòíûõ» ïàð. Õàðàê-òåðèçóåò ñïîñîáíîñòü íàõîäèòü íóæíûå ïàðû.

c a R a

= +

Ô-ìåðà (F1, F-measure). Ãàðìîíè÷åñêîå ñðåäíåå äëÿ òî÷íîñòè è ïîëíîòû. Óäîáíà â èñïîëüçîâàíèè â êà÷åñòâå îáùåé ìåòðèêè, îáúåäèíÿþùåé äâå ïðåäûäóùèå, òàê êàê è ïîëíîòà è òî÷íîñòü ïðè-ñóòñòâóþò â íåé ñ îäèíàêîâûì âåñîì.

R P

PR F 2

= +

Àêêóðàòíîñòü (Accuracy). Îòíîøåíèå ÷èñëà ïðà-âèëüíûõ ðåøåíèé àëãîðèòìà ê îáùåìó ÷èñëó ðå-øåíèé.

m d

A=a+ , ãäå m = a + b + c + d.

AC1. Ìîäèôèöèðîâàííàÿ âåðñèÿ êàïïû Êîýíà, ñòàòèñòè÷åñêîé ìåðû âçàèìíîãî ñîãëàñèÿ äâóõ îöåíùèêîâ. Èñïîëüçîâàëàñü äëÿ îöåíêè ñòåïåíè ñîãëàñèÿ (ïåðåñåêàåìîñòè) ðåçóëüòàòîâ ðàçëè÷íûõ ýêñïåðèìåíòîâ.

) ( ) (

E p 1

A E 1 p

AC = − ,

ãäå p(E)= 2P(1-P) è 2m c b a ' 2

P= + + 4.2. Ïðîãðàììíàÿ ðåàëèçàöèÿ

Äëÿ âûïîëíåíèÿ èññëåäîâàíèÿ êîìïàíèåé «ßíäåêñ»

áûë ïðåäîñòàâëåí íàáîð äàííûõ «Web-ñòðàíèöû êîëëåêöèè ÐÎÌÈÏ». Ýòà êîëëåêöèÿ èñïîëüçóåòñÿ â ðàìêàõ Ðîññèéñêîãî ñåìèíàðà ïî îöåíêå ìåòîäîâ èíôîðìàöèîííîãî ïîèñêà (ÐÎÌÈÏ) è âêëþ÷àåò ïîðÿäêà 750 òûñÿ÷ ñòðàíèö, ñîäåðæàùèõñÿ áîëåå

÷åì â 23000 ñàéòîâ äîìåíà narod.ru.

Äàííûå î äóáëèêàòàõ ýòîãî íàáîðà äàííûõ, ïðåäîñòàâëåííûå âìåñòå ñ íèì, ñîñòàâëÿëèñü íà îñíîâå ôóíêöèè Ëåâåíøòàéíà (íàçûâàåìîé òàê æå ðàññòîÿíèåì ðåäàêòèðîâàíèÿ). Ýòà ôóíêöèÿ ðàâíà ìèíèìàëüíîìó êîëè÷åñòâó îïåðàöèé ðåäàêòèðîâà-íèÿ, íåîáõîäèìûõ äëÿ ïðåîáðàçîâàíèÿ îäíîãî äî-êóìåíòà â äðóãîé. Áûëè èçâåñòíû ïàðû äîêóìåí-òîâ, êîýôôèöèåíò ñõîäñòâà êîòîðûõ, ïîñëå óäàëå-íèÿ òýãîâ, ñîñòàâëÿë íå ìåíåå 85 % è ñîñòîÿùèõ íå ìåíåå, ÷åì èç 20 ñëîâ. Ñîîòâåòñòâåííî, ðåçóëü-òàòû ýêñïåðèìåíòîâ ñðàâíèâàëèñü èìåííî ñ ýòèì

«èäåàëüíûì» ñïèñêîì äóáëèêàòîâ.

Â ðÿäå ýêñïåðèìåíòîâ èñïîëüçîâàëñÿ ñïèñîê ñòîï-ñëîâ. Â ýòîì ñëó÷àå îí ãåíåðèðîâàëñÿ èç ôàéëà stopword.lst, âõîäÿùåãî â ñîñòàâ ñâîáîäíî ðàñïðîñòðàíÿåìîãî êîìïàíèåé «ßíäåêñ» ïðîäóêòà ßndex.Server 3.8 Free Edition¹ è ñîñòîÿùåãî èç 279

1 http://company.yandex.ru/technology/products/yandex-server.xml

÷àñòî óïîòðåáèìûõ ñëîâ ðóññêîãî è àíãëèéñêîãî ÿçûêîâ.

Äëÿ óäàëåíèÿ HTML-ðàçìåòêè èñïîëüçîâàëàñü îòêðûòàÿ Java-áèáëèîòåêà HTML Parser², ïðåäîñ-òàâëÿþùàÿ äàííóþ ôóíêöèîíàëüíîñòü.

Â êîíå÷íîì èòîãå êàæäîìó äîêóìåíòó ñòàâèëñÿ â ñîîòâåòñòâèå 128-áèòíûé MD5-õåø, ïîëó÷åí-íûé èç ñãåíåðèðîâàííîé ñèãíàòóðû. Â ñîîòâåò-ñòâèè ñ [10], MD5 äàåò çíà÷èòåëüíî ìåíüøåå ÷èñ-ëî ÷èñ-ëîæíûõ ñðàáàòûâàíèé, ÷åì 40-áèòíûé õåø Ðàáèíà, èñïîëüçîâàííûé â ðàííèõ èññëåäîâàíèÿõ, ïðè ñîõðàíåíèè äîñòàòî÷íî âûñîêîé ñêîðîñòè ãå-íåðàöèè.

Ïðîãðàììíàÿ ðåàëèçàöèÿ îïèñàííûõ ìåòîäîâ âêëþ÷àëà â ñåáÿ ðåàëèçàöèþ ñëåäóþùèõ ýòàïîâ:

1. Ïîäãîòîâêà òåñòîâûõ äàííûõ:

a. Ïàðñèíã çàãîëîâêîâ è èíäåêñîâ äîêóìåíòîâ èç ïðåäîñòàâëåííîãî íàáîðà äàííûõ â ñîáñòâåííóþ áàçó äàííûõ.

b. Çàïîëíåíèå ñâåäåíèé îá èçâåñòíûõ ïàðàõ äîêóìåíòîâ-äóáëèêàòîâ.

2. Íàáîð ýêñïåðèìåíòîâ, äëÿ êàæäîãî èç êîòî-ðûõ âûïîëíÿëèñü:

a. Ãåíåðàöèÿ õåøåé äëÿ êàæäîãî äîêóìåíòà.

i. Óäàëåíèå HTML-ðàçìåòêè (åñëè òðåáîâà-ëîñü).

ii. Ïîñòðîåíèå ñèãíàòóðû â ñîîòâåòñòâèè ñ êîíêðåòíûì àëãîðèòìîì òåñòà.

iii. Õåøèðîâàíèå.

b. Àíàëèç ðåçóëüòàòîâ ýêñïåðèìåíòà ñ èñïîëü-çîâàíèåì îïèñàííûõ âûøå ìåòðèê.

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

4.3. Ýêñïåðèìåíòû

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

Òåñò ¹ 1: êîëè÷åñòâî ñïåöñèìâîëîâ è çíàêîâ ïðå-ïèíàíèÿ.

Ïîäñ÷èòûâàëîñü ÷èñëî âõîæäåíèé â òåêñò äî-êóìåíòà d êàæäîãî ñèìâîëà èç íàáîðà p, âêëþ÷àâ-øåãî â ñåáÿ ñëåäóþùèå ýëåìåíòû:

., _ : ; ! ? () è ñèìâîë ïðîáåëà.

Äîêóìåíò ïðåäñòàâëÿëñÿ â âèäå âåêòîðà ðàç-ìåðíîñòüþ 11 ýëåìåíòîâ, êîìïîíåíòàìè êîòîðîãî ÿâëÿëîñü ÷èñëî âõîæäåíèé êàæäîãî ñèìâîëà â äîêóìåíò.

s = (c₁,c₂,,c₁₁), ãäå c_i= Count(d, p_i).

Òåñò ¹ 2: êîëè÷åñòâî ñëîâ ðàçëè÷íûõ äëèí.

Ïîäñ÷èòûâàëîñü ÷èñëî âõîæäåíèé ñëîâ ðàçëè÷-íûõ äëèí â òåêñò äîêóìåíòà (çäåñü è äàëåå ïîä ñëîâîì ïîäðàçóìåâàåòñÿ íåïðåðûâíàÿ àëôàâèòíî-öèôðîâàÿ ïîñëåäîâàòåëüíîñòü). Äîêóìåíò ïðåäñòàâ-ëÿëñÿ â âèäå âåêòîðà ðàçìåðíîñòüþ, ðàâíîé äëèíå ñàìîãî äëèííîãî ñëîâà äîêóìåíòà L. Êîìïîíåíòà-ìè âåêòîðà ÿâëÿëàñü ñòðîêà âèäà: «[äëèíà ñëî-âà] [÷èñëî âõîæäåíèé]».

s = (c₁,c₂,,c_L),

ãäå c_i= d_i + Count(d, d_i), L = Max(Length(d_i)).

Òåñò ¹ 3: êîëè÷åñòâî è ñðåäíÿÿ äëèíà ñëîâ è ïðåä-ëîæåíèé.

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

«[ñðåäíÿÿ äëèíà ñëîâà] [ñðåäíÿÿ äëèíà ïðåäëî-æåíèÿ] [÷èñëî ñëîâ] [îáùåå ÷èñëî ïðåäëîæå-íèé]».

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

Òåñò ¹ 4: ïîïóëÿðíûå ñëîâà.

Ïîäñ÷èòûâàëîñü ÷èñëî ïîâòîðåíèé êàæäîãî ñëîâà â òåêñòå äîêóìåíòà. Äîêóìåíò ðàçáèâàëñÿ íà òåðìû è ïðåäñòàâëÿëñÿ â âèäå âåêòîðà, ðàçìåð-íîñòü êîòîðîãî ðàâíà ðàçìåðó ñëîâàðÿ äîêóìåíòàn.

Êîìïîíåíòàìè âåêòîðà ÿâëÿëàñü ñòðîêà âèäà: «[ñëî-âî] [÷èñëî âõîæäåíèé]».

s = (c₁,c₂,,c_n), ãäå c_i= d + Count(d, d_i).

Èñïîëüçóåìûé â äàííîì ýêñïåðèìåíòå àëãîðèòì èìååò îòäàëåííîå ñõîäñòâî ñ àëãîðèòìîì I-Match, îäíàêî èìåþòñÿ äâà ñóùåñòâåííûõ

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

Áûëè òàêæå ïðîòåñòèðîâàíû ñëåäóþùèå ìîäè-ôèêàöèè àëãîðèòìà:

îáðåçêà 2035 % ñ êàæäîé ñòîðîíû îòñîðòèðî-âàííîãî ïî êîëè÷åñòâó âõîæäåíèé ñïèñêà ñëîâ íå îêàçàëà çàìåòíîãî âëèÿíèÿ (ìåíåå 1 %);

èñïîëüçîâàíèå â êà÷åñòâå åäèíèö íå ñëîâ, à ïðåäëîæåíèé íå îêàçàëî çàìåòíîãî âëèÿíèÿ (ìå-íåå 1 %);

îòñîðòèðîâàííûé ïî ÷èñëó âõîæäåíèé ñïèñîê ñëîâ, íîðìàëèçîâàííûé è îêðóãëåííûé äî ïåðâîãî çíàêà ïîñëå çàïÿòîé äàë âûèãðûø â òî÷íîñòè â ðàç-ìåðå 12 %.

Òåñò ¹ 5: ïîñëåäîâàòåëüíîñòü äëèí ñëîâ.

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

Òåñò ¹ 6: àãðåãàòíûé.

Ñîâîêóïíûé òåñò, ñîáèðàþùèé âñå ïðåäûäó-ùèå òåñòû â îäèí. Ñèãíàòóðà ñîáèðàëàñü êîíêàòå-íàöèåé ñèãíàòóð òåñòîâ 15.

Ðåçóëüòàòû òåñòîâ ïðèâåäåíû â òàáë. 16. Ðàñøèô-ðîâêà çàãîëîâêîâ òàáëèö:

Ïîðîã ïîðîãîâàÿ âåëè÷èíà ñõîäñòâà äîêóìåí-òîâ â ñîîòâåòñòâèè ñ ôóíêöèåé Ëåâåíøòàéíà, ñ êî-òîðîé îíè ñ÷èòàþòñÿ ñõîæèìè;

ÐÎÌÈÏ ÷èñëî äóáëèêàòîâ ïî âåðñèè òåñòî-âîãî íàáîðà äàííûõ;

2 http://htmlparser.sourceforge.net/

Òåñò ÷èñëî äóáëèêàòîâ, ïîëó÷åííîå â ðåçóëü-òàòå òåñòà;

Îáùèå ÷èñëî ñîâïàäåíèé ïàð äóáëèêàòîâ òåñ-òà è ÐÎÌÈÏ;

Òàáëèöà 1 Ðåçóëüòàòû òåñòà ¹ 1