خلاصه پایان نامه تشخیص پلاگاریسم به کمک گراف در متون فارسی
پایاننامه کارشناسی ارشد رشته مهندسی کامپیوتر
گرایش: نرم افزار
چکیده
تمرکز این پایاننامه روی جستجوی شباهت های مبتنی بر گراف، در متون مربوط به زبان های طبیعی است. نیاز به یک روش قوی برای ارائه متون، مسئله مهمی در زمینه تشخیص پلاگاریسم است، ما در این پروژه با توجه به این نیاز، روشی قدرتمند را برای ارائه زبان طبیعی معرفی نموده و از آن در تشخیص پلاگاریسم بهره بردهایم. برای این منظور مفهوم "فاصله اصلاح گراف" را بیان نموده و از آن برای محاسبه فاصلهی بین دو گراف استفاده کردهایم. جملات توسط گرافهای وابستگی ارائه شدهاند که در آنها کلمات توسط وابستگیهایشان به هم متصل شدهاند. گراف وابستگی ساختار گرامری جملات را استخراج میکند. روش شباهت مبتنی بر گراف در مسئله تشخیص پلاگاریسم به کار برده شده است. مزیت اصلی ارائه مبتنی بر گراف، مربوط به توانایی این روش در تشخیص شباهتهای بین کلمات است. ارزیابیها نشان دادند که نتایج حاصل از گراف وابستگی نسبت به روشهای مقایسه مستقیم گرافها نتایج بهتری دارند. استفاده از فاصله اصلاح گراف برای مقایسه دو گراف منجر به بهبود نتایج گراف وابستگی میشود و کارایی آن را بالا میبرد.
کلیدواژه: فاصله اصلاح گراف، پردازش زبان طبیعی، گراف های وابستگی، تشخیص پلاگاریسم
فصل اول
مقدمه
برخی افراد ممکن است خواسته یا ناخواسته از کارهای محققان استفاده کنند در حالیکه حتی نامی از نویسندهی اصلی اثر ذکر نکرده باشند، این عمل پلاگاریسم نامیده میشود. پلاگاریسم عمل عمدی یا غیرعمدی کپی کردن یا استفاده از ایدهها و کارهای دیگران است بدون آنکه اطلاعاتی درباره منبع اصلی ذکر شده باشد. بر اساس بررسیهای صورت گرفته بر روی موضوع پلاگاریسم و تعداد مقالات بیشمار مندرج در وب و انعکاس نگرانی از وقوع آن مشخص است که اکثر مراکز آموزشی و پژوهشی در صفحات الکترونیکی خود در اقصی نقاط جهان چه در کشورهای در حال رشد آسیا و افریقا، تحت تاثیر ناشران با سابقه مجلات پژوهشی و نیز حفظ حیثیت علمی مراکز خود به معرفی همه جانبه این پدیده ضد اخلاقی و ضد اجتماعی به عنوان یک جرم مبادرت کردهاند. پلاگاریسم یک مشکلی در انجمن علمی است و به سرعت در حال رشد است، بدلیل آنکه داده و اطلاعات از بین اسناد الکترونیکی و اینترنت سریع و آسان از طریق کپی و درج از آن منابع بدست میآید. این مشکل زمانی رخ میدهد که محتوای اسناد غیرقانونی و بدون اجازه و بدون نقل قول پیدا شود که این مشکل به عنوان پلاگاریسم شناخته شده است و پلاگاریسم می تواند شامل طیف وسیعی از دستبردهای آگاهانه تا کپی کردن اتفاقی مطالب دیگران باشد. هدف اصلی این پایاننامه بیان روش مبتنی بر گراف برای ارائه متن و استفاده از آن در تشخیص پلاگاریسم است. بخشهایی که در ادامه این فصل میآیند دلایل استفاده از این روش را بیان نموده و به شرح مسئلهی تشخیص پلاگاریسم میپردازند. به علاوه یک راه حل برای این مسئله ارائه میدهند. در نهایت ساختار پایان نامه معرفی و مطالبی که در فصلهای بعدی به آنها پرداخته خواهد شد، مرور خواهند شد.
مسئلهی پیدا کردن شباهت بین دو متن، یک مسئله معمول در زمینهی پردازش زبانهای طبیعی است. به منظور ارزیابی شباهتها بین دو متن، هر متن نیاز به روشی برای ارائه دارد. یک روش متن ساده است، که در آن یک لیست از کلمات، یک جمله را شکل میدهند. متنِ ساده معمولا به دلیل سادگی مورد استفاده قرار میگیرد، اما فاقد اطلاعات واضح راجع به ساختار گرامری است.
بعضی از جنبههای زبان با استفاده از روشهای ارائهی ساختاری از قبیل گرافهای وابستگی که شامل کلمات متصل به هم است، بهتر ارائه میشوند.
گرافهای وابستگی ساختار گرامری یک جمله را استخراج نموده، و به گسترهی همان جمله محدود میشوند. یکی از مزایای اصلی ارائهی مبتنی بر گراف این است که گرافهای وابستگی در بیشتر موارد حساس به ترتیب کلمات نیستند. این مزیت باعث میشود که شباهت بین جملاتی که ترتیب کلمات در آنها به هم ریخته شده است، پیدا شود.
یک ارائهی قویتر پایههای بهتری را برای مشخص کردن شباهتها در وضعیتهای پیچیده فراهم میکند. دو جملهی ارائه شده در گراف وابستگی شکلهای 1-1 و 1-2 را در نظر بگیرید. انسان باید بتواند مشخص کند که این جملات دارای معانی یکسانی هستند. با این حال، تشخیص اتوماتیک شباهت این دو جمله به دلیل جایگزینی کلمات دچار مشکل خواهد شد. اگر از ارائه متن ساده استفاده شود، تنها کلمات مشترک "به"، "خارج"، "از"، "شوت" و "توپ" خواهند بود. کلمهی "شوت" و "توپ" تنها کلماتی هستند که منظور جمله را میرسانند. با دقت در گرافهای وابستگی، واضح است که شباهت ساختاری بین جملات وجود دارد.
با افزایش میزان دسترسی به متون موجود در وب، پلاگاریسم ساده و سادهتر شده است. میزان زیادی از متون پلاگاریسم در زمینهی درسی و تحصیلی سال به سال افزایش پیدا میکنند. در نتیجه، نیاز شدیدی به تشخیص خودکار پلاگاریسم احساس میشود.
1-1 توضیح مسئله
مهمترین بخش این پایاننامه پیادهسازی یک الگوریتم برای محاسبه فاصلهی اصلاح گراف است، که شباهت بین دو گراف را محاسبه میکند. الگوریتم مبتنی بر محاسبهی تعداد عملیات ویرایشی مورد نیاز برای تبدیل یک گراف به گراف دیگر است[1]. هر عمل ویرایش یک هزینهی ویرایش دارد، که مشخص میکند یک عمل چقدر هزینه میبرد.
تشخیص پلاگاریسم اتوماتیک یک زمینهی تحقیقاتی است که در اصل روی شباهت متنی بنا شده است. مسئلهی بکارگیری شباهت متن مبتنی بر گراف برای تشخیص پلاگاریسم در سوال تحقیقی 1 بیان شده است.
سوال تحقیقی 1 : آیا شباهت مبتنی بر گراف، در یک فاصله اصلاح گراف مشخص، در تشخیص پلاگاریسم قابل بکارگیری و از لحاظ محاسباتی امکانپذیر هست؟
سیستمهای تشخیص پلاگاریسم آزمایشی اغلب مبتنی بر ارائههای سادهتر متن، از قبیل تطبیق nگرام و مدل فضای بردار هستند [2 و 3]. در نتیجه، روش میتواند نسبتا منحصر به فرد باشد. به دلیل منحصر بودن روش، بعضی از جزئیات پیادهسازی تعریف شده نیستند. سوال تحقیقاتی 2 مسئلهای را بیان میکند که جزئیات الگوریتم را مشخص مینماید.
سوال تحقیقی 2 : بهترین روش برای محاسبهی فاصله ویرایش گراف بین جملات، به ویژه از لحاظ هزینهی ویرایش و ارائه گراف در زمینه تشخیص پلاگاریسم چیست ؟
به منظور ارزیابی کارایی الگوریتم محاسبه فاصلهی ویرایش گراف، کارایی آن در مقایسه با سیستمهای آزمایشی موجود مقایسه میشود. سوال تحقیقی 3 مسئلهی مقایسهی الگوریتم با روشهای موجود را مطرح میکند.
سوال تحقیقی 3 : شباهت مبتنی بر گراف با سایر روشها در تشخیص پلاگاریسم، از قبیل بازیابی مبتنی بر اندیس و تطبیق nگرام، چگونه مقایسه میشود؟
1-2 راه حلها
اهداف زیر پاسخ به سوالاتی که در بخش قبل مطرح شدند را تضمین میکنند.
هدف تحقیقی 1 : سیستم تشخیص پلاگاریسم مبتنی بر فاصله ویرایش گراف مورد آزمایش، پیادهسازی خواهد شد. سیستم باید بتواند متون زیادی را ارزیابی کند و پلاگاریسم را در سطح جمله تشخیص دهد.
هدف تحقیقی 2 : چند تابع برای محاسبهی هزینهی ویرایش پیادهسازی ارائه خواهند شد. روشهای مختلف با یکدیگر مقایسه شده و سیستمهای حاصل ارزیابی میشوند.
هدف تحقیقی 3 : خروجی سیستم آزمایشی با سیستمهای تشخیص پلاگاریسم موجود مقایسه میشود. این مقایسه ارزیابی تجربی سیستم محسوب میشود.
1-3 مشکلات موجود در پیادهسازی الگوریتم
یکی از مهمترین مشکلاتی که در پیادهسازی نرمافزار تشخیص پلاگاریسم معنایی در زبان فارسی وجود دارد، به خود زبان فارسی برمیگردد. همانطور که میدانیم زبان فارسی زبانی بسیار پیچیده است و دارای دستور زبانی با استثنائات فراوان بوده و به دلیل اشتراکاتی که با زبان عربی دارد، در کاراکترهایی که در عربی و فارسی مشترکند دچار مشکل شده و باعث میگردد برخی موارد نادرست تشخیص داده شود.
از طرفی برخلاف زبان انگلیسی که دارای علائم جمع محدودی است، زبان فارسی دارای علامتهای جمع زیادی میباشد و از طرفی برخی از کلمات وقتی به حالت جمع در میآیند شکل ظاهری آنها تغییر میکند.
همچنین در مورد افعال در زبان فارسی که تقریباً شبیه به زبان عربی است دارای اشکال مختلفی است و بسته به چندم شخص بودن تغییر میکند. این استثنائات و هزاران مسئله شبیه این موارد که به دلیل دستور زبان غنی و پیچیده زبان فارسی است سبب میشود که کار تشخیص پلاگاریسم را با مشکلات زیادی مواجه نماید و نیاز باشد تا جوانب زیادی را در پیادهسازی الگوریتم مد نظر قرار دهیم.
یکی دیگر از مشکلاتی که در زمینه تشخیص پلاگاریسم معنایی ممکن است پیش بیاید این است که تنها نمیتوان به دیکشنری مترادفهای کلمات بسنده کرد، چرا که ممکن است کاربرانی که اقدام به عمل غیرانسانی پلاگاریسم و کپیبرداری از کارهای دیگران میکنند، در برخی موارد به جای جایگزین کردن کلمات مترادف بجای اصل آنها، با اندکی تغییر در ساختار و شکل ظاهری جملات، از متضاد کلمات بجای اصل آنها استفاده نمایند. حتی گاهی بدون جایگزین کردن کلمات می توان با اندکی تغییر در ساختار جملهها، جملاتی مشابه ایجاد کرد. بنابراین ذکر این نکته مهم لازم است که پلاگاریسم معنایی را نمیتوان چیزی جدا از پلاگاریسم ساختار و یا ایده و یا حتی انواع مختلف پلاگاریسم دانست.
1-4 ساختار پایاننامه
ساختار پایاننامه به صورت زیر است:
فصل2- تحقیقات انجام شده در زمینهی تشخیص پلاگاریسم و محاسبه فاصله ویرایش گراف را معرفی و شرح میدهد،
فصل3- تئوری مورد نیاز برای پیادهسازی روش ارائه شده در فصل 4 را ارائه میکند،
فصل4- سیستم تشخیص پلاگاریسم ارائه شده در این پایان نامه را توضیح میدهد،
فصل5- نتایج حاصل از سیستم فعلی را با سیستمهای موجود مقایسه میکند و مورد تحلیل و ارزیابی قرار میدهد،
فصل6- شامل نتیجهگیری و کارهایی که در آینده میتوان انجام داد میباشد.
فصل دوم
پیشینهی تحقیق
این فصل کارهای انجام شده در زمینهی تشخیص پلاگاریسم را معرفی میکند و سپس به طور خاص کارهای انجام شده در زمینهی روش مبتنی برگراف را توضیح داده و به معرفی روشهای محاسبه میزان شباهت بین گرافها میپردازد.
2-1 تشخیص پلاگاریسم
این روزها فضای تقلبات علمی و مدارک بیاعتبار بیش از بیش مطرح و بزرگ و در حال رشد است. پلاگاریسم یک مشکلی در انجمن علمی است و به سرعت در حال رشد بوده و بدلیل آنکه داده و اطلاعات از بین اسناد الکترونیکی و اینترنت سریع و آسان از طریق کپی و درج از آن منابع بدست می آید. این مشکل زمانی رخ میدهد که محتوای اسناد غیر قانونی و بدون اجازه و بدون نقل قول پیدا شود که این مشکل به عنوان پلاگاریسم شناخته میشود . پلاگاریسم عمل عمدی یا غیرعمدی کپی کردن یا استفاده از ایده ها و کارهای دیگران است بدون آنکه اطلاعاتی درباره منبع اصلی ذکر شده باشد این یک مشکل جهانی است که در مراحل مختلف زندگیمان رخ میدهد. اخیرا در کنفرانسی درباره آفت های اجتماعی که گریبان گیر جوانان است, اعلام شد حدود 60 درصد دانشجویان دانشگاهها تقلب میکنند. همه این امور پلاگاریسمی، یک اثر منفی روی فرایند یادگیری دارد. پلاگاریسم میتواند یک جرم الکترونیکی باشد. موضوع پلاگاریسم یک موضوع بحرانی است که به راهحلهایی نیاز دارد که به وسیلهی علوم و دانش کامپیوتر مطرح میشود. پلاگاریسم یعنی برداشتن تمامی یا قسمتی از متن یک نویسنده و نام بردن به عنوان آثار خود بدون نقل قول و بدون ذکر نام نویسنده.
همه موارد زیر بعنوان یک پلاگاریسم مطرح شده هستند:
کپی کردن ایدهها و کلمات از دیگران بدون نسبت دادن به آنها
ضعف و کوتاهی در قرار دادن نقل قول (" ") در عبارت نقل قولدار
اطلاعات نادرست دادن درباره منبع نقل قول
خیانت (عدم امانتداری) ادبی در مطبوعات ( ادبیات)
یک راه دیگر پلاگاریسم شامل پلاگاریسم ترجمه بدون ذکر منابع
محتوای لغات شبیه متن را به کلمات متفاوتی تغییر دادن
فهرست پایان نامه تشخیص پلاگاریسم به کمک گراف در متون فارسی
فهرست:
مقدمه. 2
1-1 توضیح مسئله. 5
1-2 راه حلها 6
1-3 مشکلات موجود در پیادهسازی الگوریتم.. 6
1-4 ساختار پایاننامه. 7
پیشینهی تحقیق.. 9
2-1 تشخیص پلاگاریسم.. 9
2-2 ابعاد تشخیص پلاگاریسم.. 12
2-2-1 روش مبتنی بر گرامر. 12
2-2-2 روشهای مبتنی بر معنا 13
2-2-3 روشهای ترکیبی.. 14
2-2-4 روش تشخیص پلاگاریسم خارجی.. 14
2-3 روشهای محاسبه میزان شباهت گرافها 15
2-3-1 روش بزرگترین زیرگراف مشترک - کوچکترین سوپرگراف مشترک... 15
2-3-2 روش مبتنی بر جستجوی فضای حالت... 17
2-3-3 روشهای احتمالی.. 18
3-1 تشخیص پلاگاریسم.. 23
3-1-1 تطبیق n گرام. 23
3-1-2 وزندهی عبارت... 23
3-1-3 تعمیم عبارت... 24
3-2 گرافهای وابستگی.. 25
3-2-1 وابستگیها 26
3-3 فاصله ویرایش گراف... 26
3-3-1 عملیات ویرایش.... 26
3-3-2 مسئلهی انتساب... 27
3-3-3 ماتریس هزینه. 28
3-3-4 الگوریتمهای انتساب... 29
4-1 معماری.. 32
4-2 پیشپردازش متن.. 32
4-2-1 پیدا کردن جملات... 33
4-2-2 ریشهیابی کلمات... 34
4-2-3 تشکیل گراف وابستگی.. 40
4-3 استخراج کاندیدا 44
4-3-1 شاخصگذاری جمله. 45
4-3-2 استخراج جملات کاندیدا 45
4-4 تحلیل جزئیات... 45
4-4-1 الگوریتم فاصله ویرایش دو گراف... 48
4-4-2 تشخیص پلاگاریسم مبتنی بر GEDارائه شده در این پروژه 49
5-1 تشخیص پلاگاریسم جابجایی کلمات و تغییر ساختار جملات... 55
5-1-1 تغییرات ساختاری 10 درصدی.. 56
5-1-2 تغییرات ساختاری 50 درصدی.. 57
5-2-2 تغییرات ساختاری 100 درصدی.. 59
5-2 تشخیص پلاگاریسم معنایی.. 60
5-2-1 تغییرات معنایی 10 درصدی.. 60
نتیجه گیری و پیشنهادات... 64
مراجع.. 67
منبع:
Fankhauser, S., K. Riesen, and H. Bunke. Speeding up graph edit distance computation through fast bipartite matching. Graph-Based Representations in Pattern Recognition, (2011)
Suchomel, S., J. Kasprzak, and M. Brandejs (2012). Three way search engine queries with multi-feature document comparison for plagiarism detection. See Forneretal. (2012).
Grman, J. and R. Ravas Improved implementation for _nding text similarities in large sets of data - notebook for PAN at clef 2011. See Petras et al. (2011).
Asim M. El Tahir Ali, Hussam M. Dahwa Abdulla, and V´aclav Sn´aˇsel Overview and Comparison of Plagiarism Detection Tools , Dateso 2011, pp. 161{172, ISBN 978-80-248-2391-1.
A. S. Bin-Habtoor and M. A. Zaher “A Survey on Plagiarism Detection Systems ”, International Journal of Computer Theory and Engineering Vol. 4, No. 2, April 2012
Sindhu.L, Bindu Baby Thomas, Sumam Mary Idicula A Study of Plagiarism Detection Tools and Technologies, IJART, Vol. 1 Issue 1, 2011,64-70.
Schleimer, S., Wilkerson, D. and Aiken, A. (2003) Winnowing: Local Algorithms for Document Fingerprinting. SIGMOD 2003, San Diego, 9-12 June 2003, 76-85.
J.A. Malcolm and P.C.R. Lane, Tackling the PAN’09 External Plagiarism Detection Corpus with a Desktop Plagiarism Detector, 3rd PANWORKS-HOP. UNCOVERING PLAGIARISM, AUTHORSHIP AND SOCIAL SOFTWARE MISUSE, 2009, p. 29.
C. Basile, G. Cristadoro, D. Benedetto, E. Caglioti, and M. Degli Es-posti, A plagiarism detection procedure in three steps: selection, matches and” squares”, 3rd pan workshop. Uncovering plagiarism, authorship and social software misuse, 2009, p. 19.
Adam Shenker Horste Bunke, Mark Last and Abraham Kandle Graph Theoretic Techniqes For Web Content Mining, Published by World Scientific Publishing, USA 2005
Ahmed Hamza Osman, Naomie Salim and Mohammed Salem Binwahlan, Plagiarism Detection Using Graph-Based Representation, Journal Of Computing, Volume 2, Issue 4, Issn 2151-9617 , April 2010.
H. Bunke, On a relation between graph edit distance and maximum common subgraph, Pattern Recognition Letters (1997)
H. Bunke and K. Shearer, A graph distance metric based on the maximal common subgraph, Pattern Recognition Letters, Vol.!19, 1998
J.!T. L. Wang, K. Zhang, and G.-W. Chirn, Algorithms for Approximate Graph Matching, Information Sciences, Vol. 82, 1995
R. C. Wilson and E. R. Hancock, Structural Matching by Discrete Relaxation, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 6, June 1997
R. Myers, R. C. Wilson, and E. R. Hancock, Bayesian Graph Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vo .!22, No. 6, June 2000
Papineni, K., S. Roukos, T. Ward, and W. Zhu (2002). Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting on association for computational linguistics, pp. Association for Computational Linguistics.
Stamatatos, E.. Plagiarism detection using stopword n-grams. Journal of the American Society for Information Science and Technology(2011)
Jones, K.. A statistical interpretation of term speci_city and its application in retrieval. Journal of documentation (1972)
Marcus, M., M. Marcinkiewicz, and B. Santorini Building a large annotated corpus of english: The penn treebank. Computational linguistics(1993).
Riesen, K. and H. Bunke Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing (2009).
Porter, M. F. An algorithm for suffix stripping. Program, pp. 130- 137. (1980).
Megerdoomian, K .(2004). Finite-state morphological analysis of Persian. In Proceedings of the Workshop on Computational Approaches to Arabic Script-based Languages, University of Geneva, Iran.
Sheykhzadegan, J. and M. Bijankhan (2006). The Speech databases of Persian language. In Proceedings of the 2nd Workshop on Persian Language and Computing, the University of Tehran, Tehran, Iran, pp. 247-261.
Taghva, Beckley and Sadeh. A stemming algo-rithm for the Farsi language. IEEE ITCC, pp. 158 - 162. 2005.
Anvari, H. & Ahmadi Givi, H. (2006). Persian Language Grammar (2nd Ed.). Tehran: Fatemi Publication.
A. A. Sharifloo, and M. Shamsfard, “A Bottom up Approach to Persian Stemming”, Proceedings of the Third International Joint Conference on Natural Language Processing, 2008.
نرمالساز متون فارسی، سید مجید غفوری، سعید راحتی، محمدرضا پهلوان نژاد، علی عظیمی زاده، دانشگاه فردوسی مشهد، دانشگاه آزاد اسلامی مشهد