نمایش نتایج: از شماره 1 تا 5 , از مجموع 5

موضوع: الگوریتم کلاسترینگ

  1. #1
    عضو انجمن sat98 آواتار ها
    تاریخ عضویت
    Aug 2010
    نوشته ها
    101
    تشکر تشکر کرده 
    29
    تشکر تشکر شده 
    222
    تشکر شده در
    160 پست

    پیش فرض الگوریتم کلاسترینگ

    کلاسترينگ سلسله مراتبي (Hierarchical Clustering)


    با در دست داشتن N نمونه داده براي کلاستر شدن و يک ماتريس فاصله يا شباهت به ابعاد N*N ، پروسه اصلي کلاستريگ سلسله مراتبي به صورت زير ميباشد :
    1. با تخصيص هر نمونه به يک کلاستر شروع کنيد . يعني اگر N نمونه داشته باشيم ، N کلاستر داريم که هر يک داراي يک نمونه مي باشند . فاصله بين کلاستر ها همان فاصله بين کلاستر هاي آنهاست .
    2. دو کلاستري را که نزديک تر هستند پيدا کنيد و آنها را ادغام کنيد . حالا يک کلاستر کمتر داريم .
    3. فاصله کلاستر جديد را با هر يک از کلاسترهاي قديمي محاسبه کنيد .
    4. مراحل 2 و3 را آنقدر تکرار کنيد که همه نمونه ها در يک کلاستر به اندازه N قرار بگيرند
    مرحله 3 مي تواند به روش هاي مختلفي انجام گيرد که کلاستريگ single-linkage ، complete-linkage و Average-linkage را مشخص مي کند .
    در کلاستريگ single-linkage (که روش connectedness يا minimum هم ناميده مي شود( ، فاصله يک کلاستر از کلاستر ديگر را کوتاهترين فاصله هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر مي گيرند .
    اگر داده ها شامل شباهت باشند ، شباهت يک کلاستر تا کلاستر ديگر را برابر بيشترين شباهت هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر مي گيرند .
    در کلاستريگ complete-linkage (که روش diameter يا maximum هم ناميده مي شود(، فاصله يک کلاستر از کلاستر ديگر را بزرگترين فاصله هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر مي گيرند .
    در کلاستريگ average-linkage ، فاصله يک کلاستر از کلاستر ديگر را ميانگين فاصله هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر مي گيرند .
    کلاستريگ سلسله مراتبي ، agglomerative يا متراکم شونده نيز ناميده مي شود ، زيرا کلاستر ها را به تدريج ادغام مي کند .کلاسترينگ تقسيم کننده يا divisive هم وجود دارد که به صورت عکس عمل مي کند ، به اين صورت که ابتدا همه اشياء را در يک کلاستر قرار مي دهد و به تدريج آن را به قطعه هاي کوچکتر تقسيم مي کند.
    البته اين نوع کلاستريگ به ندرت مورد استفاده قرار مي گيرد . شکل زير نحوه عملکرد اين دو الگوريتم را نشان مي دهد.
    الگوريم کلاسترينگ single-linkage :


    اين الگوريم agglomerative است و زمانيکه کلاستر ها براي تشکيل کلاستر هاي جديد ، ادغام مي شوند ، سطرها و ستون هاي مربوط به آنها را در ماتريس مجاورت پاک مي کند .
    ماتريس مجاورت به ابعاد N*N ، D = [d(i,j)] را در نظر بگيريد . به کلاستر ها اعداد 0 و 1 و ... و n-1 ، تخصطص داده مي شود و L(k) ، سطح k امين کلاسترينگ است . کلاستري با شماره m به صورت (m) نمايش داده مي شود و مجاورت بين کلاسترهاي (r) و (s) به صورت d[(r) , (s)] نمايش داده مي شود .
    الگوريتم شامل مراحل زير است :
    1. با کلاسترينگ با سطح L(0)=0 و m=0 شروع کنيد .
    2. بي شباهت ترين جفت از کلاستر ها را پيدا کنيد . ((r),(s)) :
    D[(r),(s)] = min d[(i),(j)]
    مينيمم بين همه جفت کلاسترها در نظر گرفته مي شود .
    3.m=m+1 قرار دهيد . کلاستر هاي (r) و (s) را ادغام کنيد تا تا کلاستريگ بعدي را تشکيل دهد . سطح کلاستريگ را به اين صورت تنظيم کنيد :
    L(m) = d[(r),(s)]
    4. ماتريس مجاورت (D) را update کنيد . به اين ترتيب که سطرها و ستون هاي مربوط به کلاسترهاي(r) و (s) را حذف کنيد و يک سطر و ستون جديد براي کلاستري که تازه تشکيل شده ايجاد کنيد .
    مجاورت بين کلاستر جديد (r,s) و کلاستر هاي قديمي k به اين ترتيب محاسبه مي شود:
    d [(k), (r,s)] = min d[(k),(r)], d[(k),(s)]
    5. اگر تمام اشياء در يک کلاستر قرار گرفتند متوقف مي شويم ، در غير اين صورت به مرحله 2 باز مي گرديم .
    يک مثال :
    به عنوان مثال يک کلاسترينگ از فواصل بين يک سري از شهر هاي ايتاليايي که بر حسب کيلومتر بيان شده اند را بررسي مي کنيم . روش استفاده شده ، single-linkage مي باشد .
    ماتريس فاصله که ورودي مي باشد به صورت زير است : (براي همه کلاستر ها L=0 مي باشد .)
    نزديکترين شهرها MI و TO هستند ، که به فاصله 138 کيلومتر مي باشند . آنها در يک کلاستر به نام MI/TO ادغام مي شوند . سطح کلاستر جديد L(MI/TO) = 138 و m=1 مي باشد .
    مي توانيم فاصله اين شيء ترکيبي را از همه اشياء ديگر محاسبه کنيم . در کلاسترينگ single-linkage ، قانون اين است که فاصله شيء ترکيبي تا ساير اشياء ، برابر کوتاهترين فاصله از هر عضو از کلاستر تا شيء خارجي مي باشد . بنابراين فاصله MI/TO تا RM ، 564 انتخاب مي شود که فاصله از MI تا RM مي باشد.بعد از ادغام MI و TO ، خواهيم داشت :


    min d(i,j) = d(NA,RM) = 219 =>
    NA وRM در کلاستر جديدي به نام NA/RM ادغام مي شوند .
    L(NA/RM) = 219
    m = 2

    min d(i,j) = d(BA,NA/RM) = 255 =>
    BA و NA/RM در کلاستر جديدي به نام BA/ NA/RM ادغام مي شوند .
    L(BA/NA/RM) = 255
    m = 3


    min d(i,j) = d(BA/NA/RM,FI) = 268 =>
    BA/NA/RM و FI در کلاستر جديدي به نام BA/FI/NA/RM ادغام مي شوند .
    L(BA/FI/NA/RM) = 268
    m = 4


    نهايتاً دو کلاستر باقيمانده را در سطح 295 ادغام مي کنيم .
    پروسه انجام شده به صورت خلاصه در ساختار سلسله مراتبي درخت زير نمايش داده شده است .

    مشکلات :
    نقاط ضعف اصلي روش هاي کلاسترينگ agglomerative عبارتند از :
    ? پيچيدگي زماني ، حداقل ( O(n است که n ، تعداد کل اشياء مي باشد .
    ? مراحلي که قبلاً انجام شده ، قابل بازگشت نيستند و نمي توان تأثير قدم هاي قبلي را undo کرد .

  2. تعداد تشکر ها ازsat98 به دلیل پست مفید


  3. # ADS




     

  4. #2
    عضو جدید
    تاریخ عضویت
    Dec 2012
    نوشته ها
    1
    تشکر تشکر کرده 
    0
    تشکر تشکر شده 
    1
    تشکر شده در
    تشکر شده 1 بار در 1 پست

    پیش فرض پاسخ : الگوریتم کلاسترینگ

    باتشکر

    مطلب خوبی بود

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

  5. تعداد تشکر ها از rezaje به دلیل پست مفید


  6. #3
    کاربر اخراج شده
    تاریخ عضویت
    Dec 2012
    نوشته ها
    166
    تشکر تشکر کرده 
    57
    تشکر تشکر شده 
    130
    تشکر شده در
    106 پست

    پیش فرض پاسخ : الگوریتم کلاسترینگ

    جالب بود ، ولی زیاد به کار نمیاد

  7. تعداد تشکر ها از coloserver به دلیل پست مفید


  8. #4
    عضو انجمن fr0nk آواتار ها
    تاریخ عضویت
    Jun 2011
    محل سکونت
    /etc/passwd
    نوشته ها
    379
    تشکر تشکر کرده 
    72
    تشکر تشکر شده 
    373
    تشکر شده در
    248 پست

    پیش فرض پاسخ : الگوریتم کلاسترینگ

    میشه بپرسم چرا به کار نمیاد ؟

  9. تعداد تشکر ها از fr0nk به دلیل پست مفید


  10. #5
    کاربر اخراج شده
    تاریخ عضویت
    Dec 2010
    محل سکونت
    Shargi Azar Baijan
    نوشته ها
    413
    تشکر تشکر کرده 
    163
    تشکر تشکر شده 
    593
    تشکر شده در
    410 پست

    پیش فرض پاسخ : الگوریتم کلاسترینگ

    نقل قول نوشته اصلی توسط coloserver نمایش پست ها
    جالب بود ، ولی زیاد به کار نمیاد
    اگر امکان داره شما اونایی که به کار میان بزارین ؟!
    با تشکر از استارت و شما دوست عزیز که میخواین به درد بخورهارو بزارین

  11. تعداد تشکر ها از sniper000man به دلیل پست مفید


اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

موضوعات مشابه

  1. چکار کنیم سایتمان هنگام جستجو اینگونه نمایش داده شود
    توسط GREAT در انجمن مباحث و منابع آموزشی
    پاسخ ها: 8
    آخرين نوشته: December 9th, 2017, 12:57
  2. داستان الگوریتم گوگل
    توسط sibait در انجمن مباحث و منابع آموزشی
    پاسخ ها: 0
    آخرين نوشته: July 16th, 2017, 04:19
  3. پاسخ ها: 4
    آخرين نوشته: July 21st, 2014, 18:53
  4. شرایط اعطای نمایندگی رایتل در شهرستان کوچک
    توسط HesaM4388 در انجمن مباحث دیگر
    پاسخ ها: 3
    آخرين نوشته: August 24th, 2013, 20:25
  5. فروش دامنه مناسب سایتهای وبمستری
    توسط ToooPDL در انجمن فروش دامین
    پاسخ ها: 1
    آخرين نوشته: July 8th, 2011, 21:58

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •