Matnni qayta ishlash uchun grafik modellar tomon

Plagiatni aniqlash
Katta matn to'plamlaridan plagiatni aniqlash muammosi har doim katta matn to'plamlarining strukturaviy naqshlarini aniqlash qiyinligi sababli matn qazib olish hamjamiyati uchun juda qiyin bo'lib kelgan. Biroq, matnli hujjatni masofaviy grafigiga aylantirish grafik naqshini qazib olish texnikasidan foydalanish imkonini beradi. Biz katta bog'langan grafikalar odatda plagiatga to'g'ri kelishini ta'kidlaymiz, chunki ular hujjatning asosiy matn qismlarida katta tizimli o'xshashliklarga mos keladi. Xususan, ikkita hujjat o'rtasidagi plagiat indeksini aniqlash uchun bir juft grafik o'rtasidagi maksimal umumiy pastki chiziqdan foydalanish mumkin. MayliGAGAvaGBGBikkita hujjatning masofaviy grafik tasviri bo'lsin va ruxsat beringMCG (GA,GB)MCG(GA,GB)ikki hujjat orasidagi maksimal umumiy subgraf bo'lsin. Keyin, biz plagiat indeksini aniqlaymizP(GA,GB)P(GA,GB)quyidagicha:
P(GA,GB) =∣∣MCG {GA,GB}∣∣|GA|−−−−√⋅|GB|−−−−√P(GA,GB)=|MCG{GA,GB}||GA|⋅|GB|
(bir)
Biz maksimal umumiy subgrafni hisoblash umumiy holatda NP-qiyin muammo ekanligini ta'kidlaymiz, ammo bu holda bu oddiy muammo, chunki barcha tugun belgilari alohida va noyob so'zlarga mos keladi. Shu sababli, ushbu yondashuv asosiy ma'lumotlarda mumkin bo'lgan plagiatlarni aniqlash uchun samarali metodologiyani ta'minlaydi.
Eksperimental natijalar
Ushbu bo'limdagi maqsadimiz masofaviy grafiklardan foydalanishning vakillik afzalliklarini ko'rsatishdir. Bunga tayyor vektor-kosmik va strukturaviy ilovalardan foydalanish orqali erishiladi. Maqsad muayyan algoritmlarning o'ziga xos ta'sirini minimallashtirish va yangi taqdimot matnning an'anaviy vektor-fazo tasviriga qaraganda kuchliroq ifodasini ta'minlashini ko'rsatishdir. Biz shuni ta'kidlaymizki, ko'plab (strukturaviy) algoritmlarni yanada optimallashtirish mumkin, ammo biz bu masalani kelajakdagi tadqiqotlarga qoldiramiz. Klasterlash, tasniflash va o'xshashlikni qidirish kabi turli xil ilovalardan foydalanamiz, bu yangi taqdimot yanada sifatliroq natijalar beradi. Bundan tashqari, natijalarimiz ma'lum bir texnika bilan chegaralanib qolmasligini, balki keng ko'lamli ilovalarda samarali natijalarga erishish mumkinligini ko'rsatish uchun biz har xil turdagi tayyor ilovalardan foydalanamiz. Shuningdek, bizning usullarimiz vektor-fazo tasviridan kamtarona samaradorlik darajasini saqlab qolishini ko'rsatamiz. Ushbu maqolada ko'zlangan maqsadlarga erishish uchun bu oqilona kelishuvdir.
Bizning barcha tajribalarimiz 2,4 gigagertsli protsessor, 2 Gb xotira va Redhat Linux bilan ishlaydigan Intel kompyuterida o'tkazildi. Barcha algoritmlar gcc 3.2.3 tomonidan amalga oshirildi va kompilyatsiya qilindi.
Ma'lumotlar to'plamlari
Eksperimental tadqiqotlarimizda an'anaviy matn qazib olish va ma'lumot qidirish ilovalarida ishlatiladigan uchta mashhur ma'lumotlar to'plamini tanlaymiz: (1) 20 ta yangiliklar guruhi, (2) Reuters-21578 va (3) WebKB. Bundan tashqari, Reuters-21578 ma'lumotlar to'plami ikki xil: Reuters-21578 R8 va Reuters-21578 R52. Shunday qilib, bizda jami to'rt xil ma'lumotlar to'plami mavjud. 20 ta yangiliklar guruhi ma'lumotlar to'plami^Izoh3 -da Usenet-ning 20 ta yangiliklar guruhidan 20 000 ta xabar mavjud bo'lib, ularning har birida 1000 ta Usenet maqolalari mavjud. Har bir yangilik guruhi sinf yorlig'i sifatida qaralishi mumkin bo'lgan katalogda saqlanadi va har bir yangilik maqolasi alohida fayl sifatida saqlanadi. Reuters-21578 korpusi^Izoh4 - matn qazib olish bo'yicha tadqiqotlar uchun keng qo'llaniladigan testlar to'plami. Ma'lumotlar dastlab Carnegie Group, Inc. va Reuters, Ltd. tomonidan CONSTRUE matn turkumlash tizimini ishlab chiqish jarayonida to'plangan va etiketlangan [ 16 ]. Korpus uchun sinf taqsimoti juda egri bo'lganligi sababli, ikkita kichik to'plam: Reuters-21578 R52 va Reuters-21578 R8, odatda matnni qazib olish vazifalari uchun ko'rib chiqiladi [ 11 ]. Eksperimental tadqiqotlarimizda biz ushbu ikkita ma'lumotlar to'plamidan bir qator turli xil ma'lumotlarni qazib olish algoritmlarini baholash uchun foydalanamiz. WebKB ma'lumotlar to'plami^Izoh5 1997 yil yanvar oyida CMU matn o'rganish guruhining Butunjahon bilimlar bazasi loyihasi tomonidan turli universitetlarning informatika bo'limlaridan to'plangan WWW sahifalarini o'z ichiga oladi. 8282 sahifa qoʻlda quyidagi yetti toifaga ajratildi: talaba, professor-oʻqituvchilar, xodimlar, boʻlim, kurs, loyiha va boshqalar . Yuqorida aytib o'tilgan ma'lumotlar to'plamidagi har bir hujjat alfanumerik bo'lmagan belgilar, maxsus sarlavhalar yoki teglar va to'xtash so'zlarini yo'q qilish orqali oldindan qayta ishlanadi. Har bir hujjatning qolgan so'zlari Porterning asosiy algoritmidan kelib chiqadi.^Izoh6 Masofa grafiklari ushbu keyingi qayta ishlangan tasvirga nisbatan aniqlanadi.
Keyinchalik, biz turli xil ma'lumotlar qazib olish ilovalari, jumladan, matn tasnifi, klasterlash va o'xshashlikni qidirish bo'yicha eksperimental baholashimizni batafsil bayon qilamiz. Ko'p hollarda biz bir nechta turli usullarni sinab ko'ramiz. Maqsad, masofaviy grafikning turli xil muammolar va usullarga nisbatan konchilik maqsadlarida bir qator vakillik afzalliklariga ega ekanligini ko'rsatishdir.
Tasniflash ilovalari
Ushbu bo'limda biz birinchi navbatda turli tasniflash algoritmlarida masofaviy grafik tasvirining samaradorligini sinab ko'ramiz. Biz eksperimental tadqiqotlarimiz uchun bepul mavjud bo'lgan statistik matnlarni tasniflash vositalari to'plami bo'lgan Rainbow [ 19 ] dan foydalanamiz. Avvalo, Rainbow matnli hujjatlarni o'qiydi va indekslaydi va statistik modelni quradi. Keyinchalik, statistik model bo'yicha turli xil matn tasniflash algoritmlari amalga oshiriladi. Matnlarni tasniflash uchun biz Rainbow -dan uchta turli xil algoritmlardan foydalandik . Bu algoritmlar Naive Bayes klassifikatori [ 18 ], TFIDF klassifikatori [ 15 ] va Ehtimoliy indekslash tasniflagichi [ 12 ].], mos ravishda. Qiziqarli har bir tasniflash usuli uchun biz matn tasnifi uchun asosiy vakillik modellari sifatida unigram, bigram va trigram modellarini o'z ichiga olgan vektor-fazo modellaridan va mos ravishda 1 dan 4 gacha bo'lgan turli tartibdagi masofaviy grafik modellaridan foydalanamiz. Bigram modeli va trigramma modelining xatti-harakatlarini taqlid qilish uchun biz korpusdan eng tez-tez uchraydigan 100 ta dublet va tripletlarni chiqaramiz va har bir hujjatni mos ravishda shunday dublonlar va tripletlar bilan to'ldiramiz. Shuning uchun vektor-fazo modellari qo'shimcha so'zlarsiz unigramma , dublet ko'paytirishli bigramma va trigramma sifatida tasniflanadi.uchliklarni ko'paytirish bilan. Turli vakillik strategiyalaridan olingan tasniflash aniqligini solishtirish uchun har bir algoritm uchun 5 marta o'zaro tekshirish o'tkazamiz. Xabar qilingan barcha tasniflash aniqliklari statistik ahamiyatga ega va 95% ahamiyatlilik darajasi.
3 -rasmda biz tasniflashning aniqligi natijalarini tasvirlab berdikyigirmayigirmauch xil tasniflagichlar uchun yangiliklar guruhlari ma'lumotlar to'plami. Unigram, bigram va trigram modellari uchun vektor-fazo tasvirlaridan tashqari, biz 1 dan 4 gacha bo'lgan turli masofa tartiblari bilan masofaviy grafik tasvirlari uchun tasniflash natijalarini ham tasvirlab berdik. Ko'rinib turibdiki, tizimli ma'lumotlarning qo'shilishi. masofaviy grafik modellari aksariyat hollarda asosiy natija sifatini yaxshilaydi. Xususan, eng yaxshi tasniflash natijalari mos ravishda Naive Bayes klassifikatorida 2-darajali, TFIDF klassifikatorida 1-darajali va 4-tartibli probabilistik indekslash tasniflagichida masofaviy grafiklar uchun olinadi. Shu bilan birga, barcha holatlarda masofaviy grafik tasvirlari barcha vektor-fazo modellariga, shu jumladan unigram, bigram, va trigramma modellari. Ba'zi eksperimental stsenariylarda 1 va 2 tartibli masofaviy grafiklar uchun optimal tasniflash aniqligiga erishilgan bo'lsa ham, vektor-fazo tasvirlari barcha holatlarda yuqori tartibli masofa grafiklaridan ham yaxshiroq ishlamaganligi diqqatga sazovordir. Reuters-21578 (R8 va R52) ma'lumotlar to'plamlari uchun tasniflash natijalarini ham sinab ko'rdik. Tasniflashning aniqligi natijalari 2-rasmda ko'rsatilgan. mos ravishda 4 va 5 . Ko'rinib turibdiki, masofaviy grafik tasvirlar vektor-fazo tasvirlari bilan solishtirganda turli xil tasniflagichlar bo'yicha yuqoriroq tasniflash aniqligini ta'minlay oladi. Buning sababi shundaki, masofaviy grafik tasvirlar tasniflashning aniqligini oshirishga yordam berish uchun foydalaniladigan hujjatlar to'g'risidagi tizimli ma'lumotlarni olishi mumkin. Natijada, masofaviy grafik tasvirlardan foydalangan holda olingan tasnif natijalari vektor-fazo tasvirlari yordamida olingan natijalardan ustundir.