ارائه یک الگوریتم خوشه بندی برای داده های دسته ای با ترکیب معیارها

نبی لو, مریم; دانشپور, نگین

ارائه یک الگوریتم خوشه بندی برای داده های دسته ای با ترکیب معیارها

نویسندگان

دانشگاه تربیت دبیر شهید رجایی

چکیده

خوشه بندی یکی از تکنیک های اصلی داده کاوی است. خوشه بندی فرایندی است که مجموعه داده ها را داخل گروه هایی طبقه بندی می کند. در خوشه بندی داده های موجود در یک خوشه بیشترین شباهت را به هم دارند و داده های موجود در دو خوشه متفاوت بیشترین تفاوت را با هم دارند. الگوریتم های خوشه بندی با توجه به نوع داده ها به دو دسته تقسیم می شوند: الگوریتم های خوشه بندی داده های عددی و الگوریتم های خوشه بندی داده های دسته ای. الگوریتم های خوشه بندی داده های دسته ای به دلیل ماهیت و کاربرد این داده ها نسبت به الگوریتم های خوشه بندی داده های عددی از اهمیت بالایی برخوداراند. هر یک از این الگوریتم ها با توجه به نوع داده (عددی یا دسته ای) از معیارهای شباهت متفاوتی در خوشه بندی استفاده می کنند. در این مقاله یک روش جدید در خوشه بندی با استفاده از ترکیب معیارهای شباهت Overlay و Jaccard روی یک الگوریتم سلسله مراتبی برای داده های دسته ای پیشنهاد می شود. معیار Overlay تفاوت بین داده ها را به صورت صفر و یک بیان می کند که این امر باعث از بین رفتن برخی اطلاعات مربوط به داده ها می شود. معیار Jaccard نیز اگر به تنهایی برای اندازه گیری شباهت میان داده ها استفاده گردد بیشتر خوشه ها در یک ناحیه از مجموعه داده ها انتخاب می شوند. بنابراین در این مقاله ترکیبی از دو معیار به کار رفته است.آزمایشات نشان می دهد که روش ارائه شده در این مقاله توانسته است که نتایج حاصل از خوشه بندی را بهبود ببخشد و بطور متوسط 10 درصد بهبود بر روی هر فاکتور ارزیابی داشته است.

کلیدواژه‌ها

عنوان مقاله [English]

A clustering algorithm for categorical data with combining measures

نویسندگان [English]

Maryam Nabiloo
Negin Daneshpour

چکیده [English]

Clustering is one of the main techniques in data mining. Clustering is a process that classifies data set into groups. In clustering, the data in a cluster are the closest to each other and the data in two different clusters have the most difference. Clustering algorithms are divided into two categories according to the type of data: Clustering algorithms for numerical data and clustering algorithms for categorical data. The clustering algorithms for categorical data are more important than clustering algorithms for numerical data because of the nature and application of these data. Each of these algorithms uses different similarity measures according to the type of data (numeric or categorical). In this paper, a new clustering method is proposed for clustering by combining Overlay and Jaccard similarity measures on a hierarchical algorithm for categorical data. Overlay measure represents similarities between the data as one and zero which caused the loss of some information. Jaccard measure If used alone to measure the similarity between data set, most clusters are selected in the particular area of data collection. So in this paper a combination of the two measures are used. Experimental results show that the proposed method improves the results of clustering. Resulted improvemen is 10% on any evaluation factor in average.

کلیدواژه‌ها [English]