نظرت چیه ؟

مرکز هم فکری و انتقال تجربه

همین الان ثبت نام کن و از ما باش

ثبت نام

توجه : وارد کردن هر دو گزینه ایمیل و موبایل اجباری نیست فقط یک مورد کافی است.

پرسشنامه

کد امنیتی

تغییر

یاد آوری کردن کلمه عبور

چنانچه رمز عبور خود را فراموش کرده اید ایمیل خود را وارد کنید تا اطلاعات حساب کاربری برای شما ارسال شود.

یاد آوری کلمه عبور به وسیله موبایل

یاد آوری کلمه عبور به وسیله ایمیل

خوشه بندی

طراحی و پیاده سازی Document clustering  توزيع شده بر پايه MapReduce

چکيده:

در اين مقاله ما توضيح ميدهيم که Document Clustering براي مجموعه هاي بزرگ بوسيله Map-Reduce چگونه ميتواند به طور موثر اجرا شود. Hadoop یک چارچوب مناسب و انعطاف پذیر برای محاسبات توزیع شده  خوشه ای از ماشین آلات کالا پياده سازي و فراهم می کند. در اين مقاله طراحی و پیاده سازی tfidf و الگوریتم K-Means در Map Reduce ارائه شده است. از همه مهمتر، کارایی و اثربخشی از الگوریتم بهبود یافته است و در نهایت، ما در مورد برخي نتايج بحث های مرتبطي خواهيم داشت.

واژه هاي مرتبط :  Map-Reduce, tfidf, K-Means clustering

مقدمه :

با توسعه سریع اینترنت، حجم عظیمی از اسناد باید در یک زمان کوتاه پردازش شود. تحقیق در وب کاوی در مورد  روش مقیاس پذیر و قابل انطباق با اسناد جمعی تمرکز دارد [1]. ذخیره سازی و محاسبات جرم داده های اسناد در یک سیستم توزیع شده یک روش جایگزین است [2]. در محاسبات توزیع شده، مشکل تقسيم وظایف است، به طوري که هر کدام توسط یک کامپیوتر حل شود. با این حال، بسیاری از مشکلات مانند برنامه ریزی کار، تحمل خطا و ارتباط بین دستگاه برای برنامه نویسان با تجربه کم، با سیستم موازی و توزیع شده بسیار مشکل است. در این مقاله ما تجربه ها و یافته های Document Clustering را بر اساس  Map-Reduce توصیف می کنيم. Map-Reduce [3] ، یک چارچوب است که برنامه نویسان تنها نیاز به مشخص نمودن تابع Map  و Reduce  دارند تا وظيفه هاي بزرگ را به صورت موازي در مورد خوشه هاي بزرگ بر روي ماشین آلات کالا اجرا نمايند. در مرحله پيش پردازش سند ، ما يک الگوريتم تکرار شونده براي محاسبه وزن tfidf در Map-Reduce  به منظور ارزیابی مهم بودن یک دوره براي  یک سند در یک مجموعه طراحي ميکنيم. سپس يک Mean Cluster در Map Reduce اجرا مي شود تا تمام اسناد رو به k خوشه تقسيم کند که هر سند متعلق به يک خوشه با همين معنا است. از همه مهمتر، در می یابیم که نادیده گرفتن شرایط با بالاترین فرکانس سند نمی تواند سرعت الگوریتم ما در Map-Reduce را بهبود ببخشد ، اما دقت خوشه سند را کمی بهبود مي بخشد. آزمایش نشان می دهد که روش مار رشد تقریبا خطی  در زمان مورد نیاز در حال اجرا  با افزایش اندازه مجموعه برای مجموعه هاي حاوی  چند ده هزار سند خواهد داشت.

II. Map Reduce و Hadoop

بسیاری از وظایف در دنیای واقعی دارای همان ویژگی ها است :

تعداد زيادي از سوابق براي توليد نتايج نسبي که هر کدام از بعضي روشها جمع آوري شده اند محاسبه شده اند. Map-Reduce یک مدل برنامه نویسی است که متخصص در مشکلات توزیعي ساختار " Divide and Conquer "  است. Map-Reduce با الهام از زبان یک زبان تابعی شامل Map و Reduce  و مفاهیم انتزاعی کار مي کند. تابع Map هر رکورد منطقي را در ورودي خودمان با مجموعه ای از جفت کلید های مياني ​​/ با ارزش محاسبه کرده و تابع Reduce يک کليد مياني و مجموعه ای از ارزش ها برای کلید به منظور ترکیب اطلاعات به دست آمده مناسب را می پذیرد.

شکل 1 دو مرحله پردازش را نشان مي دهد.

 

Apache Hadoop[4] ،  یک چارچوب نرم افزار جاوا است که شامل یک مدل Map-Reduce  و یک فایل سیستم توزیع شده است (HDFS  شبيه به GFS[5]).  HDFS  براي ذخيره سازي به مقیاس انبوه در سراسر دستگاه های متعدد طراحي شده است و به صورت شفاف خواندن / نوشتن و تهيه نسخه پشتيبان و fault tolerance را براي کاربران فراهم مي کند. Hadoop به طور فزاينده اي در حال محبوب شدن است [6,7] چرا که جزييات بهم ريخته موازي سازي ، تحمل خطا، توزیع داده ها و حفظ تعادل بار را پنهان مي کند.

III. محاسبه TFIDF در   MAP-REDUCE

وزن tfidf [8] (مدت فرکانس سند فرکانس معکوس) اغلب در متن استخراج معدن و بازیابی اطلاعات استفاده می شود. اهمیت یک دوره متناسب با تعداد دفعاتی که یک واژه در سند ظاهر می شود  افزایش می یابد   اما توسط فرکانس از این کلمه در مجموعه خنثي مي شود. بنابراین وزن قابلیت واژه در مجموعه را می توان با استفاده از طرح tfidf  کلاسیک در فرمول محاسبه کرد[1].                        

 

fij  ويژگي دوره فرکانس ti در سند dj است. اين موضوع ميتواند به وسيله |ti|/|dj| تعيين شده باشد که در آن تعداد تکرار دوره ti در سند dj مجموع ترمهاي سند dj است. N مجموع سندهاي نوشته شده و ni مجموع سندهايي شامل ترم ti است.ما ميتوانيم اين فرمول را [1] زماني که بايد |ti|و|dj|وni براي دريافت tfidf در Map-Reduce محاسبه کنيم ببينيم.

1)  مجموع زماني که به نظر ميرسد به يک دوره ti در يک سند داده شده :

فرمت داده هاي ورودي به تابع Map به صورت (نام سند ، محتوا) است، به این معنی که نام سند مهم و مرتبط با محتوای ارزش است. برای هر ترم در سند، خروجی تابع Map ((مدت، نام سند)،1) است که به معنی مدت تکرار یک زمان در این سند است. تابع Reduce خروجي تابع Map قبلي را مي پذيرد و با رکوردهاي همان کليد جمع مي کند.خروجي فرمت تابع Reduce به صورت (مدت،نام سند ، |ti|) است. در عمل، ما می توانیم یک تابع ترکیب برای سرعت بخشیدن به سرعت محاسبات اضافه کنیم.  این تابع از تابع ترکیب همان تابع Reduce است.

2) تعداد ترمها در هر سند :

در اين مرحله داده هاي ورودي ، داده هاي خروجي مرحله قبل است و تابع Map آنها را به فرمت (نام سند،(دوره،|ti|)) تبديل مي کند. تابع Reduce رکوردهاي به اشتراک گذاشته شده با همان نام سند را گرفته و روي هم شماره ترمهاي مختلف |ti|به |tj| را در همان سند انباشته مي کند. خروجي اين مرحله به صورت ( (دوره،نام سند)،(|ti|،|tj|)) خواهد بود.

3) تعداد اسناد ظاهر شده ترم |ti|:

تابع Map در اين مرحله خروجي مرحله بالا را به فرمت (دوره،(نام سند،|ti|،|dj|،1)) تبديل کرده که به اين معني است که اين ترم دريک سند  به نظر برسد.تابع Reduce "1" ها را در همان ترم ni  به روي هم انباشته مي کند. اين تعداد اسناد شامل ترم ti ميشود. خروجي اين مرحله به صورت ((دوره،نام سند،(|ti|،|dj|،ni)) است.

4) محاسبه tfidf :

خروجي مرحله 3 به اين معني که زمان رخداد ترم ti در سند dj است. |dj|برابر تعداد ترمهاي موجود در سند dj و ni تعداد سندهاي موجود در ترم ti است.ما فقط از فرمول 1 براي محاسبه ترم tfidf در سندهاي مختلف ميتوانيم استفاده کنيم. نتيجه خروجي به صورت (نام سند،(دوره& tfidf1،.....،ترمn & tfidfn)).

IV. خوشه بندي K-Means

خوشه بندي K-Means [9] k نقطه آغازين را انتخاب کرده و هر کدام را به عنوان نقطه مياني مجموعه K علامت گذاري مي کنيم. سپس براي هر عنصر در تمام مجموعه داده ها  که مجموعه داده هاي k به آن نزديکتر است. سپس ميانگين مرکز هر مجموعه را به وسيله نقاطي که به مجموعه نزديکتر هستند پيدا مي کنيم. با مجموعه ای جدید از مراکز (مرکز جرم)، اين الگوریتم را تکرار مي کنيم تا زمانی که همگرایی به اتمام برسد.

اجراي Document Clustering در Map-Reduce دو دايرکتوري به عنوان ورودي ميپذيرد:

یک دایرکتوری اسناد با خروجی محاسبه tfidf ، و یک پوشه مراکز با K  نقطه اولیه مرکز سند . این K سند اولیه از سوابق دایرکتوری اسناد انتخاب شده است. توجه داشته باشید که k-خط اطلاعات سند همان شرایط را با امکانات دارا است. در هر تکرار چارچوب Map-Reduce فايلهاي ورودي از دايرکتوري اسناد را به مجموعه اي از M قسمت پارتيشن خواهد کرد و اين قسمتها به صورت موازي با تابع Map پردازش خواهند شد.تابع Map اسناد را به صورت (نام سند،(دوره1،tfidf1،......،دورهn،tfidfn)) خواهد خواند. تابع Map بايد مشخص کند هرکدام از مجموعه هاي موجود از مراکز k سند (در مزکز پوشه) نزديک تر است و يک رکورد شامل تمام داده هاي اسناد را منتشر و k مرکز را به صورت (kمرکز،(نام سند،دوره1 & tfidf1،....،دورهn& ftidfn)) انتخاب کند. تابع Reduce ، k مرکز را دريافت کرده و تمام اسناد به اين kمرکز محدود مي شوند. بايد يک k مرکز جديد محاسبه شودو اين k مرکز در پوشه مرکزي قرار داده شود. براي محاسبه مسافت بين دو سند ما از شباهت متري کسينوس tfidf استفاده مي کنيم و ميانگين را براي k مرکز جديد حساب مي کنيم. توجه داشته باشید که مطالب در دایرکتوری سند در طول فرآیند تغییر نخواهد کرد.تمام خوشه بندي K-Means در Map-Reduce ميتواند با دو گام زير بيان شود:

 

V. ارزيابي تجربه

در آزمایش ما، ما از Hadoop نسخه 0.18.2  و یک خوشه با 5 ماشین (یکي به عنوان Master و بقيه به عنوان Slave) استفاده مي کنيم. هر دستگاه دارای دو پردازنده تک هسته ای (2.33GH) ، حافظه 1GB  و هارد دیسک 130GB  و پهنای باند شبکه 100Mbps بهره مي برند. پيکر يندي Hadoop داراي دو تابع Map اجرا شده بر روي يک هسته پردازنده به طور همزمان است.تعداد توابع Reduce را دقيقا ميتوان کنترل کرد. ما از اسناد طبقه بندي شده Sogou   (http://www.sogou.com/labs/dl/c.html) شامل 80 کيلو بايت سند در مجموع 211 مگابايت  استفاده مي کنيم. در مجموع 10 موضوع مختلف طبقه بندي شده است که يعني هر موضوع 8 کيلوبايت سند. اين اسناد تجزيه تحليل و ريشه يابي شده اند. تمام کلمات خالي در اين اسناد حذف شده اند. ما همیشه زمان در حال اجرا را به عنوان واحد  بهره وری مي سنجيم.  یک مسئله که در آزمایش های اولیه مشخص شد، شیوع "stragglers" بود، که به معنی یک یا تابع Reduce  به طور قابل توجهی طولانی تر از دیگران مي شود(این یک مشکل شایع است) به دليل توزيع Zipfian. در اين آزمايش ما ترم ها را با استفاده از بیشترین فرکانس سند حذف کرديم.

 

 

ما  95% از برش مرحله سوم را به قسمت سوم تعميم مي دهيم به اين معني که 5% ترم تکرار شونده در نظر گرفته نميشود.اين روش تا حد زيادي کارايي الگوريتم ما را در Hadoop افزايش مي دهد. از سوي ديگر  ما غير وابسته ها را در نظر نمي گيريم که دقت خوشه سند کمي بهبود يابد. شکل 2 زمان اجرای الگوریتم tfidf  را در خوشه خود ا با افزایش اندازه مجموعه برای مجموعه اي  حاوی 80k  سند نشان می دهد. ما نتايج را فقط براي ديدن اثر الگوريتمان در Hadoop ميگيريم.ما خوشه مان را براي پيکي بندي بهينه سازي نمي کنيم. ما زمان مورد استفاده براي محاسبه کل مجموعه که بيشتر از نيم ساعت است را پيدا مي کنيم. با این حال، زمان در حال اجرا و فضای مورد نیاز تقریبا به اندازه مجموعه خطی است، این ویژگی است که ما در پردازش داده ها و توده انتظار داريم . ما زمان اجراي خوشه بندي K-Means  در خوشه ها را اندازه ميگيريم  و سپس به طور معمولي K-Means را بر روي يک ماشين به عنوان نمونه پياده سازي مي کنيم. این نتایج در برابر یک حرکت معادل در دستگاه با زمان مشابه تکرار(5 بار)مقایسه شد. ما از شکل 3 ميتوانيم ببينيم که زمان اجراي الگوريتم K-Means بر روي خوشه با 5 ماشين نسبتا بسيار پايين تر از يک دستگاه مي باشد. از همه مهمتر، با افزایش اندازه مجموعه های ما، افزايش بهره وری به طور فزاینده ای مشهود است.

 

VI. نتيجه گيري

اين مقاله خوشه بندی اسناد جرم در یک سیستم توزیع شده از Hadoop را معرفی کرده است. آزمایش نشان می دهد که مقیاس پذیری روش ما در پردازش جرم  داده ها است. و کار ما را در طراحي و اجراي هر دو روش tfidf و K-means در Map-Reduce نشان ميدهد. ما باور داریم که کار ما به عنوان مثال از یک الگوی برنامه نویسی است که می تواند برای طیف گسترده ای از مشکلات تجزیه و تحلیل متن مفید. در نهایت، ما همیشه توجه داريم که روشهای جایگزین برای مسائل مشابه بر اساس Map- Reduce[10] وجود دارد. Hadoop  نيز فرصت بی سابقه ای برای محققان براي  رسیدگی به مشکلات دنیای واقعی در مقیاس کوچک فراهم می کند.

 

منابع :

[1] Roberto, J.B., M. Yiming, and S. Ramakrishnan, Scaling up all pairs similarity search, in Proceedings of the 16th  international conference on World Wide Web. 2007, ACM: Banff, Alberta, Canada.

[2] Michael, J.F., Evolution of distributed computing theory: from concurrency to networks and beyond, in Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. 2008, ACM: Toronto, Canada.

[3] Jeffrey, D. and G. Sanjay, MapReduce: simplified data processing on large clusters. Commun. ACM, 2008. 51(1): p. 107-113.

[4] Apache Lucene Hadoop[EB/OL].http://hadoop.apache.org/.

[5] Sanjay, G., G. Howard, and L. Shun-Tak, The Google file system, in Proceedings of the nineteenth ACM symposium on Operating systems principles. 2003, ACM: Bolton Landing, NY, USA.

[6] Jimmy, L., Brute force and indexed approaches to pairwise document similarity comparisons with MapReduce, in Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. 2009,ACM: Boston, MA, USA.

[7] ZHENG Xin-jie, ZHU Cheng-rong, and X. Qi-bang, Design and Implementation of Distributed Ray Tracing Using MapReduce. Computer Engineering, 2007(22).

[8] Salton, G. and T.Y. Clement, On the construction of effective vocabularies for information retrieval, in Proceedings of the 1973 meeting on Programming languages and information retrieval. 1973, ACM: Gaithersburg, Maryland.

[9] Fasulo, D., An Analysis of Recent Work on Clustering Algorithms, in Technical Report UW-CSE-01-03-02. 1999, ACM: University of Washington.

[10] Chu, C.-T., S.K. Kim, and Y.-A. Lin, Mapreduce for machine learning on multicore, in In Proceedings of Neural Information Processing Systems Conference (NIPS) 2007.

 


نظر دهی

برای نظر دهی باید وارد سایت شوید. با تشکر