1308ｨｪｨｪ06ｨｰｨ 02ｨｨ ｨｮ09ｨｺｨｪｨ 07 ｨｺ09ｨ 05ｨｨ00ｨｨｨｺｨ 02ｨｨ06ｨｪｨｪｨ 07 08ｨ ｨ 06ｨｰｨ ｨｪｨ ｨｰ02ｨｬｨｮ 0604ｨ ｨｪｨｪｨ 07 09ｨｨ09ｨｰ02ｨｬｨ 0108ｨ ｨ

Ïðàâèòåëüñòâî Ðîññèéñêîé Ôåäåðàöèè Ôåäåðàëüíîå ãîñóäàðñòâåííîå àâòîíîìíîå îáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãî ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ

Íàöèîíàëüíûé èññëåäîâàòåëüñêèé óíèâåðñèòåò

¾Âûñøàÿ øêîëà ýêîíîìèêè¿

Îòäåëåíèå ïðîãðàììíîé èíæåíåðèè

Êàôåäðà Óïðàâëåíèÿ ðàçðàáîòêîé ïðîãðàììíîãî îáåñïå÷åíèÿ

ÂÛÏÓÑÊÍÀß ÊÂÀËÈÔÈÊÀÖÈÎÍÍÀß ÐÀÁÎÒÀ

òåìà:

Ðàñïðåäåëåííàÿ ñèñòåìà

õðàíåíèÿ è ðóáðèêàöèè

äîêóìåíòîâ

Distributed System for Document

Storage and Clustering

Íàïðàâëåíèå 010400 - Ïðîãðàììíàÿ èíæåíåðèÿ

Âûïîëíèë: ñòóäåíò ãðóïïû 271ìÓÐÏÎ Ä. Ñ. Ôðîëîâ Íàó÷íûé ðóêîâîäèòåëü: ïðîôåññîð, ä. ò. í Á. Ã. Ìèðêèí

Àííîòàöèÿ

Âûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà íà òåìó ¾Ðàñïðåäåëåííàÿ ñèñòåìà õðàíåíèÿ è ðóáðèêàöèè äîêóìåíòîâ¿ èìååò îáúåì 43 ñòðàíèöû, ñîäåðæèò 5 ðèñóíêîâ è 4 òàáëèöû. Ïðè ïîäãîòîâêå ðàáîòû èñïîëüçîâàíî 47 èñòî÷íèêîâ.  ñòðóêòóðó ðàáîòû âõîäèò ââåäåíèå, îáçîð ëèòåðàòóðû è ïîõîæèõ ðåøåíèé, 2 ñîäåðæàòåëüíûå ãëàâû, ãëàâà îá ýêñïåðèìåíòàëüíîé àïðîáàöèè ðàçðàáîòàííîé ñèñòåìû è çàêëþ÷åíèå. Ðàáîòà ïîñâÿùåíà ðàçðàáîòêå è ýêñïåðèìåíòàëüíîé àïðîáàöèè ðàñïðåäåëåííîé ñèñòåìû îáðàáîòêè êîëëåêöèé òåêñòîâûõ äîêóìåíòîâ.  ðàáîòå ðåàëèçîâàíû ìå-òîäû ðóáðèêàöèè êîëëåêöèé äîêóìåíòîâ íà îñíîâå ìîäåëåé ñêðûòîãî ðàçìåùåíèÿ Äèðèõëå (LDA) è âåðîÿòíîñòíîãî ëàòåíòíîãî ñåìàíòè÷åñêîãî àíàëèçà (PLSI), ðåà-ëèçîâàíû ñðåäñòâà ïîèñêà è èçâëå÷åíèÿ äîêóìåíòîâ íà îñíîâå ýòèõ ìîäåëåé, à òàê-æå ðàçðàáîòàííîé àâòîðîì ïîèñêîâîé ìàøèíû íà áàçå àííîòèðîâàííûõ ñóôôèêñ-íûõ äåðåâüåâ (ÀÑÄ) ñ ïðåäâàðèòåëüíîé îáðàáîòêîé êîëëåêöèè. Âî âðåìÿ ïðåäâà-ðèòåëüíîé îáðàáîòêè êîëëåêöèè ïðîèñõîäèò ïîñòðîåíèå ñïåöèàëüíîé ñòðóêòóðû äàííûõ, èñïîëüçóåìîé äëÿ ñîêðàùåíèÿ âðåìåíè âûïîëíåíèÿ ïîèñêîâîãî çàïðîñà. Ðåàëèçîâàííûå ìåòîäû âêëþ÷åíû â ðàáîòàþùóþ ðàñïðåäåëåííóþ ñèñòåìó îáðà-áîòêè êîëëåêöèé äîêóìåíòîâ. Ïðîâåäåíî ýêñïåðèìåíòàëüíîå ñðàâíåíèå ðåàëèçî-âàííûõ ìåòîäîâ, â êà÷åñòâå êîëëåêöèé äîêóìåíòîâ áûëè âçÿòû òîâàðíûå êàòàëîãè èíòåðíåò-ìàãàçèíà ¾Îçîí¿, íàõîäÿùèåñÿ â ñâîáîäíîì äîñòóïå. Íà îñíîâàíèè ýòîãî ñäåëàí âûâîä, ÷òî ñäåëàííûå ìîäèôèêàöèè ñïîñîáíû â ðÿäå ñëó÷àåâ êàê óëó÷øèòü êà÷åñòâî ïîèñêà äîêóìåíòîâ è óñêîðèòü ïðîöåññ ïîèñêà äîêóìåíòîâ â êîëëåêöèè, òàê è ñîêðàòèòü âðåìÿ, çàòðà÷èâàåìîå íà îáðàáîòêó êîëëåêöèé. Êëþ÷åâûå ñëîâà: ñêðûòîå ðàçìåùåíèå Äèðèõëå (LDA), âåðîÿòíîñòíûé ëà-òåíòíûé ñåìàíòè÷åñêèé àíàëèç (PLSI), àííîòèðîâàííûå ñóôôèêñíûå äåðåâüÿ (ÀÑÄ), ðóáðèêàöèÿ òåêñòîâ, ñèñòåìû ïîèñêà äîêóìåíòîâ, ðàñïðåäåëåííûå ñèñòåìû îáðàáîòêè òåêñòîâûõ äîêóìåíòîâ

Îãëàâëåíèå

Ââåäåíèå 5 0.1 Ââåäåíèå . . . 5 0.2 Ïîñòàíîâêà çàäà÷è . . . 5 0.3 Àêòóàëüíîñòü ðàáîòû . . . 6 0.4 Íîâèçíà ðàáîòû . . . 7 1 Îáçîð ëèòåðàòóðû è ïîõîæèõ ðàáîò 8 1.1 Ñóùåñòâóþùèå ïîäõîäû ê ðóáðèêàöèè è ïîèñêó äîêóìåíòîâ (íà ïðèìåðå âåá-ñòðàíèö ñàéòîâ) . . . 8 1.1.1 Ìåòîäû ðóáðèêàöèè äîêóìåíòîâ . . . 8 1.1.2 Ìåòîäû ïîèñêà äîêóìåíòîâ . . . 8 1.2 Ñóùåñòâóþùèå ïðîãðàììíûå ñèñòåìû îáðàáîòêè êîëëåêöèé äîêóìåíòîâ . . . 9 1.2.1 Áèáëèîòåêà gensim . . . 9 1.2.2 Ñèñòåìà texterra . . . 11 2 Ìåòîäû îáðàáîòêè òåêñòîâ íà åñòåñòâåííîì ÿçûêå 12 2.1 Ñïîñîáû ïðåäñòàâëåíèÿ òåêñòîâ . . . 12 2.1.1 Îñíîâíûå ïîäõîäû . . . 12 2.1.2 Ïðèçíàêîâîå îïèñàíèå äîêóìåíòîâ . . . 12 2.1.3 Ôðàãìåíòíîå ïðåäñòàâëåíèå òåêñòà . . . 14 2.2 Ñïîñîáû îáðàáîòêè êîëëåêöèé äîêóìåíòîâ . . . 16 2.2.1 Çàäà÷à âåðîÿòíîñòíîãî òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ . . . 16 2.2.2 Âåðîÿòíîñòíûé ëàòåíòíûé ñåìàíòè÷åñêèé àíàëèç . . . 17 2.2.3 Ñêðûòîå ðàçìåùåíèå Äèðèõëå . . . 18 2.2.4 Áîëåå ñëîæíûå ìîäåëè . . . 19 2.3 Ðóáðèêàöèÿ äîêóìåíòîâ â êîëëåêöèè . . . 20

2.3.1 Êëàñòåðèçàöèÿ äîêóìåíòîâ êàê ðóáðèêàöèÿ . . . 20 2.3.2 Ðóáðèêàöèÿ â âåðîÿòíîñòíîì òåìàòè÷åñêîì ìîäåëèðîâàíèè . . . 21 2.4 Ïîèñê äîêóìåíòîâ êîëëåêöèè . . . 21 2.4.1 Ïîèñê â ìîäåëÿõ PLSI è LDA . . . 21 2.4.2 Ïîèñêîâàÿ ìàøèíà íà îñíîâå ÀÑÄ . . . 21 3 Ïðîåêòèðîâàíèå è ðåàëèçàöèÿ ñèñòåìû 23 3.1 Ôóíêöèè ñèñòåìû . . . 23 3.2 Àðõèòåêòóðà è èíñòðóìåíòû ðåàëèçàöèè . . . 24 3.2.1 Âûñîêîóðîâíåâàÿ àðõèòåêòóðà . . . 24 3.2.2 Àðõèòåêòóðà óçëà . . . 25 3.2.3 Èíñòðóìåíòû ðåàëèçàöèè ñèñòåìû . . . 27 3.2.4 Èíñòðóìåíòû äëÿ ðåàëèçàöèè î÷åðåäè çàäà÷ è ïàðàëëåëüíîé îáðàáîòêè . . . 27 3.2.5 Ïðåäâàðèòåëüíàÿ îáðàáîòêà äîêóìåíòîâ . . . 28 4 Ýêñïåðèìåíòàëüíàÿ àïðîáàöèÿ 30 4.1 Êîëëåêöèè äîêóìåíòîâ . . . 30 4.2 Ñðàâíåíèå âðåìåíè îáðàáîòêè êîëëåêöèé . . . 31 4.3 Ñðàâíåíèå ñêîðîñòè ïîèñêà . . . 32 4.4 Ñðàâíåíèå êà÷åñòâà ïîèñêà . . . 33 4.5 Âûâîäû . . . 38 Çàêëþ÷åíèå 39 Áèáëèîãðàôè÷åñêèé ñïèñîê èñïîëüçîâàííîé ëèòåðàòóðû 40

Ââåäåíèå

0.1 Ââåäåíèå

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

0.2 Ïîñòàíîâêà çàäà÷è

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

õðàíèëè-ùàõ. Äðóãîå íàïðàâëåíèå  èñïîëüçîâàíèå àãðåãèðîâàííîãî ïðåäñòàâëåíèÿ êîë-ëåêöèé òåêñòîâûõ äîêóìåíòîâ, äàâàåìûõ òàêèìè ñîâðåìåííûìè ïîäõîäàìè, êàê ñêðûòîå ðàçìåùåíèå Äèðèõëå (LDA), âåðîÿòíîñòíûé ëàòåíòíûé ñåìàíòè÷åñêèé àíàëèç (PLSI), àííîòèðîâàííûå ñóôôèêñíûå äåðåâüÿ (ÀÑÄ). Ïîýòîìó öåëüþ ðà-áîòû ÿâëÿåòñÿ ðàçðàáîòêà ðàñïðåäåëåííîé ñèñòåìû õðàíåíèÿ è ðåäàêòèðîâàíèÿ êîëëåêöèé äîêóìåíòîâ, îñíîâàííîé íà ñîâðåìåííûõ ïîäõîäàõ ê àãðåãèðîâàííîìó ïðåäñòàâëåíèþ, à òàêæå èõ ýêñïåðèìåíòàëüíîå ñðàâíåíèå. Äëÿ äîñòèæåíèÿ ïîñòàâëåííîé öåëè íåîáõîäèìî ðåøèòü çàäà÷è: 1) ðåàëèçîâàòü àëãîðèòìû ïðåäâàðèòåëüíîé îáðàáîòêè äîêóìåíòîâ íà ðóññêîì è àíãëèéñêîì ÿçûêàõ; 2) ðåàëèçîâàòü àëãîðèòìû PLSI, LDA, ÀÑÄ äëÿ àãðåãèðîâàííîãî ïðåäñòàâëå-íèÿ êîëëåêöèé äîêóìåíòîâ; 3) îïðåäåëèòü ôîðìàò õðàíåíèÿ äàííûõ î êîëëåêöèè â ÁÄ; 4) îïðåäåëèòü ôîðìàò îáìåíà äàííûìè ìåæäó óçëîì-ìàñòåðîì è ïîä÷èíåííû-ìè óçëàïîä÷èíåííû-ìè; 5) ñäåëàòü ïðîãðàììíóþ ðåàëèçàöèþ óçëà-ìàñòåðà; 6) ñäåëàòü ïðîãðàììíóþ ðåàëèçàöèþ ïîä÷èíåííîãî óçëà; 7) ðåàëèçîâàòü ïðèëîæåíèå ñ âîçìîæíîñòüþ äîáàâëåíèÿ è ðàñøèðåíèÿ êîëëåê-öèè äîêóìåíòîâ, ïîèñêà äîêóìåíòîâ; 8) ïðîâåñòè ýêñïåðèìåíòû ïî ñðàâíåíèþ ðåçóëüòàòîâ èñïîëüçîâàíèÿ ðàçíûõ ïîäõîäîâ íà ðåàëüíûõ äàííûõ.

0.3 Àêòóàëüíîñòü ðàáîòû

Àêòóàëüíîñòü ðàáîòû îïðåäåëÿþòñÿ íåîáõîäèìîñòüþ ïðîäâèæåíèÿ â ñëåäóþùèõ íàïðàâëåíèÿõ: 1) àâòîìàòèçàöèÿ àíàëèçà òåêñòîâîé èíôîðìàöèè; 2) ïîâûøåíèå ñêîðîñòè ðóáðèêàöèè è ïîèñêà äîêóìåíòîâ; 3) ïîâûøåíèå êà÷åñòâà ïîèñêà äîêóìåíòîâ; 4) îáåñïå÷åíèå âîçìîæíîñòè ðàñïðåäåëåííîãî õðàíåíèÿ äîêóìåíòîâ;

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

0.4 Íîâèçíà ðàáîòû

 äàííîé ðàáîòå ìû îáúåäèíèëè íåñêîëüêî ýòàïîâ, îò ïðåäâàðèòåëüíîé îáðàáîòêè ïðèçíàêîâ äîêóìåíòîâ äî ðàáîòû ñ êîëëåêöèåé äîêóìåíòîâ öåëèêîì, ïðèìåíåíà ðàñïðåäåëåííàÿ îáðàáîòêà äîêóìåíòîâ è êîëëåêöèè. Ðåàëèçîâàíà ïîèñêîâàÿ ìà-øèíà íà îñíîâå àííîòèðîâàííûõ ñóôôèêñíûõ äåðåâüåâ ñ ïðåäâàðèòåëüíîé îáðà-áîòêîé êîëëåêöèè. Îáçîð ïîõîæèõ ðàáîò ïðåäñòàâëåí â ðàçäåëå íèæå. Ê çàäà÷å ïîèñêà äîêóìåíòîâ â êîëëåêöèè ïðèìåíåí íîâûé ïðèíöèï, êîãäà ïî-èñê îñóùåñòâëÿåòñÿ ïî ïðåäâàðèòåëüíî àãðåãèðîâàííîé èíôîðìàöèè î êîëëåêöèè äîêóìåíòîâ. Ýòîò ïðèíöèï ðåàëèçîâàí ñ ïîìîùüþ ðàçíûõ ïîäõîäîâ ê àãðåãèðî-âàíèþ, ðàçâèâàåìûõ â ëèòåðàòóðå (ñêðûòîå ðàçìåùåíèå Äèðèõëå (LDA), âåðîÿò-íîñòíûé ëàòåíòíûé ñåìàíòè÷åñêèé àíàëèç (PLSI), àííîòèðîâàííûå ñóôôèêñíûå äåðåâüÿ (ÀÑÄ)) â ðàáîòàþùåé ïðîãðàììíîé ñèñòåìå. Ïðîâåäåíû ýêñïåðèìåíòû íà ðåàëüíûõ äàííûõ, ïîêàçûâàþùèå ïðåèìóùåñòâà òîãî èëè èíîãî ïîäõîäà äëÿ òîãî èëè èíîãî òèïà çàïðîñîâ.

Ãëàâà 1

Îáçîð ëèòåðàòóðû è ïîõîæèõ ðàáîò

1.1 Ñóùåñòâóþùèå ïîäõîäû ê ðóáðèêàöèè

è ïîèñêó äîêóìåíòîâ

(íà ïðèìåðå âåá-ñòðàíèö ñàéòîâ)

1.1.1 Ìåòîäû ðóáðèêàöèè äîêóìåíòîâ

Ëþáîé âåá-ñàéò â ñèñòåìå Èíòåðíåò ìîæíî ðàññìàòðèâàòü êàê êîëëåêöèþ äîêó-ìåíòîâ  âåá-ñòðàíèö ýòîãî ñàéòà. Äîâîëüíî ÷àñòî âñòðå÷àåòñÿ çàäà÷à ðóáðèêàöèè âåá-ñòðàíèö ñàéòà è çàäà÷à ïîèñêà âåá-ñòðàíèö, ðåëåâàíòíûõ çàïðîñó. Äëÿ ðåøåíèÿ ïåðâîé çàäà÷è ÷àñòî ñîçäàòåëÿìè ñàéòîâ óæå ïðåäóñìîòðåíû òå-ìàòè÷åñêèå êàòàëîãè. Îäíàêî ïðè èõ îòñóòñòâèè ìîæåò ïîòðåáîâàòüñÿ ïðîèçâåñòè àâòîìàòè÷åñêóþ êëàñòåðèçàöèþ ñòðàíèö. Îòìåòèì èçâåñòíûå ðàáîòû [30, 31].  [30] èññëåäóþòñÿ ðàçëè÷íûå ðàññòîÿíèÿ ìåæäó âåá-ñòðàíèöàìè. Ðàçëè÷íûå ðàñ-ñòîÿíèÿ ìåæäó äîêóìåíòàìè ïðèâîäÿò ê ðàçëè÷íûì ðåçóëüòàòàì êëàñòåðèçàöèè, â ðàáîòå ðàññìàòðèâàþòñÿ è âàðèàíòû íåñèììåòðè÷íûõ ðàññòîÿíèé.  [31] ðàñ-ñìàòðèìàåòñÿ, êàê ñåòü ãèïåðññûëîê, ñîåäèíÿþùèõ ñòðàíèöû, ìîæåò áûòü ïðèìå-íåíà äëÿ áîëåå òî÷íîé êëàñòåðèçàöèè.  áîëåå ñâåæåé ðàáîòå [32] ðàññìàòðèâàåòñÿ êëàñòåðèçàöèÿ íà îñíîâå ïîèñêîâûõ çàïðîñîâ.

1.1.2 Ìåòîäû ïîèñêà äîêóìåíòîâ

Çàäà÷à ïîèñêà äîêóìåíòîâ ïî çàïðîñó íå ìåíåå èíòåðåñíà. Íåëüçÿ íå îòìåòèòü øèðîêî èçâåñòíóþ êíèãó Ê. Ìàííèíãà ¾Ââåäåíèå â èíôîðìàöèîííûé ïîèñê¿ [4], íåîäíîêðàòíî ïåðåèçäàííóþ è ïåðåâåäåííóþ íà ðóññêèé ÿçûê, êîòîðàÿ ìîæåò ÿâ-ëÿåòñÿ áàçîâûì ïîñîáèåì ïðè èçó÷åíèè çàäà÷ èíôîðìàöèîííîãî ïîèñêà.  ðàáîòå

[33], èìåþùåé ñêîðåå íàó÷íî-ïîïóëÿðíûé õàðàêòåð, îïèñûâàþòñÿ ìíîãèå ìåòîäû è òåõíèêè, ïðèìåíÿåìûå â êðóïíåéøåé â ìèðå ïîèñêîâîé ñèñòåìå Google.  [34] ðàñ-ñìàòðèâàþòñÿ ñðåäñòâà ïîèñêà â òîì ÷èñëå è äëÿ òàêèõ ñïåöèôè÷åñêèõ äîêóìåí-òîâ, êàê ñòðàíèöû èíòåðíåò-ôîðóìîâ, ãäå îñíîâíàÿ äîëÿ èíôîðìàöèè ñîçäàåòñÿ ïîëüçîâàòåëÿìè.  ïðîñòåéøåì ñëó÷àå çàäà÷ó ïîèñêà äîêóìåíòîâ ïî çàïðîñó ìîæíî ðàññìàòðè-âàòü êàê çàäà÷ó ïîëíîòåêñòîâîãî ïîèñêà èëè äàæå ýëåìåíòàðíóþ çàäà÷ó î ïîèñêå ïîäñòðîêè â ñòðîêå. Çäåñü ñóùåñòâóåò ìíîæåñòâî ìåòîäèê, î êîòîðûõ ãîâîðèòñÿ, íàïðèìåð, â ðàáîòàõ [35, 36]. Ïðèìåíÿåìûå òåõíèêè íàïðàâëåíû, â îñíîâíîì, íà ñîáëþäåíèå ðàçóìíîãî áàëàíñà ìåæäó êà÷åñòâîì ðåçóëüòàòîâ, íàéäåííûõ ïî ïîèñ-êîâîìó çàïðîñó, è âðåìåíåì âûïîëíåíèÿ çàïðîñà. Îáúåäèíåíèå êîëëåêöèé âåá-ñàéòîâ ïðèâîäèò ê î÷åíü ìàñøòàáíîé çàäà÷å ïîèñ-êà ñòðàíèö, êîòîðóþ ðåøàþò ïîèñêîâûå ñèñòåìû. Çäåñü îòìåòèì îáçîðíóþ ðàáîòó È. Ñåãàëîâè÷à [20], ïî ïðàâó ñ÷èòàþùóþñÿ ñâîåãî ðîäà ¾êëàññèêîé¿ ñðåäè ïîäîá-íûõ îáçîðîâ. Ñðåäè íàáîðà òåõíîëîãèé, ðàññìîòðåíïîäîá-íûõ È. Ñåãàëîâè÷åì, îòìåòèì ìåòîäû ïîèñêîâûõ èíäåêñîâ, ïðèìåíÿþùèåñÿ äëÿ ðàáîòû ñ áîëüøèìè êîëëåêöèÿ-ìè äîêóìåíòîâ.

1.2 Ñóùåñòâóþùèå ïðîãðàììíûå ñèñòåìû

îáðàáîòêè êîëëåêöèé äîêóìåíòîâ

1.2.1 Áèáëèîòåêà gensim

Îäíèì èç íàèáîëåå èçâåñòíûõ ñóùåñòâóþùèõ ñðåäñòâ ðàáîòû ñ êîëëåêöèÿìè äî-êóìåíòîâ ÿâëÿåòñÿ ïàêåò gensim, ðàçðàáîòàííûé äëÿ ÿçûêà python êîìàíäîé ñïå-öèàëèñòîâ ïîä ðóêîâîäñòâîì Ðàäèìà Ðåõóðåêà [23]. Ïðîåêò gensim áûë íà÷àò â 2008 ãîäó êàê íàáîð ïðîãðàìì äëÿ âû÷èñëåíèÿ ðàç-ëè÷íûõ ðàññòîÿíèé ìåæäó òåêñòîâûìè äîêóìåíòàìè.  2009 ãîäó áûë ðàçðàáîòàí ïîëíîöåííûé ïàêåò ôóíêöèé äëÿ âåðîÿòíîñòíîãî òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ.  íàñòîÿùåå âðåìÿ ïðîåêò ðàñïðîñòðàíÿåòñÿ ïîä ëèöåíçèåé GNU LGPL, ÷òî äåëàåò åãî ñâîáîäíûì êàê äëÿ ïåðñîíàëüíîãî. òàê è äëÿ êîììåð÷åñêîãî èñïîëüçîâàíèÿ.

Ïàêåò gensim èìååò äâà îñíîâíûõ íàïðàâëåíèÿ èñïîëüçîâàíèÿ. Ïåðâûé  îá-ðàáîòêà êîëëåêöèè äîêóìåíòîâ ñ ïîìîùüþ ìåòîäîâ PLSA è LDA (ñ ìîäèôèêà-öèÿìè). Âòîðîé  ðåàëèçàöèÿ ïîèñêîâîé ìàøèíû íà áàçå ïîñòðîåííîé ÂÒÌ. Âî âòîðîì ñëó÷àå, íåñìîòðÿ íà ðÿä âîçìîæíîñòåé ïî óëó÷øåíèþ ïðîèçâîäèòåëüíî-ñòè, ïîèñê ðàáîòàåò ìåäëåííî íà äîñòàòî÷íî áîëüøè õ êîëëåêöèÿõ. Ýòî ïîêàçàëè ðåçóëüòàòû ïðîñòûõ ýêñïåðèìåíòîâ, ïðèâåäåííûå â òàáëèöå 1.1. Òàáëèöà 1.1. Ñðåäíåå âðåìÿ âûïîëíåíèÿ çàïðîñà èç îäíîãî ñëîâà â ñèñòåìå gensim Êîëè÷åñòâî äîêóìåíòîâ â êîë-ëåêöèè 104 105 2× 105 3× 105 Ñðåäíåå âðåìÿ âûïîëíåíèÿ çà-ïðîñà èç îäíîãî ñëîâà, ñ 0.72 1.35 2.21 2.83 Ìîæíî ñäåëàòü âûâîä, ÷òî ïîèñêîâàÿ ìàøèíà, ðåàëèçîâàííàÿ â gensim, ñëàáî ïîäõîäèò äëÿ èñïîëüçîâàíèÿ â ïðîåêòàõ, êîãäà êîëè÷åñòâî äîêóìåíòîâ â êîëëåê-öèè ïðåâîñõîäèò 105_{. Êðîìå òîãî, âðåìÿ çàïðîñà ïðàêòè÷åñêè íå çàâèñèò îò åãî} äëèíû â ïðèçíàêàõ (çàâèñèìîñòü åñòü ëèøü ïðè âûïîëíåíèè ïðåäâàðèòåëüíîé îá-ðàáîòêè çàïðîñà, íåîáõîäèìîé äëÿ gensim). Áîëüøèíñòâî ïîèñêîâûõ çàïðîñîâ âû-ïîëíÿåòñÿ äëÿ êîðîòêèõ çàïðîñîâ (1-10 ïðèçíàêîâ), äëèííûå çàïðîñû ïåðåâîäÿò ýòó çàäà÷ó â ïðîáëåìó âûÿâëåíèÿ ïîõîæèõ íà çàäàííûé äîêóìåíòîâ. Îòìåòèì òàêæå, ÷òî ïàêåò âêëþ÷àåò è ðåàëèçàöèþ áàçîâûõ ïðåîáðàçîâàíèé, òàêèõ êàê TF-IDF [23]. Îäíàêî áîëåå ñëîæíûå ìåòîäû ïðåîáðàçîâàíèé gensim ïðî-èçâîäèòü íå ïîçâîëÿåò. Òàêæå, íà íàø âçãëÿä, íåäîñòàòêîì áèáëèîòåêè ÿâëÿåòñÿ ïîëíîå îòñóòñòâèå âñòðîåííûõ ìåòîäîâ îáðàáîòêè ïðèçíàêîâ. ×àñòè÷íûì ðåøåíè-åì ýòîé ïðîáëðåøåíè-åìû âûãëÿäèò èñïîëüçîâàíèå gensim â ñîâîêóïíîñòè ñ èçâåñòíåéøåé áèáëèîòåêîé nltk [46], íî òàêîå ðåøåíèå òåõíè÷åñêè áóäåò î÷åíü ìàññèâíûì. Ïðè èçó÷åíèè ìåòîäîâ gensim è ïðîâåäåíèè ýêñïåðèìåíòîâ ñ ýòîé áèáëèîòåêîé àâòîðû èñïîëüçîâàëè ñîáñòâåííûå ñðåäñòâà îáðàáîòêè ïðèçíàêîâ.  íàøó ñèñòåìó ýòè ìåòîäû óæå âêëþ÷åíû.

1.2.2 Ñèñòåìà texterra

Èçâåñòíåéøåé ñèñòåìîé àíàëèçà òåêñòîâ ÿâëÿåòñÿ texterra, ðàçðàáàòûâàåìàÿ â Èíñòèòóòå Ñèñòåìíîãî Ïðîãðàììèðîâàíèÿ (ÈÑÏ) ÐÀÍ è îïèñàííàÿ â ðàáîòàõ [17, 18]. Ýòî Java-ôðåéìâîðê è áèáëèîòåêà ôóíêöèé (API) äëÿ ðàáîòû ñ íèì. Ñèñòåìà ïðåäîñòàâëÿåò ìíîæåñòâî ôóíêöèé, ñðåäè êîòîðûõ, íàïðèìåð, çàäà÷è ñèíòàêñè÷åñêîãî àíàëèçà, îïðåäåëåíèå ÷àñòåé ðå÷è è ò.ä. Îñîáåííîñòÿìè ñèñòåìû ÿâëÿåòñÿ èñïîëüçîâàíèå áàç çíàíèé, ñîçäàííûõ ïðè ïîìîùè ýêñïåðòîâ, è ðàñøè-ðÿåìîñòü àðõèòåêòóðû. Ñèñòåìà texterra óæå èñïîëüçóåòñÿ â íåñêîëüêèõ êîììåð÷åñêèõ ïðîåêòàõ [17], à òàêæå â ñåðâèñàõ ÈÑÏ ÐÀÍ. Ãëàâíîå îòëè÷èå äàííîé ñèñòåìû îò íàñòîÿùåé ðàáîòû  texterra íàïðàâëåíà íà ãëóáîêèé àíàëèç ñòðóêòóðû òåêñòà ñ èñïîëüçîâàíèåì ýêñïåðòíûõ çíàíèé, â òî âðåìÿ êàê ìû ðåøàåì çàäà÷è ðóáðèêàöèè è ïîèñêà äîêóìåíòîâ, íå ïðèáåãàÿ ê èñïîëüçîâàíèþ òàêèõ ñðåäñòâ.

Ãëàâà 2

Ìåòîäû îáðàáîòêè òåêñòîâ íà

åñòåñòâåííîì ÿçûêå

2.1 Ñïîñîáû ïðåäñòàâëåíèÿ òåêñòîâ

2.1.1 Îñíîâíûå ïîäõîäû

 íàñòîÿùåå âðåìÿ ñóùåñòâóåò ÷åòûðå îñíîâíûõ ïîäõîäà äëÿ ðàáîòû ñ òåêñòàìè [8]: 1) ïîïàðíîå íàëîæåíèå (âûðàâíèâàíèå) òåêñòîâ, 2) ôîðìèðîâàíèå ïðîôèëÿ è ñêðûòîé ìàðêîâñêîé ìîäåëè, 3) ïðèçíàêîâîå îïèñàíèå, 4) ïðåäñòàâëåíèå ôðàãìåíòàìè. Îò âûáîðà êîíêðåòíîãî ïîäõîäà çàâèñèò è äàëüíåéøåå ïîñòðîåíèå ìàòåìàòè÷å-ñêîé ìîäåëè, èñïîëüçóåìîé äëÿ ïðåäñòàâëåíèÿ âñåé êîëëåêöèè äîêóìåíòîâ. Îñòà-íîâèìñÿ ïîäðîáíåå íà äâóõ ïîñëåäíèõ ïîäõîäàõ, êîòîðûå ìû è ñîáèðàåìñÿ èñïîëü-çîâàòü â ñâîåé ðàáîòå.

2.1.2 Ïðèçíàêîâîå îïèñàíèå äîêóìåíòîâ

Äëÿ íà÷àëà ðàññìîòðèì îñíîâíûå ïðèíöèïû ðàáîòû ñ òåêñòàìè (äîêóìåíòàìè) íà åñòåñòâåííîì ÿçûêå, èñïîëüçóåìûå ïðè ïîäõîäå, îñíîâàííîì íà ðàáîòå ñ ïðèçíàêà-ìè. Ðàññìîòðèì ìíîæåñòâî (òàêæå ïðèìåíÿåòñÿ òåðìèí ¾êîëëåêöèÿ¿) òåêñòîâûõ äîêóìåíòîâ íà åñòåñòâåííîì ÿçûêå. Ïðåäïîëàãàåòñÿ, ÷òî âñå äîêóìåíòû â êîëëåê-öèè èìåþò îäèí è òîò æå ÿçûê.

Äëÿ âîçìîæíîñòè ïîñëåäóþùåé îáðàáîòêè äîêóìåíò ðàññìàòðèâàåòñÿ êàê ìíî-æåñòâî ñâîèõ ïðèçíàêîâ.  ñâîþ î÷åðåäü, ïðèçíàêàìè äîêóìåíòà ìîãóò ÿâëÿòüñÿ îòäåëüíûå ñëîâà èëè ïîñëåäîâàòåëüíîñòè íåñêîëüêèõ (äâóõ, òðåõ è òàê äàëåå) ïîä-ðÿä èäóùèõ ñëîâ. Ïîñòðîåííûå òàêèì îáðàçîì ïðèçíàêè íàçûâàþò n-ãðàììàìè, n - êîëè÷åñòâî ñëîâ â ïðèçíàêå. Ïðè n=2 ïðèçíàê íàçûâàþò áèãðàììîé. Êàê ïðàâè-ëî, íà ïðàêòèêå äëÿ ïðåäñòàâëåíèÿ äîêóìåíòîâ èñïîëüçóþòñÿ òîëüêî îòäåëüíûå ñëîâà è áèãðàììû. Îòìåòèì, ÷òî èñïîëüçîâàíèå áèãðàìì íàìíîãî óâåëè÷èâàåò êîëè÷åñòâî ïðèçíàêîâ, ñ êîòîðûìè ïðèõîäèòñÿ ðàáîòàòü, íî ïîçâîëÿåò ãîðàçäî ëó÷øå ¾÷óâñòâîâàòü¿ ñòðóêòóðó òåêñòà. Íàïðèìåð, ôðàçû ¾òåîðèÿ âåðîÿòíîñòåé¿ è ¾âåðîÿòíîñòü òåîðèè¿ ïîçâîëÿþò ñòðîèòü ïðåäïîëîæåíèÿ î äîêóìåíòàõ, èç êî-òîðûõ îíè ïîëó÷åíû.  ïåðâîì ñëó÷àå, ñêîðåå âñåãî, äîêóìåíò èìåë îòíîøåíèå ê ìàòåìàòè÷åñêîé äèñöèïëèíå, òîãäà êàê âòîðîé ñëó÷àé óæå íå ïîçâîëÿåò ñäåëàòü òàêîå ïðåäïîëîæåíèå. Ïðèçíàêè ìîãóò ïîäâåðãàòüñÿ ñòåììèðîâàíèþ è ëåììàòèçàöèè. Ñòåììèðî-âàíèå  ïðîöåññ, ïðè êîòîðîì èç ïîëíîé ôîðìû ïðèçíàêà âûäåëÿåòñÿ åãî îñíîâà, íàïðèìåð, âìåñòî ïðèçíàêà ¾êëóáíè÷íûé¿ èñïîëüçóåòñÿ ¾êëóáí¿ èëè ¾êëóáíè÷¿, â çàâèñèìîñòè îò ïðèìåíÿåìîãî àëãîðèòìà. Áîëüøèíñòâî àëãîðèòìîâ ñòåììèðîâà-íèÿ îñíîâàíî íà îòäåëåíèè îò ñëîâà ïðèñòàâîê, ñóôôèêñîâ è îêîí÷àíèé èç êàêîãî-ëèáî çàäàííîãî íàáîðà. Ëåììàòèçàöèÿ  ýòî ïðîöåññ ïðèâåäåíèÿ ñëîâà ê íîðìàëü-íîé ôîðìå (äëÿ ñóùåñòâèòåëüíûõ - èìåíèòåëüíûé ïàäåæ åäèíñòâåííîãî ÷èñëà, äëÿ ãëàãîëîâ - íåîïðåäåëåííàÿ ôîðìà è ò. ä.). Íàïðèìåð, ïðèçíàê ¾êàðòîôåëå-÷èñòêàìè¿ ïðåîáðàçóåòñÿ â ¾êàðòîôåëå÷èñòêà¿. ×àñòî ýòî ãîðàçäî áîëåå ñëîæíûé ïðîöåññ, íåæåëè ñòåììèðîâàíèå, ïîñêîëüêó íåîáõîäèìûì ÿâëåòñÿ íàëè÷èå ñëîâà-ðåé ðàçëè÷íûõ ôîðì ñëîâ, äàæå åñëè àëãîðèòì ïîçâîëÿåò ñòðîèòü ïðåäïîëîæåíèÿ (äëÿ ñëîâ íå èç ñëîâàðÿ). Äàííûå äåéñòâèÿ íåîáõîäèìû äëÿ âûÿâëåíèÿ ðàçëè÷-íûõ ôîðì îäíîãî è òîãî æå ïðèçíàêà è ñîêðàùåíèÿ èõ êîëè÷åñòâà. Ïðàêòè÷åñêèå ýêñïåðèìåíòû ïîêàçàëè, ÷òî äëÿ ðóññêîãî ÿçûêà öåëåñîîáðàçíåå èñïîëüçîâàòü ëåì-ìàòèçàöèþ, à äëÿ àíãëèéñêîãî - ñòåììèðîâàíèå. Ñëóæåáíûå è íàèáîëåå ÷àñòî âñòðå÷àþùèåñÿ ñëîâà, òàêèå êàê ïðåäëîãè, àð-òèêëè, ñîþçû è äðóãèå, êàê ïðàâèëî, íå ðàññìàòðèâàþò â êà÷åñòâå ïðèçíàêîâ. Ïðèìåðîì òàêèõ ñëîâ ÿâëÿþòñÿ ðóññêèå ¾è¿, ¾÷òî¿, àíãëèéñêèå ¾a¿, ¾the¿. Íà ïðàêòèêå èõ õðàíÿò â ñïåöèàëüíûõ ñëîâàðÿõ è ¾îòñåèâàþò¿ ïðè îáðàáîòêå òåêñòà. Òàêèå ñëîâà íàçûâàþò ñòîï-ñëîâàìè.

2.1.3 Ôðàãìåíòíîå ïðåäñòàâëåíèå òåêñòà

Äðóãîé ïîäõîä ê àíàëèçó äîêóìåíòîâ íà åñòåñòâåííîì ÿçûêå  ïðåäñòàâëåíèå òåê-ñòà íå â âèäå ìíîæåñòâà ïðèçíàêîâ, à â âèäå ïîñëåäîâàòåëüíîñòåé ñèìâîëîâ, ïðè-÷åì èìåííî â òîì ïîðÿäêå, êàê îíè ðàñïîëîæåíû â òåêñòå.  ýòîì ïîäõîäå èñïîëü-çóþòñÿ òàê íàçûâàåìûå àííîòèðîâàííûå ñóôôèêñíûå äåðåâüÿ. Äàäèì îïðåäåëåíèå èç [10]. Àííîòèðîâàííîå ñóôôèêñíîå äåðåâî (ÀÑÄ)  ýòî ñòðóêòóðà äàííûõ, èñ-ïîëüçóåìàÿ äëÿ âû÷èñëåíèÿ è õðàíåíèÿ âñåõ ôðàãìåíòîâ òåêñòà ñîâìåñòíî ñ èõ ÷àñòîòàìè. Îíà çàäà¼òñÿ êàê êîðíåâîå äåðåâî, â êîòîðîì êàæäûé óçåë ñîîòâåòñòâóåò îäíîìó ñèìâîëó è ïîìå÷åí ÷àñòîòîé òîãî ôðàãìåíòà òåêñòà, êîòîðûé êîäèðóåò ïóòü îò êîðíÿ äî äàííîãî óçëà. Ïðè èñïîëüçîâàíèè ÀÑÄ âåñü òåêñò ðàçáèâàåòñÿ íà ñòðîêè - öåïî÷êè ñèìâîëîâ. Êàê ïðàâèëî, îäíà ñòðîêà ôîðìèðóåòñÿ èç 2-4 ïîäðÿä èäóùèõ ñëîâ. Ïðèìåð ÀÑÄ äëÿ êîðîòêîé ñòðîêè ïðèâåäåí íà ðèñóíêå (2.1) Ðèñ. 2.1. Àííîòèðîâàííîå ñóôôèêñíîå äåðåâî äëÿ ñòðîêè ¾mining¿ Ñóôôèêñîì äëèíû k ñòðîêè s = s1s2. . . sN äëèíû N (0 < k ≤ N), ñîñòîÿùåé èç ñèìâîëîâ s1, s2, . . . , sN, íàçûâàåòñÿ ïîäñòðîêà sN−k. . . sN. Íàïðèìåð, äëÿ ñòðîêè ABCDE ñóôôèêñîì äëèíû 2 áóäåò ÿâëÿòüñÿ ïîäñòðîêà DE. Ïðèâåäåì îïèñàíèå àëãîðèòìà ïîñòðîåíèÿ ÀÑÄ ïî çàäàííîé ñòðîêå s.

1) Èíèöèàëèçèðîâàòü ïóñòóþ ñòðóêòóðó äëÿ õðàíåíèÿ ÀÑÄ - T . Ýòà ñòðóêòó-ðà äîëæíà èìåòü âîçìîæíîñòü õñòðóêòó-ðàíèòü äåðåâî ñ ñèìâîëàìè è ÷èñëàìè (èõ ÷àñòîòîé) â óçëàõ. 2) Íàéòè âñå ñóôôèêñû ñòðîêè: {sk|k = 1, . . . , N} 3) Äëÿ êàæäîãî ñóôôèêñà sk èùåì â T òàêîé ïóòü îò êîðíÿ, ÷òî ñîâïàäåíèå ñ íà÷àëîì ñóôôèêñà ìàêñèìàëüíî ïî äëèíå  smax k . Äëÿ âñåõ ñèìâîëîâ, ïî-ïàâøèõ â ñîâïàäåíèå smax k , óâåëè÷èâàåì ÷àñòîòó ñîîòâåòñòâóþùèõ óçëîâ íà 1. 4) Åñëè ñîâïàäåíèå smax k ïî äëèíå ìåíüøå k, çíà÷èò, ñóôôèêñ íå ïðîéäåí äî êîíöà. Òîãäà â T íåîáõîäèìî ñîçäàòü íîâûå óçëû, ïðèñâîèâ èì ÷àñòîòó 1. Ïðè ïîñòðîåíèè ÀÑÄ äëÿ äâóõ è áîëåå ñòðîê ñóôôèêñû âñåõ ñòðîê ïîñëåäî-âàòåëüíî íàêëàäûâàþòñÿ íà îáùåå äåðåâî. Òàêèì îáðàçîì, ïðåäñòàâèâ äîêóìåíò â âèäå ìíîæåñòâà ñòðîê, ìîæíî ïîñòðîèòü äëÿ íåãî ñîîòâåòñòâóþùåå ÀÑÄ. ÀÑÄ, ïîñòðîåííîå äëÿ äîêóìåíòà, ïîçâîëÿåò óñïåøíî ðåøàòü òàêóþ çàäà÷ó, êàê íàõîæäåíèå áëèçîñòè ñòðîêè è äîêóìåíòà. Ýòà çàäà÷à íàçûâàåòñÿ çàäà÷åé îïðåäåëåíèÿ ñòåïåíè âõîæäåíèÿ ïîäñòðîêè â äåðåâî. Ïðèâåäåì åå ðåøåíèå èç [10]. Ââåäåì ïîíÿòèå óñëîâíîé âåðîÿòíîñòè óçëà u â ÀÑÄ T ñ êîðíåâîé âåðøèíîé R. ×àñòîòó óçëà u îáîçíà÷èì ÷åðåç f(u). Òîãäà óñëîâíàÿ âåðîÿòíîñòü óçëà ðàâíà: p(u) = f (u) f (ancestor(u)), (1) ãäå ancestor(u)  ïðåäîê óçëà u â äåðåâå T . Äëÿ òåõ âåðøèí, äëÿ êîòîðûõ ïðåäêîì ÿâëÿåòñÿ êîðíåâàÿ âåðøèíà R, ôîðìóëà (6) ïðèíèìàåò âèä: p(u) = ∑f (u) v∈T :ancestor(v)=R f (v), (2) ãäå ìíîæåñòâî {v ∈ T : ancestor(v) = R} åñòü íè÷òî èíîå, êàê ìíîæåñòâî âñåõ óçëîâ íà ïåðâîì óðîâíå äåðåâà. Äëÿ êàæäîãî ñóôôèêñà sk ñòðîêè s îöåíêà ñòåïåíè åãî âõîæäåíèÿ â äåðåâî âûðàæàåòñÿ êàê ñóììà óñëîâíûõ âåðîÿòíîñòåé óçëîâ, ïðèíàäëåæàùèõ ìàêñèìàëü-íîìó ñîâïàäåíèþ smax k = sk1. . . skkmax äëèíû kmax. score(sk, T ) = k∑max i=0 p(sk_i) (3)

Òîãäà îöåíêà ñòåïåíè âõîæäåíèÿ ñòðîêè â äåðåâî îïðåäåëÿåòñÿ êàê Score(s, T ) = N ∑ k=1 score(sk, T ) N . (4) Ïðè ñðàâíåíèè ñòåïåíåé âõîæäåíèÿ ñòðîêè â äâà è áîëåå ÀÑÄ ôîðìóëó (3) íåîáõîäèìî ìîäèôèöèðîâàòü, ïîäåëèâ íà äëèíó íàéäåííîãî âõîæäåíèÿ [9]. score′(sk, T ) = k∑max i=0 p(sk i) kmax (5) Àëãîðèòì ïîñòðîåíèÿ ÀÑÄ, ïðèâåäåííûé âûøå, íå ÿâëÿåòñÿ îïòèìàëüíûì.  íàñòîÿùåå âðåìÿ äëÿ ïîñòðîåíèÿ ÀÑÄ ÷àùå ïðèìåíÿþòñÿ àëãîðèòìû, îñíîâàííûå íà êëàññè÷åñêèõ ìåòîäàõ ðàáîòû ñî ñòðîêàìè, íàïðèìåð, àëãîðèòìå Óêêîíåíà ïî-èñêà ïîäñòðîêè â ñòðîêå [15]. Ýòî ïîçâîëÿåò ñîêðàòèòü âðåìåííûå çàòðàòû êàê íà ïîñòðîåíèå ÀÑÄ, òàê è íà âû÷èñëåíèå îöåíêè âõîæäåíèÿ ñòðîêè â ÀÑÄ. Äðóãîå íàïðàâëåíèå  óìåíüøåíèå òðåáóåìûõ ðåñóðñîâ ïàìÿòè. Ýòîãî ìîæíî äîñòèãíóòü ïóòåì ïðèìåíåíèÿ ðàçëè÷íûõ ñòðóêòóð äàííûõ äëÿ õðàíåíèÿ äåðåâüåâ, íàïðèìåð, ñïåöèàëüíûõ ìàññèâîâ.

2.2 Ñïîñîáû îáðàáîòêè êîëëåêöèé äîêóìåíòîâ

2.2.1 Çàäà÷à

âåðîÿòíîñòíîãî òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ

Ñðåäè ìàòåìàòè÷åñêèõ ìîäåëåé, îñíîâàííûõ íà ïðèçíàêîâîì îïèñàíèè òåêñòà, âûäåëèì òàê íàçûâàåìóþ çàäà÷ó âåðîÿòíîñòíîãî òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ [16, 7]. Äàäèì îñíîâíûå îïðåäåëåíèÿ è ðàññìîòðèì ïîñòàíîâêó êëàññè÷åñêîé çà-äà÷è òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ. Âåðîÿòíîñòíàÿ òåìàòè÷åñêàÿ ìîäåëü (ÂÒÌ)  ìîäåëü ìíîæåñòâà äîêóìåí-òîâ, îïèñûâàþùàÿ êàæäóþ òåìó äîêóìåíòîâ äèñêðåòíûì ðàñïðåäåëåíèåì íà ìíîæåñòâå ïðèçíàêîâ, êàæäûé äîêóìåíò - äèñêðåòíûì ðàñïðåäåëåíèåì íà ìíîæåñòâå òåì. Îñòàíîâèìñÿ ïîäðîáíåå íà òåðìèíå ¾òåìà¿.  äàííîì êîíòåêñòå ïîä òåìîé ïî-íèìàåòñÿ ìíîæåñòâî ïðèçíàêîâ, ïðèíàäëåæàùèõ îäíîé è òîé æå ïðåäìåòíîé îáëà-ñòè. Èç îïðåäåëåíèÿ ñëåäóåò, äîêóìåíò ìîæåò ïðèíàäëåæàòü áîëåå ÷åì îäíîé òåìå.

Îïèñàíèå äîêóìåíòà äèñêðåòíûì ðàñïðåäåëåíèåì íà ìíîæåñòâå òåì  òàê íàçû-âàåìàÿ ¾ìÿãêàÿ¿ êëàñòåðèçàöèÿ.  ñâîþ î÷åðåäü, ïðèçíàê ìîæåò ïðèíàäëåæàòü äâóì è áîëåå òåìàì. ×àñòî ýòî ñâÿçàíî ñ ïîëèñåìèåé (ñèíîíèìèåé)  ñèòóàöèåé, êîãäà îäíî è òî æå ñëîâî èìååò ðàçíûå çíà÷åíèÿ. Èòàê, äàíî D - ìíîæåñòâî (êîëëåêöèÿ) äîêóìåíòîâ, è W - ìíîæåñòâî ïðèçíàêîâ êîëëåêöèè. Ïóñòü êàæäûé äîêóìåíò d ∈ D ïðåäñòàâëåí êàê ïîñëåäîâàòåëüíîñòü ïðèçíàêîâ èç W . Òîãäà çàäà÷à âåðîÿòíîñòíîãî òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ çâó-÷èò ñëåäóþùèì îáðàçîì, íåîáõîäèìî íàéòè: 1) Q - ìíîæåñòâî òåì äîêóìåíòîâ; 2) p(w|q) - ðàñïðåäåëåíèå íà W , çàäàþùåå òåìó q ∈ Q; 3) p(q|d) - òåìàòè÷åñêèé ïðîôèëü äëÿ äîêóìåíòà d ∈ D. Îòìåòèì, ÷òî âåðîÿòíîñòíûå òåìàòè÷åñêèå ìîäåëè ìîãóò áûòü àññîöèèðîâàíû ñ ïðîöåññîì, ïîðîæäàþùèì äîêóìåíòû êîëëåêöèè, íàçûâàåìûì ãåíåðàòèâíûì. Âûáðàííûé ãåíåðàòèâíûé ïðîöåññ îïðåäåëÿåò àëãîðèòì ïîëó÷åíèÿ äîêóìåíòà ïðè èçâåñòíûõ ðàñïðåäåëåíèÿõ 2 è 3, è îïðåäåëÿåò îáðàòíîå äåéñòâèå  îöåíèâàíèå ïàðàìåòðîâ ìîäåëè ïî çàäàííîé êîëëåêöèè. Óäîáíî ðàññìàòðèâàòü çàäà÷ó ÂÒÌ â ìàòðè÷íîé ïîñòàíîâêå. Äëÿ ýòîãî êîë-ëåêöèè D ñòàâèòñÿ â ñîîòâåòñòâèå ìàòðèöà F = (fij)|W |×|D|, fij = p(wi|dj), ãäå i = 1, ...,|W |, j = 1, ..., |D|. Òðåáóåòñÿ íàéòè ðàçëîæåíèå F íà äâå ñòîõàñòè÷åñêèå ìàòðèöû: F = ΦT, (6) ãäå Φ = (ϕij)|W |×|T |  ìàòðèöà ïðèçíàêîâ òåì, à T = (tij)|T |×|D|  ìàòðèöà òåì äîêóìåíòîâ. Íà ïðàêòèêå òàêàÿ çàäà÷à ìîæåò áûòü ðåøåíà íåñêîëüêèìè ñïîñîáàìè. Ìîæíî íàéòè ñèíãóëÿðíîå ðàçëîæåíèå ìàòðèöû F ñ ïîñëåäóþùèì âûáîðîì |Q| ãëàâíûõ êîìïîíåíò. Îäíàêî ìàòðèöû, ïîëó÷àåìûå â ðåçóëüòàòå ñèíãóëÿðíîãî ðàçëîæåíèÿ, âîîáùå ãîâîðÿ, íå ÿâëÿþòñÿ ñòîõàñòè÷åñêèìè  è ôîðìàëüíîãî ðåøåíèÿ çàäà÷è ÂÒÌ ýòîò ìåòîä íå äàåò, õîòÿ ÷àñòî ÿâëÿåòñÿ ïîëåçíûì â äðóãèõ ñëó÷àÿõ. Êàê ïðàâèëî, ïðèìåíÿåòñÿ ìåòîä ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ [5] è EM-àëãîðèòì èëè ñýìïëèðîâàíèå Ãèááñà.

2.2.2 Âåðîÿòíîñòíûé ëàòåíòíûé ñåìàíòè÷åñêèé àíàëèç

Ñàìûì ïðîñòûì èíñòðóìåíòîì ÂÒÌ ÿâëÿåòñÿ âåðîÿòíîñòíûé ëàòåíòíûé ñåìàí-òè÷åñêèé àíàëèç (àíãë. Probabilistic Latent Semantic Analysis) [16, 7]. Ýòîò ìåòîä

âïåðâûå áûë îïóáëèêîâàí â 1999 ã [25]. Ìåòîä îñíîâûâàåòñÿ íà ïðèíöèïàõ ìàòå-ìàòè÷åñêîé ñòàòèñòèêè è èìååò íåñêîëüêî ìîäèôèêàöèé. Îïèøåì âåðîÿòíîñòíûé ëàòåíòíûé ñåìàíòè÷åñêèé àíàëèç ãåíåðàòèâíûì ïðî-öåññîì. 1) Âûáèðàåòñÿ äîêóìåíò d ñîãëàñíî ðàñïðåäåëåíèþ P (d). 2) Âûáèðàåòñÿ òåìà θ íà îñíîâå ðàñïðåäåëåíèÿ òåì ïðè óñëîâèè, ÷òî äîêóìåíò ôèêñèðîâàí: P (q = θ|d). 3) Âûáèðàåòñÿ ïðèçíàê v, èñõîäÿ èç ðàñïðåäåëåíèÿ P (w = v|q = θ). Òàêèì îáðàçîì, ñòðîèòñÿ ñëåäóþùåå óðàâíåíèå: P (d, w) = P (d)∑ q∈Q P (w|q)P (q|d), (7) êîòîðîå è îïðåäåëÿåò âåðîÿòíîñòíóþ ìîäåëü. Îòìåòèì, ÷òî (7) ìîæåò áûòü ïåðåïèñàíî â âèäå [7]: P (d, w) =∑ q∈Q P (q)P (w|q)P (d|q). (8) Äëÿ ýòîãî äîñòàòî÷íî ïðèìåíèòü èçâåñòíîå ñîîòíîøåíèå P (A)P (B|A) = P (B)P (A|B). Ïîñëåäíåå óðàâíåíèå íàçûâàþò ñèììåòðè÷íûì ïðåäñòàâëåíèåì ìî-äåëè. Êàê ïðàâèëî, äëÿ îöåíèâàíèÿ ñêðûòûõ ïåðåìåííûõ òåì èñïîëüçóåòñÿ ìåòîä ìàêñèìàëüíîãî ïðàâäîïîäîáèÿ è EM-àëãîðèòì [24]. Äàííûé ïîäõîä èìååò íåñêîëüêî ÿâíûõ íåäîñòàòêîâ [7]. • ×èñëî ïàðàìåòðîâ ìîäåëè ëèíåéíî çàâèñèò îò ÷èñëà äîêóìåíòîâ â êîëëåê-öèè. • Íåâîçìîæíî âû÷èñëèòü âåðîÿòíîñòü äîêóìåíòà, îòñóòñòâóþùåãî â êîëëåê-öèè • Íåò çàêîíîìåðíîñòåé ïðè ãåíåðàöèè äîêóìåíòîâ äëÿ ñî÷åòàíèÿ òåì.

2.2.3 Ñêðûòîå ðàçìåùåíèå Äèðèõëå

Íåêîòîðûå èç íåäîñòàòêîâ PLSA óñòðàíåíû â ìîäåëè ñêðûòîãî ðàçìåùåíèÿ Äè-ðèõëå (àíãë. Latent Dirichlet Allocation, LDA), ïðåäëîæåííîé â 2003 ãîäó [26]. Ãå-íåðàòèâíûé ïðîöåññ ìîäåëè ïðåäñòàâëåí íèæå [7].

1) Âûáðàòü äëÿ äîêóìåíòà d åãî ðàñïðåäåëåíèå ïî òåìàì qd. 2) Äëÿ âñåõ ïðèçíàêîâ â d: (a) âûáðàòü òåìó ϕt ∈ qd; (b) âûáðàòü çíà÷åíèå ïðèçíàêà èç ðàñïðåäåëåíèÿ ïðèçíàêîâ â âûáðàííîé òåìå ϕt.  êëàññè÷åñêîé ïîñòàíîâêå çàäà÷è êîëè÷åñòâî òåì (K) çàäàåòñÿ çàðàíåå. Ïðåä-ïîëàãàåòñÿ, ÷òî ïàðàìåòðû θd è ϕt èìåþò ðàñïðåäåëåíèå Äèðèõëå. Ýòî ïðåäïîëî-æåíèå ëåæèò â îñíîâå ìîäåëè è ñóùåñòâåííî îáëåã÷àåò îöåíêó ïàðàìåòðîâ [7, 26]. Ïðèâåäåì óðàâíåíèå, îïèñûâàþùåå ñîâìåñòíîå ðàñïðåäåëåíèå íàáëþäàåìûõ ïåðåìåííûõ è ïàðàìåòðîâ [7]: P (ϕ1:K, θ1:D, q1:D, w1:D) = K ∏ i=1 P (ϕi) D ∏ d=1 P (θd)( N ∏ n=1 P (qdn|θd)P (wdn|ϕ1:K, qdn)), (9) D - êîëè÷åñòâî äîêóìåíòîâ â êîëëåêöèè. Äëÿ îïðåäåëåíèÿ îïòèìàëüíûõ çíà÷åíèé ïàðàìåòðîâ ìîäåëè íåîáõîäèìî íàéòè òàê íàçûâàåìîå àïîñòåðèîðíîå ðàñïðåäåëåíèå [26]: P (ϕ1:K, θ1:D, q1:D|w1:D) = P (ϕ1:K, θ1:D, q1:D, w1:D) P (w1:D) . (10) Äëÿ îöåíèâàíèÿ (10) ìîæåò áûòü ïðèìåíåíî ñýìïëèðîâàíèå ïî Ãèááñó, î÷åíü óäîáíîå íà ïðàêòèêå [28].

2.2.4 Áîëåå ñëîæíûå ìîäåëè

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

2.3 Ðóáðèêàöèÿ äîêóìåíòîâ â êîëëåêöèè

2.3.1 Êëàñòåðèçàöèÿ äîêóìåíòîâ êàê ðóáðèêàöèÿ

 çàäà÷àõ îáðàáîòêè êîëëåêöèé äîêóìåíòîâ ïîä ðóáðèêàöèåé ïîíèìàåòñÿ ðàñïðå-äåëåíèå äîêóìåíòîâ êîëëåêöèè ïî ðóáðèêàì (êàòåãîðèÿì, òåìàì, êëàññàì) [16, 14]. Ïðîöåññ ðóáðèêàöèè ïîçâîëÿåò ïîëó÷èòü ãðóïïû áëèçêèõ (åñòåñòâåííî, ïî çàäàí-íîé ìåòðèêå, íàïðèìåð, ïî êîëè÷åñòâó ïîõîæèõ ïðèçíàêîâ) äîêóìåíòîâ. Ýòîò ïðî-öåññ, â ÷àñòíîñòè, îáëåã÷àåò çàäà÷ó ïîèñêà äîêóìåíòîâ â êîëëåêöèè.  çàâèñèìî-ñòè îò çàäà÷è, ðóáðèêè ìîãóò êàê áûòü çàðàíåå çàäàííûìè (â ýòîì ñëó÷àå ðåøàåòñÿ çàäà÷à êëàññèôèêàöèè [5]), òàê è íåèçâåñòíûìè (ìîæåò áûòü çàäàíî èõ êîëè÷å-ñòâî).  óñëîâèÿõ âòîðîãî ñëó÷àÿ çàäà÷à ìîæåò áûòü ðåøåíà ìåòîäàìè êëàñòåð-íîãî àíàëèçà [22]. Ïðèâåäåì ïîñòàíîâêó êëàññè÷åñêîé çàäà÷è êëàñòåðíîãî àíàëèçà. Ïóñòü X = {x1, . . . , xn}  ìíîæåñòâî îáúåêòîâ, C = {c1, . . . , ck}  ìíîæåñòâî íîìåðîâ êëàñòå-ðîâ è çàäàíà ôóíêöèÿ ðàññòîÿíèÿ ìåæäó îáúåêòàìè x1 è x2: r = r(x1, x2). Çàäà÷à êëàñòåðèçàöèè ñîñòîèò â òîì, ÷òîáû ðàçáèòü ìíîæåñòâî îáúåêòîâ íà íåïåðåñåêàþ-ùèåñÿ ïîäìíîæåñòâà, íàçûâàåìûå êëàñòåðàìè, òàê, ÷òîáû êàæäûé êëàñòåð ñîñòî-ÿë èç îáúåêòîâ, áëèçêèõ ïî ðàññòîÿíèþ, à îáúåêòû ðàçíûõ êëàñòåðîâ ñóùåñòâåííî îòëè÷àëèñü, è êàæäîìó îáúåêòó ïðèïèñàòü íîìåð åãî êëàñòåðà. Ñóùåñòâóåò ìíî-æåñòâî ðàçëè÷íûõ ìåòîäîâ êëàñòåðèçàöèè: ìåòîä K-ñðåäíèõ, èåðàðõè÷åñêèå è ò.ä. [22]. Ïðè êëàñòåðèçàöèè êîëëåêöèè óäîáíî ðàáîòàòü ñ ïðèçíàêîâûì îïèñàíèåì äî-êóìåíòîâ. Øèðîêî èçâåñòíîé è íàèáîëåå ÷àñòî ïðèìåíÿåìîé ñòàëà ìîäåëü Bag-of-Words [29], â êîòîðîé äîêóìåíò T ïðåäñòàâëÿåòñÿ êàê ïîñëåäîâàòåëüíîñòü ñâî-èõ ïðèçíàêîâ: T = (f1, . . . , fN). Çàòåì ñòðîèòñÿ òàê íàçûâàåìûé âåêòîðèçàòîð  âåêòîð-ôóíêöèÿ, ïðåäñòàâëÿþùàÿ êàæäûé äîêóìåíò âåêòîðîì ïðèçíàêîâ êîë-ëåêöèè. Äëÿ ýòîãî ôèêñèðóåòñÿ ïîðÿäîê ïðèçíàêîâ âñåõ äîêóìåíòîâ êîëëåêöèè: < f1, . . . , fMx >. Âåêòîðèçàòîð V<f1,...,fM>(T ) äëÿ äîêóìåíòà X ñòðîèò âåêòîð V<f1,...,fM>(X) =< c1, . . . , cM >, ãäå i - êîëè÷åñòâî âñòðå÷ ïðèçíàêà fi â äîêóìåíòå X. Ïðîñòîé ìîäèôèêàöèåé îïèñàííîãî çäåñü âåêòîðèçàòîðà ÿâëÿåòñÿ áèíàðíûé âåêòîðèçàòîð, âìåñòî êîëè÷åñòâà âñòðå÷ ïðèçíàêà ïîêàçûâàþùèé åãî íàëè÷èå ëè-áî îòñóòñòâèå. Òàêæå ïðèìåíÿþòñÿ òåõíèêè TF-IDF è íåêîòîðûå äðóãèå [29].  êà÷åñòâå ðàññòîÿíèÿ ìåæäó äîêóìåíòàìè áåðåòñÿ ðàññòîÿíèå ìåæäó âåêòîðà-ìè, ïîëó÷åííûìè èç ýòèõ äîêóìåíòîâ ñ ïîìîùüþ âåêòîðèçàòîðà. Ìîæíî èñïîëüçî-âàòü êàê ïðîñòûå (íàïðèìåð, êîñèíóñ) òàê è áîëåå ñëîæíûå ðàññòîÿíèÿ. Ïðèìåðîì ïîñëåäíèõ ÿâëÿåòñÿ äèâåðãåíöèÿ Êóëüáàêà-Ëåéáëåðà [16].

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

2.3.2 Ðóáðèêàöèÿ â

âåðîÿòíîñòíîì òåìàòè÷åñêîì ìîäåëèðîâàíèè

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

2.4 Ïîèñê äîêóìåíòîâ êîëëåêöèè

2.4.1 Ïîèñê â ìîäåëÿõ PLSI è LDA

Ðàññìîòðèì, êàê ïðîèñõîäèò ïîèñê äîêóìåíòîâ, ðåëåâàíòíûõ ñòðîêîâîìó çàïðîñó, â ìåòîäàõ PLSI è LDA.  ýòèõ ìåòîäàõ çàäà÷à ñâîäèòñÿ ê çàäà÷å âûÿâëåíèÿ äîêóìåíòîâ, ïîõîæèõ íà çàäàííûé, òî åñòü íà ñàì ïîèñêîâûé çàïðîñ. Ïðè ýòîì ïîèñêîâûé çàïðîñ ïðå-îáðàçóåòñÿ ê âåêòîðíîé ôîðìå (î êîòîðîé áûëî ðàññêàçàíî âûøå). Ïîñëå ýòîãî ïðîèçâîäèòñÿ ïðîöåäóðà ðàñ÷åòà ñòåïåíè áëèçîñòè, ñâîäèìàÿ ê ïîèñêó âåêòîðà ïðîèçâåäåíèÿ ìàòðèöû íà âåêòîð [47], ïîñëåäóþùåé åãî ñîðòèðîâêå è èçâëå÷åíèþ äîêóìåíòîâ, ïîëó÷èâøèõ íàèáîëüøèé âåñ. Åñòåñòâåííî, ïðè âûáîðå ðàçëè÷íûõ ïàðàìåòðîâ PLSI è LDA (â ÷àñòíîñòè, êîëè÷åñòâà âûÿâëÿåìûõ òåì è ïàðàìåòðîâ àëãîðèòìîâ) ðåçóëüòàòû ýòîé ïðîöåäóðû ìîãóò îòëè÷àòüñÿ.

2.4.2 Ïîèñêîâàÿ ìàøèíà íà îñíîâå ÀÑÄ

Ïðè èñïîëüçîâàíèè ÀÑÄ ïðîöåäóðà ïîèñêà ñâîäèòñÿ ê ïðîöåäóðå îïðåäåëåíèÿ ñòå-ïåíåé âõîæäåíèÿ ñòðîêè (ïîèñêîâîãî çàïðîñà) â äåðåâüÿ, ïîñòðîåííûå äëÿ êîëëåê-öèè, è âûÿâëåíèþ äîêóìåíòîâ, ïîëó÷èâøèõ íàèáîëüøèå çíà÷åíèå ñòåïåíè âõîæ-äåíèÿ. Ïðèìåíåíèå ýòîé ïðîöåäóðû â ÿâíîì âèäå ïðàêòè÷åñêè íåïðèìåíèìî ê áîëüøèì êîëëåêöèÿì, íàïðèìåð, äëÿ êîëëåêöèè èç 20000 äîêóìåíòîâ îíà çàíèìà-ëà áîëåå 10 ñåêóíä.

Ìû ðàçðàáîòàëè ìåòîä, êîòîðûé ñóùåñòâåííî ñîêðàùàåò ýòî âðåìÿ ïîèñêà. Îí çàêëþ÷àåòñÿ â ïðîâåäåíèè ñëåäóþùèõ äâóõ ïðîöåäóð, íàçâàííûõ íàìè èíäåêñè-ðîâàíèåì ÀÑÄ. 1) Ïîñòðîåíèå ÀÑÄ äëÿ êàæäîãî äîêóìåíòà êîëëåêöèè. 2) Íàéòè âñïîìîãàòåëüíûå ïðèçíàêè {fi|i = 1, . . . , N} äëÿ êîëëåêöèè è ïîñòðî-èòü ñëîâàðü âèäà: {fi : (di1, . . . , dimi)}, ãäå (d i 1, . . . , dimi)  íîìåðà äîêóìåíòîâ, ãäå âñòðå÷àåòñÿ ïðèçíàê fi. Îïèøåì âòîðóþ ïðîöåäóðó ïîäðîáíåå.  êà÷åñòâå âñïîìîãàòåëüíîãî ïðèçíà-êà êîëëåêöèè ìîæåò âûñòóïàòü ëþáîé ïðèçíàê äîêóìåíòà: â íàøåé ðåàëèçàöèè èñïîëüçîâàëèñü òðîéêè è ÷åòâåðêè ïîäðÿä èäóùèõ ñèìâîëîâ. Òàêæå ìîæíî èñ-ïîëüçîâàòü îáðàáîòàííûå ñëîâà èëè ñëîâîñî÷åòàíèÿ, íî òàêîé ïîäõîä âèäèòñÿ èç-ëèøíèì. Áðè î÷åíü áîëüøèõ ðàçìåðàõ êîëëåêöèè ìîæíî áðàòü íå âñå âñïîìîãà-òåëüíûå ïðèçíàêè, à òîëüêî òå, êîòîðûå âñòðå÷àþòñÿ ñ ÷àñòîòîé, áîëüøå çàäàííîé. Òàêèì îáðàçîì, îáðàáîòêà ïîèñêîâîãî çàïðîñà ïåðåä íåïîñðåäñòâåííûì îïðåäåëå-íèåì ñòåïåíåé âõîæäåíèÿ ñòðîêè â äåðåâüÿ äîëæíà âêëþ÷àòü â ñåáÿ: 1) âûÿâëåíèå âñïîìîãàòåëüíûõ ïðèçíàêîâ â ñàìîì çàïðîñå, 2) îïðåäåëåíèå íîìåðîâ äîêóìåíòîâ-êàíäèäàòîâ äëÿ ïîñëåäóþùåé ïðîâåðêè â íèõ ñòåïåíåé âõîæäåíèÿ ñòðîêè â ÀÑÄ ïóòåì îáúåäèíåíèÿ íîìåðîâ äîêó-ìåíòîâ, ñîäåðæàùèõ äàííûé âñïîìîãàòåëüíûé ïðèçíàê, äëÿ êàæäîãî âñïî-ìîãàòåëüíîãî ïðèçíàêà, âûÿâëåííîãî â ñòðîêå çàïðîñà. Ýòî  ïðîñòåéøèé âàðèàíò ïðîöåäóðû èíäåêñèðîâàíèÿ ïåðåä ïðèìåíåíèåì ÀÑÄ. Òàêæå âîçìîæíû óñîâåðøåíñòâîâàíèÿ øàãà (2) ïóòåì çàìåíû îáúåäèíåíèÿ íà îáúåäèíåíèå ñ ïîäñ÷åòîì íîìåðîâ äîêóìåíòîâ è äðóãèå óñîâåðøåíñòâîâàíèÿ. Îòäåëüíûé âîïðîñ äëÿ èçó÷åíèÿ ïðåäñòàâëÿåò ñèòóàöèÿ, êîãäà â ïîèñêîâîì çàïðî-ñå íå âûÿâëåíû âñïîìîãàòåëüíûå ïðèçíàêè.  íàøåì àëãîðèòìå ïðè òàêîì ñëó÷àå â ñïèñîê äîêóìåíòîâ-êàíäèäàòîâ âêëþ÷àåòñÿ âñÿ êîëëåêöèÿ öåëèêîì.

Ãëàâà 3

Ïðîåêòèðîâàíèå è ðåàëèçàöèÿ

ñèñòåìû

3.1 Ôóíêöèè ñèñòåìû

Ðàçðàáàòûâàåìàÿ ñèñòåìà äîëæíà îáëàäàòü ñëåäóþùèì íàáîðîì áàçîâûõ ôóíê-öèé: 1) çàãðóçêà êîëëåêöèè äîêóìåíòîâ; 2) ðåäàêòèðîâàíèå êîëëåêöèè äîêóìåíòîâ (äîáàâëåíèå, èçìåíåíèå è óäàëåíèå äîêóìåíòîâ); 3) ïîëó÷åíèå ñïèñêà òåì (â âèäå õàðàêòåðíûõ ïðèçíàêîâ); 4) îïðåäåëåíèå òåìû äîêóìåíòà; 5) ïîèñê äîêóìåíòîâ ïî çàäàííîé (âûáðàííîé èç ñïèñêà îïðåäåëåííûõ ñèñòå-ìîé) òåìå; 6) ïîèñê äîêóìåíòîâ ïî ïîèñêîâîìó çàïðîñó. Îòìåòèì, ÷òî ôóíêöèè 1 è 2 ÿâëÿþòñÿ ÷èñòî òåõíè÷åñêèìè. Ôóíêöèè 3, 4 è 5 áóäóò ñäåëàíû ñ ïîìîùüþ ðåàëèçàöèè âåðîÿòíîñòíûõ òåìàòè÷åñêèõ ìîäåëåé (PLSI è LDA), ôóíêöèÿ 6 áóäåò ðåàëèçîâàíà êàê ñ ïîìîùüþ îáîèõ âåðîÿòíîñòíûõ òåìàòè÷åñêèõ ìîäåëåé, òàê è ñ ïîìîùüþ ïîèñêîâîé ìàøèíû íà áàçå ÀÑÄ. Âñå ýòî ïîçâîëèò ñäåëàòü ýêñïåðèìåíòàëüíóþ àïðîáàöèþ è ñðàâíåíèå óïîìÿíóòûõ òåõíèê.

3.2 Àðõèòåêòóðà è èíñòðóìåíòû ðåàëèçàöèè

3.2.1 Âûñîêîóðîâíåâàÿ àðõèòåêòóðà

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

3.2.2 Àðõèòåêòóðà óçëà

Îáùèé âèä àðõèòåêòóðû óçëà ñèñòåìû ïîêàçàí íà ðèñ. 3.2.

Îïèøåì ïîäñèñòåìû óçëîâ è âõîäÿùèå â íèõ ìîäóëè. 1) Èíòåðôåéñ óïðàâëåíèÿ  ýòî êîíñîëüíûé ïîëüçîâàòåëüñêèé èíòåðôåéñ, ïîç-âîëÿþùèé ïðîèçâîäèòü ðàáîòó ñ êîëëåêöèåé è åå äîêóìåíòàìè. ×åðåç íåãî ïðîèñõîäèò îáðàùåíèå ê ôóíêöèîíàëó, îïèñàííîì â 3.1. 2) Ïîäñèñòåìà óïðàâëåíèÿ  âûïîëíÿåò ñâÿçóþùóþ ôóíêöèþ ìåæäó Èíòåð-ôåéñîì óïðàâëåíèÿ è ïîäñèñòåìàìè íåïîñðåäñòâåííîé ðåàëèçàöèè ôóíêöèî-íàëà. Ýòà ïîäñèñòåìà èìååò ôàéë ïàðàìåòðîâ êîíôèãóðàöèè, êîòîðûé îïðå-äåëÿåò åå íàñòðîéêè, òàêèå êàê èíôîðìàöèÿ î äðóãèõ óçëàõ (â ÷àñòíîñòè, èõ àäðåñà), ôîðìàòû îáìåíà äàííûìè è ò.ä. (a) Ìîäóëü óïðàâëåíèÿ  åäèíñòâåííûé ìîäóëü äàííîé ïîäñèñòåìû. 3) Ïîäñèñòåìà îáìåíà äàííûìè è îáðàáîòêè ðåçóëüòàòîâ  íåîáõîäèìà äëÿ ïîëó÷åíèÿ è ðàñïðåäåëåíèÿ çàäà÷, îáìåíà äàííûìè ìåæäó óçëàìè, îáðàáîò-êè ðåçóëüòàòîâ âûïîëíåíèÿ çàäà÷. (a) Ìîäóëü ðàñïðåäåëåíèÿ  ìîäóëü, ïîëó÷àþùèé è ðàñïðåäåëÿþùèé çàäà-÷è, îáúåäèíÿþùèé ðåçóëüòàòû èõ âûïîëíåíèÿ. (b) Ñåðâåð  ìîäóëü, ïðåäíàçíà÷åííûé äëÿ îáìåíà äàííûìè ìåæäó óçëàìè. Ïðèíèìàåò çàäà÷è äëÿ ïîñëåäóþùåãî âûïîëíåíèÿ, îòñûëàåò ðåçóëüòàòû èõ âûïîëíåíèÿ.  äàííîì êîíòåêñòå ìû óìûøëåííî íå äåëàåì àêöåíò íà ñîáëþäåíèè êëàññè÷åñêîé òåðìèíîëîãèè êëèåíò-ñåðâåðíûõ àðõèòåêòóð, ïîñêîëüêó â òàêîé òåðìèíîëîãèè îäèí è òîò æå óçåë ìîæåò âûñòóïàòü êàê ¾êëèåíòîì¿, òàê è ¾ñåðâåðîì¿, â çàâèñèìîñòè îò ñèòóàöèè. 4) Ïîäñèñòåìà îáðàáîòêè êîëëåêöèè  êðóïíàÿ ïîäñèñòåìà, îáåñïå÷èâàþùàÿ ðàáîòó ñ êîëëåêöèåé äîêóìåíòîâ. Âêëþ÷àåò â ñåáÿ äâå áîëåå ìåëêèå ïîä-ñèñòåìû. Èìååò äîñòóï ê äâóì áàçàì äàííûõ  ÁÄ ïàðàìåòðîâ, êîòîðàÿ õðàíèò ïàðàìåòðû ìîäåëåé êîëëåêöèè, ñïèñîê ïðèçíàêîâ è äðóãóþ èíôîð-ìàöèþ, íåîáõîäèìóþ äëÿ ðàáîòû ìîäóëåé, è ÁÄ äîêóìåíòîâ, êîòîðàÿ õðàíèò ñàìè äîêóìåíòû. (a) Ïîäñèñòåìà ÌÀÑÄ  ïîäñèñòåìà, íåîáõîäèìàÿ äëÿ ðàáîòû ñ ïîèñêîâîé ìàøèíîé íà áàçå ÀÑÄ. i. Ìîäóëü ìàøèíû íà ÀÑÄ  ìîäóëü, ðåàëèçóþùèé ïîèñêîâóþ ìàøè-íó íà áàçå ÀÑÄ.

(b) Ïîäñèñòåìà ÂÒÌ  ïîäñèñòåìà, íåîáõîäèìàÿ äëÿ ðàáîòû ñ âåðîÿòíîñò-íûìè òåìàòè÷åñêèìè ìîäåëÿìè.

i. Ìîäóëü PLSI  ìîäóëü, ðåàëèçóþùèé ÂÒÌ íà áàçå ìîäåëè PLSI. ii. Ìîäóëü LDA  ìîäóëü, ðåàëèçóþùèé ÂÒÌ íà áàçå ìîäåëè LDA. 5) Ïîäñèñòåìà îáðàáîòêè äîêóìåíòîâ  íåîáõîäèìà äÿë îáðàáîòêè ñàìèõ äî-êóìåíòîâ êîëëåêöèè. Èìååò äîñòóï ê ÁÄ ñëîâàðåé, íåîáõîäèìûì äëÿ ðàáîòû åå ìîäóëåé. (a) Ìîäóëü ÀÑÄ  ìîäóëü, ðåàëèçóþùèé ïîñòðîåíèå àííîòèðîâàííîãî ñóô-ôèêñíîãî äåðåâà äëÿ ÀÑÄ è îïåðàöèè ñ íèì. (b) Ìîäóëü îáðàáîòêè ïðèçíàêîâ  ìîäóëü, ðåàëèçóþùèé ðàáîòó ñ ïðèçíà-êàìè äîêóìåíòîâ (âûÿâëåíèå ïðèçíàêîâ, èõ îáðàáîòêà è ò.ä.)

3.2.3 Èíñòðóìåíòû ðåàëèçàöèè ñèñòåìû

Ðàññìîòðèì èíñòðóìåíòû ðåàëèçàöèè ÷àñòåé ñèñòåìû. Îíè ïðåäñòàâëåíû íèæå: • ÿçûê ïðîãðàììèðîâàíèÿ python; • ïàêåò WebPy äëÿ ðåàëèçàöèè ñåðâåðà, îáìåí äàííûìè ñ ïîìîùüþ ôîðìàòà JSON; • õðàíåíèå äàííûõ  äîêóìåíòîîðèåíòèðîâàííàÿ áàçà äàííûõ MongoDB [38]; • èñïîëüçîâàíèå òåõíîëîãèè MapReduce äëÿ ðàáîòû ñ áàçàìè äàííûõ; • èñïîëüçîâàíèå ïàêåòîâ Numpy/Scipy, áèáëèîòåê äëÿ ðàáîòû ñ òåêñòàìè NLTK, PyMorphy (äëÿ ðàáîòû ñ ïðèçíàêàìè). Âñÿ ñèñòåìà ðàçìåùåíà íà ñåðâåðàõ DigitalOcean.

3.2.4 Èíñòðóìåíòû äëÿ ðåàëèçàöèè î÷åðåäè çàäà÷ è

ïàðàë-ëåëüíîé îáðàáîòêè

Òàê êàê ñèñòåìà äîëæíà ïðîèçâîäèòü áîëüøèå îáúåìû âû÷èñëåíèé, íåîáõîäèìûì ñòàíîâèòñÿ èñïîëüçîâàíèå ïðîãðàììíîé ïëàíèðîâêè î÷åðåäè çàäà÷.  êà÷åñòâå èíñòðóìåíòà äëÿ ýòîãî âçÿò ïàêåò Celery [37]. Ïðîåêò Celery ïðåäñòàâëÿåò ñîáîé ðåàëèçàöèþ ðàñïðåäåëåííîé àñèíõðîííîé î÷åðåäè çàäàíèé, îáëàäàþùóþ øèðî÷àéøèì ôóíêöèîíàëîì [37]. Celery ïîçâîëÿåò

ïðèíèìàòü çàäà÷è è ðàñïðåäåëÿòü èõ ñ ïîìîùüþ òàê íàçûâàåìîãî áðîêåðà, êîòî-ðûé èñïîëüçóåò äëÿ ýòîãî RabbitMQ (ýòîò âàðèàíò ðåêîìåíäóåòñÿ äëÿ èñïîëüçî-âàíèÿ), Redis è áàçû äàííûõ, êàê, íàïðèìåð, MongoDB. Êðàòêî ïåðå÷èñëèì îñíîâíîé ôóíêöèîíàë Celery. • Ïðîñòîå ñèíõðîííîå èëè àñèíõðîííîå âûïîëíåíèå çàäàíèé. Çàäàíèå ñòàâèòñÿ â î÷åðåäü è ïåðåäàåòñÿ íà èñïîëíåíèå áðîêåðîì, ñîãëàñíî óêàçàííûì ïàðà-ìåòðîì âûïîëíåíèÿ. • Âûïîëíåíèå ïåðèîäè÷íûõ (íàïðèìåð, îïðîñ ñîñòîÿíèÿ ñåðâåðîâ èëè ïîëó÷å-íèå ñòàòèñòèêè) è îòëîæåííûõ çàäàíèé. • Ïîâòîðíîå âûïîëíåíèå çàäàíèé. Îãðàíè÷åíèå ÷àñòîòû âûïîëíåíèÿ çàäàíèé. Ìîæíî ñîçäàâàòü ñïåöèàëüíûå ðàñïèñàíèÿ. • Ðàñïðåäåëåíèå çàäàíèé ïî âû÷èñëèòåëüíûì ðåñóðñàì èëè êîíêóðåíòíîå âû-ïîëíåíèå íåñêîëüêèõ çàäàíèé íà îäíîì ðåñóðñå. Âîçìîæíà òàê íàçûâàåìàÿ ìàðøðóòèçàöèÿ (routing) çàäàíèé. • Ñîçäàíèå îò÷åòîâ î ðåçóëüòàòàõ ðàáîòû. Celery îòëè÷íî ïîäîøåë äëÿ èñïîëüçîâàíèÿ â íàøåé ñèñòåìå. Ñ ïîìîùüþ íåãî ðåàëèçîâàíû òàêèå âû÷èñëèòåëüíî ñëîæíûå çàäà÷è, êàê: 1) ïîñòðîåíèå ÀÑÄ äëÿ ãðóïïû äîêóìåíòîâ; 2) èíäåêñàöèÿ ïðèçíàêîâ äîêóìåíòîâ äëÿ âûïîëíåíèÿ ïîèñêîâîãî çàïðîñà; 3) ðåøåíèå çàäà÷è âåðîÿòíîñòíîãî òåìàòè÷åñêîãî ìîäåëèðîâàíèÿ.

3.2.5 Ïðåäâàðèòåëüíàÿ îáðàáîòêà äîêóìåíòîâ

Ìîäóëü ïðåäâàðèòåëüíîé îáðàáîòêè äîêóìåíòîâ âêëþ÷àåò â ñåáÿ âûäåëåíèå ïðè-çíàêîâ, èõ ñòåììèðîâàíèå äëÿ LDA è PLSI è âûäåëåíèå âñïîìîãàòåëüíûõ ïðèçíà-êîâ è íàðåçêó äîêóìåíòîâ íà ñòðîêè äëÿ ìåòîäà íà îñíîâå ÀÑÄ. Ñòåììèðîâàíèå è óäàëåíèå ñòîï-ñëîâ âûïîëíÿëîñü ñ ïîìîùüþ ñðåäñòâ áèá-ëèîòåê NLTK (äëÿ àíãëèéñêîãî ÿçûêà) [46], PyMorphy (äëÿ ðóññêîãî ÿçûêà). Îò-ìåòèì, ÷òî òàêæå áûëà ðåàëèçîâàíà ôóíêöèÿ àâòîîïðåäåëåíèÿ ÿçûêà êîëëåêöèè äîêóìåíòîâ (ïðè ïîìîùè áèáëèîòåêè langid). Ïðè ïîäãîòîâêå ñòðîê äîêóìåíòà (äëÿ ìåòîäà ÀÑÄ) èç äîêóìåíòà óäàëÿëèñü âñå ñòîï-ñëîâà, à òàêæå ñïåöèàëüíûå ñèìâîëû (ïðîáåëû, çíàêè ïóíêòóàöèè è ò.ä.).

Íèêàêîé ìîäèôèêàöèè ñëîâ, ñòåììèðîâàíèÿ èëè ëåììàòèçèðîâàíèÿ, íå ïðîèçâî-äèëîñü. Äàëåå îñòàâøèåñÿ ñëîâà êàæäîãî ïðåäëîæåíèÿ äåëèëèñü íà òðîéêè èç ïîäðÿä èäóùèõ (âîçìîæíî, íåïîëíûå), ñëîâà â òðîéêàõ êîíêàòåíèðîâàëèñü. Òà-êèì îáðàçîì ñòðîèëèñü ñòðîêè äëÿ èõ ïîñëåäóþùåãî ðàçìåùåíèÿ íà ÀÑÄ.

Ãëàâà 4

Ýêñïåðèìåíòàëüíàÿ àïðîáàöèÿ

4.1 Êîëëåêöèè äîêóìåíòîâ

 êà÷åñòâå êîëëåêöèé äîêóìåíòîâ äëÿ ýêñïåðèìåíòàëüíîé àïðîáàöèè áûëè âçÿ-òû òîâàðíûå êàòàëîãè èçâåñòíîãî èíòåðíåò-ìàãàçèíà ¾Îçîí¿, íàõîäÿùèåñÿ â îò-êðûòîì äîñòóïå [19]. Êàæäûé òàêîé êàòàëîã ïðåäñòàâëÿåò ñîáîé ñïèñîê òîâàðîâ îïðåäåëåííîé êàòåãîðèè, íàïðèìåð, ¾áûòîâàÿ òåõíèêà¿ èëè ¾ýëåêòðîíèêà¿. Íåêî-òîðûå êðóïíûå êàòåãîðèè, êàê, íàïðèìåð, ¾êíèãè¿, äîñòóïíû êàê â âèäå ïîëíîãî êàòàëîãà, òàê è â âèäå ïîäêàòàëîãîâ (íàïðèìåð, ¾êíèãè íà âîåííóþ òåìàòèêó¿).  çàâèñèìîñòè îò êàòåãîðèè, êàòàëîã ìîæåò ñîäåðæàòü îò 6 òûñ. äî 1 ìëí. òîâàðîâ. Êàæäûé òîâàð èìååò íàèìåíîâàíèå, áîëåå äåòàëüíîå îïèñàíèå (â ñðåäíåì 100-500 ñëîâ), ñïèñîê ïàðàìåòðîâ è äðóãèå õàðàêòåðèñòèêè. Ïðèìåð òîâàðà èç êàòàëîãà (ðó÷êà-ñòèëóñ èç êàòåãîðèè ¾ýëåêòðîíèêà¿) ïîêàçàí íèæå:

<offer id="24173844" available="true">

<url>http://www.ozon.ru/context/detail/id/...</url> <price>1511</price>

<picture>http://www.ozon.ru/multimedia/...</picture> ...

<delivery>true</delivery>

<name>Wacom Bamboo Stylus Duo 2, Yellow ñòèëóc-ðó÷êà</name> <vendor>Wacom</vendor>

<vendorCode>CS-150Y</vendorCode>

<description>Ñòèëóñ Wacom Bamboo Stylus Duo 2 ïðåäíàçíà÷åí äëÿ ... </description>

<param name="Öâåò">æåëòûé</param>