خانه --> دیتاست (data set) --> دانلود مجموعه داده اخبار با طبقه بندی موضوعی (classification)

دانلود مجموعه داده اخبار با طبقه بندی موضوعی (classification)

به منظور استفاده دانشجوبان عزیز در انجام پایان نامه حدود بیست هراز مجموعه داده اخبار با طبقه بندی موضوعی (classification) و خوشه بندی سلسله مراتبی در زیر برای دانلود ارائه شده است.

دانلود مجموعه داده اخبار فارسی دسته بندی شده

Download (ZIP, 43.55MB)

بررسی و مقایسه الگوریتمهای خوشه بندی سلسله مراتبی

توصیف کلی از الگوریتمهای سلسله مراتبی در سند (Algorithm_Total14-8-90) [8] میباشد. هدف از تدوین سند فعلی، بررسی الگوریتمهای خوشه بندی با جزییات بیشتر و مقایسه آنها میباشد. در ابتدا به مشکلات خوشه بندی ROCK و cure میپردازیم. سپس به پیچیدگی زمانی و مقایسه الگوریتمهای متفاوت پرداخته و از میان خوشه بندیهای ارائه شده، خوشه بندی مناسب را انتخاب میکنیم. برای کاهش زمان از روشهای کاهش بعد استفاده شده است. تستهای انجام گرفته در این زمینه نیز در این سند آورده شده است.

ROCK: در مجموعه داده با ابعاد بالا، فاصله یا شباهت میان نقاط یکنواختتر میشود و خوشه بندی را سختتر میکند. محاسبه شباهت با استفاده از نزدیکترین همسایه مشترک[۱] در خوشه بندی ROCK میتواند برای حل این مشکل مفید باشد[۱,۶] . شباهت با استفاده از نزدیکترین همسایه مشترک اطلاعات کلیتری از فضای خوشه را نیز میدهد. با توجه اینکه خوشه بندی Rockدر نرمالسازی اتصالات خوشه موفق نیست، برای خوشه های پیچیده با چگالیهای متفاوت مناسب نیست. این خوشه بندی به انتخاب پارامتر بسیار حساس بوده و به نویز[۲] نیز حساس است.[۲] در این خوشه بندی ممکن است حالتی اتفاق بیفتد که تعداد خوشه ها را ۹ انتخاب کنیم و خروجی شامل یک خوشه بزرگ و ۸ خوشه نویز باشد. یا حالتی پیش بیاید که ۱۰۰۰ خوشه را بخواهیم و خروجی شامل ۵ خوشه بزرگ و بقیه نویز باشد. ROCK برای محاسبه مقدار اتصال برای جفت نقطهها از ضریب Jaccard استفاده میکند:

EROCK [4] به جای ضریب Jaccard، از cosine استفاده میکند. Cosine از طول سند مستقل است.

Cure: نتیجه خوشه بندی cure به انتخاب نقاط نماینده و ضریب کوچک شدن[۳] α بستگی دارد. اگر α بزرگ باشد، شبیه k-means و در صورتی که کوچک باشد نسبت به داده های دورافتاده[۴] حساس خواهد بود. جدول ۱ نشان می دهد که این خوشه بندی توانایی مقابله با مجموعه داده با ابعاد بالا را دارد.

CHAMELEON: با وجود اینکه CHAMELEON در خوشه بندی بسیار موثر است، داده دورافتاده را نمیتواند مدیریت کند و پارامترهای زیادی را مانند تعداد نزدیکترین همسایگی در گراف خلوت، شرط توقف تقسیم گراف و ضریب α برای تنظیم نزدیکی نسبی دارد.

جدول ۱ [۳]

مجموعه داده اخبار
مجموعه داده اخبار

Pca را با k- means ادغام می کند.[۸]

خوشه بندیهای سلسله مراتبی در جدول ۲ highlight شده است. Block و ERiC [8] به ترتیب خصیصه ها بستگی ندارند. Block مجموعه سطرها ERiC یکی از انواع خوشه بندی همبستگی میباشد. در خوشه بندی همبستگی، ارتباط میان داده ها به جای خود داده به کار می رود. برای مثال یک گراف امضا شده G=(V,E) می تواند مورد استفاده قرار بگیرد که در آن برچسب یال شباهت یا تفاوت گره ها را نشان میدهد. خوشه بندی همبستگی به task دیگری نیز مربوط میشود که در آن همبستگی میان خصیصه های بردارهای ویژگی در ابعاد بالا در فرآیند خوشه بندی مورد استفاده قرار میگیرد. این همبستگیها ممکن است در کلاسترهای مختلف متفاوت باشد. همبستگی میان زیرمجموعه خصیصه ها منجر به شکلهای مختلف خوشه میشود.

ERiC [8]شامل دو مرحله می باشد: ۱- در ابتدا برای همسایگی محلی هر داده، همبستگی بعد محلی تعیین میشود. همبستگی بعد محلی این داده کمترین تعداد eigenvalue است که حداقل به اندازه α از کل واریانس را توصیف کند. نقاط همسایگی میتوانند k نزدیکترین همسایه باشند. K بایستی به طور قابل ملاحظه از d بزرگتر باشد. با توجه به این مساله این نوع خوشه بندی برای متن مناسب نیست زیرا در بسیاری از موارد با ابعاد مجموعه داده از تعداد داده ها بزرگتر است.

جدول ۲- [۵]

مجموعه داده اخبار
مجموعه داده اخبار

جدول ۳- خوشهبندهای اسناد وب [۷]

مجموعه داده اخبار
مجموعه داده اخبار

جدول ۴- خوشهبندهای اسناد وب [۷]

جدول ۵- مقایسه خوشهبندها [۷]

نام الگوریتم

پیچیدگی محاسباتی

مزایا

معایب

پیاده سازی

توانایی مقابله با مجموعه داده با ابعاد بالا [۳]

HAC -Single Link (nearest neighbor) [minimum spanning tree]

O(n2 )- در صورت استفاده از آرایه نزدیکترین همسایگی

۱-وجود درخت‌واره، از مهمترین مزایای این روش به شمار میرود.

۲- الگوریتمهای سلسله مراتبی کلیه اشکال را تشکیل میدهند.

۱- تأثیر زنجیرهای

۲- نسبت به داده های پرت آسیب پذیر است.

دارد

خیر

HAC -Complete Link(Farthest Neighbor)

O(n2 log n)

۱-وجود درخت‌واره، از مهمترین مزایای این روش به شمار میرود.

۲- الگوریتمهای سلسله مراتبی کلیه اشکال را تشکیل میدهند.

نسبت به وجود داده های پرت آسیب پذیر است

دارد

خیر

HAC -Average-Link

O(n2 log2n)

۱-وجود درخت‌واره، از مهمترین مزایای این روش به شمار میرود.

۲- الگوریتمهای سلسله مراتبی کلیه اشکال را تشکیل میدهند.

نسبت به وجود داده های پرت حساس است

دارد

خیر

HAC -Centroid Based

O(n2 log2n)

۱-وجود درخت‌واره، از مهمترین مزایای این روش به شمار میرود.

۲- الگوریتمهای سلسله مراتبی کلیه اشکال را تشکیل میدهند.

۱-علاوه بر ماتریس فاصله نیاز به خود ماتریس داده ها نیز دارد

۲- تنها یک نقطه مرکز ثقل را به عنوان نماینده یک خوشه در نظر می گیرد

دارد

خیر

HAC -Ward’s Distance Method

O(n2 log2n)

۱-وجود درخت‌واره، از مهمترین مزایای این روش به شمار میرود.

۲- الگوریتم های سلسله مراتبی کلیه اشکال را تشکیل میدهند.

۳-نسبت به روشهای قبلی حساسیت کمتری نسبت به داده های پرت دارد.

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

در rapid ندارد. در weka دارد.

خیر

BIRCH

O(n)

۱-تنها یکبار مجموعه داده را اسکن میکند.

۲-دارای مکانیزم تجدید/بازسازی در ساخت درخت CF است.

۳-پیچیدگی زمانی فوق العاده خوبی دارد.

۴-مقیاسپذیری آن بر خلاف الگوریتمهای معمولی سلسله مراتبی بسیار عالی است.

۵-متناسب با منابع سخت افزاری موجود بهترین کارایی خود را ارائه میدهد.

اگر خوشه ها ذاتا دارای شکل کروی نباشند، الگوریتم خوب عمل نمیکند.

دارد

خیر

ROCK

O(n2+nmmma+n2logn) که در آن mm و ma به ترتیب بیشترین و میانگین تعداد همسایه ها و n تعداد اشیاء است.

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

در عملیات ادغام، نزدیکی بین کلاستری را ملاک قرار نمیدهد.

   

Cure

O(n2Logn) برای داده های با ابعاد بالا و O(n2) برای داده های دو بعدی و سه بعدی

۱-تشخیص خوشه هایی با شکل غیر کروی و با سایزهای متنوع

۲-حساسیت کم نسبت به داده های پرت

۳- این خوشه بندی توانایی مقابله با مجموعه داده با ابعاد بالا را دارد[۳].

در عملیات ادغام، نزدیکی درون کلاستری را ملاک قرار نمیدهد.

 

بله

Chameleon

در حالتی که مجموعه داده با ابعاد بالا داشته باشیم، پیچیدگی زمانی O(n^2) خواهد بود.

۱-در عملیات ادغام، فاصله بین کلاستری و نزدیکی درون کلاستری را ملاک قرار میدهد.

۲-تشخیص خوشه هایی با شکل غیر کروی و با سایزهای متنوع) شکلهایی یا کیفیت بهتر نسبت به Birch)

  1. به پارامترها خیلی حساس است.
  2. گراف باید متناسب با حافظه باشد.
  3. ادغام را به درستی انجام نمیدهد.
   

HiCO

   
  1. یک معیار فاصله نسبتا پیچیده ای را به کار می برد که توان پردازشی قابل ملاحظه ای را نیاز خواهد داشت.

۲- سلسله مراتب نسبتا ساده ای از خوشه های همبسته را درنظر می گیرد و سلسله مراتب پیچیده را نمی تواند شناسایی کند.

   

ERiC

O(n2 d2)

 
  1. در مرحله اول k همسایگی را برای هر داده درنظر می گیرد که تعداد آن بایستی از ابعاد بزرگتر باشد.
   

block

 

در مواردی که خوشه بندی اسناد و کلمات نیاز است. به جای اینکه جداگانه هر خوشه بندی اسناد براساس کلمات و خوشه بندی کلمات براساس اسناد صورت بگیرد، همزمان خوشه بندی اسناد و کلمات را انجام میدهد.

     

DiSH

   

به ترتیب خصیصه ها بستگی دارد.

   

CASH

   

به ترتیب خصیصه ها بستگی دارد.

   

مراجع

۱) Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data, L. Ertöz, M. Steinbach, V. Kumar, University of Minnesota

Minneapolis, MN USA

۲) On Data Clustering Analysis: Scalability, Constraints and Validation

O. R. Zaiane, A. Foss, Ch. Lee, and W. Wang, University of Alberta, Edmonton, Alberta, Canada

۳) Survey of Clustering Algorithms, R. Xu, IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 16, NO. 3, MAY 2005

۴) Document Topic Generation in Text Mining by Using Cluster Analysis with

EROCK, R. Ahmad, A. Khanum, National University of Science & Technology

Rawalpindi, Pakistan

۵) Clustering High-Dimensional Data: A Survey on Subspace Clustering, Pattern-Based Clustering, and Correlation Clustering, H.P. KRIEGEL, P. KROGER, and A. Z. Ludwig-Maximilians-Universitat Muunchen

۶) Cluster Cores-based Clustering for High Dimensional Data, Y.D. Shen, Z. Y. Shen and Sh.M. Zhang, Q. Yang

۷) A Review of Web Document Clustering Approaches, N. Oikonomakou, M. Vazirgiannis, Athens University of Economics & Business

۸) On Exploring Complex Relationships of Correlation Clusters, E. Achtert, Ch. B¨ohm, H. P. Kriegel, P. Kr¨oger, A. Zimek, In Proc. 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), Banff, Canada, 2007

  1. shared nearest neighbor approach

  2. noise

  3. shrinking

  4. outlier

آدرس کانال تلگرام سایت بیگ دیتا:

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

جهت دیدن سرفصل های دوره های آموزشی بر روی اینجا کلیک کنید.

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *