density-based clustering
در نشریات گروه فنی و مهندسی-
Distance-based clustering methods categorize samples by optimizing a global criterion, finding ellipsoid clusters with roughly equal sizes. In contrast, density-based clustering techniques form clusters with arbitrary shapes and sizes by optimizing a local criterion. Most of these methods have several hyper-parameters, and their performance is highly dependent on the hyper-parameter setup. Recently, a Gaussian Density Distance (GDD) approach was proposed to optimize local criteria in terms of distance and density properties of samples. GDD can find clusters with different shapes and sizes without any free parameters. However, it may fail to discover the appropriate clusters due to the interfering of clustered samples in estimating the density and distance properties of remaining unclustered samples. Here, we introduce Adaptive GDD (AGDD), which eliminates the inappropriate effect of clustered samples by adaptively updating the parameters during clustering. It is stable and can identify clusters with various shapes, sizes, and densities without adding extra parameters. The distance metrics calculating the dissimilarity between samples can affect the clustering performance. The effect of different distance measurements is also analyzed on the method. The experimental results conducted on several well-known datasets show the effectiveness of the proposed AGDD method compared to the other well-known clustering methods.Keywords: Density-based Clustering, Distance-based Clustering, Gaussian Density
-
Spatio-temporal (ST) clustering is a relatively new field in data mining with great popularity, especially in geographic information. Moving objects are a type of ST data where the available information on these objects includes their last position. The strategy of performing the clustering operation on all-time sequences is used for clustering moving objects. The problem with density-based clustering, which uses this strategy, is that the density of clusters may change at any point in time because of the displacement of points. Hence, the input parameters of an algorithm like DBSCAN used to cluster moving objects will change and have to be determined again. The DBSCAN-based methods have been proposed so far, assuming that the value of input parameters is fixed over time and does not provide a solution for their automatic determination. Nonetheless, with the objects moving and the density of the clusters changing, these parameters have to be determined appropriately again at each time interval. The paper used a dynamic multi-objective genetic algorithm to determine the parameters of the DBSCAN algorithm dynamically and automatically to solve this problem. The proposed algorithm in each time interval uses the clustering information of the previous time interval to determine the parameters. Beijing traffic control data was used as a moving dataset to evaluate the proposed algorithm. The experiments show that using the proposed algorithm for dynamic determination of DBSCAN input parameters outperforms DBSCAN with fixed input parameters over time in terms of the Silhouette and Outlier indices.
Keywords: Density-based Clustering, DBSCAN, Dynamic Multi-Objective Optimization, Clustering Moving Objects, Cluster Validity Index -
شبکه های آبرسانی ارتباط مستقیمی با توسعه اقتصادی و اجتماعی جوامع شهری دارند. با توجه به افزایش سریع جمعیت و توسعه شهرنشینی لازم است تا این شبکه ها به طور مناسب نگهداری و بازسازی شوند. در این مقاله، با بهره گیری از روش یادگیری غیرنظارتی و با استفاده از الگوریتم خوشه بندی مبتنی بر چگالی OPTICS مناطق اولویت دار شبکه های توزیع آب جهت بازسازی تعیین گردیدند. 361 حادثه شکستگی رخ داده در یکی از پهنه های شبکه توزیع آب مشهد مورد بررسی واقع شد. این الگوریتم در مجموع 16 خوشه را در پنج سطح متفاوت اهمیت شناسایی کرد. این 16 خوشه که برخی زیرخوشه دیگری محسوب می شوند از منظر نرخ شکست با یکدیگر مورد مقایسه قرار گرفتند و سه خوشه که به ترتیب نرخ شکستگی برابر با 79/1، 62/2 و 50/1 (حادثه/ 100 کیلومتر/ سال) را داشتند، به عنوان اولویت های اصلی بازسازی معرفی شدند. نرخ شکست میانگین در کل شبکه مورد بررسی برابر با 14/8 بود. در ادامه، خوشه های شناسایی شده از منظر جنس و قطر لوله نیز مورد ارزیابی قرار گرفته و عوامل موثر در نرخ شکستگی آن ها، بررسی شدند. نتایج نشان داد که الگوریتم خوشه بندی OPTICS با شناسایی خوشه های متعدد و سطح بندی آن ها توانایی قابل توجهی در تشخیص پهنه های اولویت دار برای برنامه های بازسازی دارد؛ بنابراین از روش پیشنهادی به عنوان ابزاری کاربردی و انعطاف پذیر برای اولویت بندی بازسازی شبکه توزیع آب، شناسایی علل اصلی حوادث با پرهیز از روش های محاسباتی پیچیده و طولانی و به دور از قضاوت شخصی کارشناسان می توان استفاده کرد.
کلید واژگان: خوشه بندی مبتنی بر چگالی، تحلیل مکانی، شبکه های زیرساختی، شکستگی، ارزیابی وضعیت، شبکه توزیع آب، الگوریتم OPTICSWater supply networks are directly related to the economic and social development of urban communities. Due to the rapid increase in population and urbanization, these networks should be properly maintained and rehabilitated. In this paper, an unsupervised learning method with OPTICS density-based clustering algorithm is used to determine the priority areas for rehabilitation. 361 burst event data in one of the Mashhad water network zones were analyzed. The algorithm identified a total number of 16 clusters at 5 different levels of importance. These 16 clusters, which are considered sub-clusters for higher levels, were compared in terms of burst rate. Three clusters with failure rates of 79.1, 62.2, and 50.1 (failures/100 km/year) were introduced as the main priorities for rehabilitation and renovation, respectively. The average burst rate in the whole network was 14.8. The identified clusters were examined in terms of pipe material and diameter and their most affecting factors on the burst rate. The obtained results showed that the OPTICS clustering algorithm has a significant ability to determine priority zones for the rehabilitation plan, by identifying multiple clusters and their according levels. Therefore, the proposed method can be used as a practical and flexible tool to prioritize the rehabilitation process of water networks and identify the main causes of failure events, avoiding complex computational methods or the personal judgment of experts.
Keywords: Density-Based Clustering, spatial analysis, Infrastructure Networks, Failure, Condition assessment, Water Distribution Network, OPTICS Algorithm -
تشخیص داده های نویز(پرت یا غیرعادی) از داده های جریان در شبکه های توزیع آب در مرحله آماده سازی و پیش پردازش داده ها برای دستیابی به داده های تاریخی قابل اعتماد انجام می گیرد؛ که در بهبود روش های ارزیابی و مدیریت نشت و بهره برداری موثر از شبکه، مهم و ضروری است. هدف از ارائه این مقاله توسعه یک متدولوژی جدید بر مبنای روش های یادگیری بدون نظارت، جهت شناسایی داده های پرت یا غیرعادی در یک مجموعه داده های جریان در شبکه های توزیع آب می باشد. متدولوژی توسعه داده شده شامل مراحل 1- جمع آوری داده های مورد نیاز، 2- صحت سنجی و نرمال سازی داده ها و 3- شناسایی و کشف داده های پرت یا غیرعادی با استفاده از الگوریتم خوشه بندی مکانی مبتنی بر چگالی مقاوم در مقابل نویز (DBSCAN) می باشد. متدولوژی پیشنهادی برای داده های جریان ورودی به یک منطقه در شبکه توزیع آب شهری تهران با تواتر زمانی برداشت داده 15 دقیقه برای سال 1394 به کار برده شد. نتایج نشان داد که متدولوژی توسعه داده شده قابلیت شناسایی داده های پرت ناشی از انواع شکستگی ها و مصارف مجاز غیرمعمول نظیر مصارف ناشی از تغییر در الگوی مصرفی جمعیت یا مصارف مجاز غیرعادی را دارد. از اینرو این متدولوژی را می توان به عنوان یک ابزار کاربردی و انعطاف پذیربرای پایش داده های جریان و شناسایی و حذف انواع داده های پرت از آنها مورد استفاده قرار داد.
کلید واژگان: داده پرت، خوشه بندی مبتنی بر چگالی، الگوریتم DBSCAN، داده های جریان، شبکه توزیع آبAnomaly or outlier detection of flow data in water distribution networks (WDNs) is implemented in data preparation and prepossessing step to achieve reliable historical data; it is important to improve the leakage assessment and management methods and the operations of the network efficiently. The main objective of this paper is to develop a new methodology based on unsupervised learning methods for anomaly or outlier detection in a flow data set in WDNs. The developed methodology includes three steps 1- required data acquisition, 2- data validation and normalization, and 3- anomaly or outlier detection using the density-based spatial clustering of application with noise (DBSCAN) algorithm. The proposed methodology is applied for inflow data into an area in Tehran's urban water distribution network with 15-min sampling intervals for 1394. The results showed that the developed methodology is capable to the detection anomalies due to different type of pipe breaks and unusual legitimate consumption such as water usage due to changes in water consumption pattern or unauthorized consumption. Therefore, this methodology can be used as an applicable and flexible tool for monitoring flow data and detecting and eliminating of different types of outliers from them.
Keywords: outlier, Density-Based Clustering, DBSCAN Algorithm, Flow Data, Water Distribution Network -
خوشه بندی مبتنی بر چگالی یکی از روش های مورد توجه در داده کاوی و DBSCANنمونه ای پرکاربرد از این روش است. DBSCAN علاوه بر مزایای خود معایبی نیز دارد. به عنوان نمونه، تعیین پارامترهای ورودی این الگوریتم توسط کاربر کار مشکلی است. در مقاله حاضر سعی شده است، اصلاحاتی روی یکی از الگوریتم های مبتنی برچگالی به نام ISB-DBSCAN انجام شود. در روش پیشنهادی همانند ISB-DBSCAN از یک پارامتر ورودی k به عنوان تعداد نزدیک ترین همسایه استفاده شده است. از آنجا که تعیین پارامتر k ممکن است، برای کاربر مشکل باشد، یک روش پیشنهادی با الگوریتم ژنتیک برای تعیین خودکار k نیز ارائه شده است. برای ارزیابی روش های پیشنهادی آزمایش هایی روی یازده مجموعه داده استاندارد انجام شد و دقت خوشه بندی در روش ها مورد ارزیابی قرار گرفت. نتایج به دست آمده در مقایسه با دیگر روش های موجود نشان داد که روش پیشنهادی در مجموعه داده های مختلف، نتایج بهتری را کسب کرده است.
کلید واژگان: خوشه بندی مبتنی بر چگالی، پارامتر همسایگی، خوشه بندی با چگالی متفاوتClustering is one of the main tasks in data mining, which means grouping similar samples. In general, there is a wide variety of clustering algorithms. One of these categories is density-based clustering. Various algorithms have been proposed for this method; one of the most widely used algorithms called DBSCAN. DBSCAN can identify clusters of different shapes in the dataset and automatically identify the number of clusters. There are advantages and disadvantages in this algorithm. It is difficult to determine the input parameters of this algorithm by the user. Also, this algorithm is unable to detect clusters with different densities in the data set. ISB-DBSCAN algorithm is another example of density-based algorithms that eliminates the disadvantages of the DBSCAN algorithm. ISB-DBSCAN algorithm reduces the input parameters of DBSCAN algorithm and uses an input parameter k as the nearest neighbor's number. This method is also able to identify different density clusters, but according to the definition of the new core point, It is not able to identify some clusters in a different data set.
This paper presents a method for improving ISB-DBSCAN algorithm. A proposed approach, such as ISB-DBSCAN, uses an input parameter k as the number of nearest neighbors and provides a new definition for core point. This method performs clustering in three steps, with the difference that, unlike ISB-DBSCAN algorithm, it can create a new cluster in the final stage. In the proposed method, a new criterion, such as the number of dataset dimensions used to detect noise in the used data set. Since the determination of the k parameter in the proposed method may be difficult for the user, a new method with genetic algorithm is also proposed for the automatic estimation of the k parameter. To evaluate the proposed methods, tests were carried out on 11 standard data sets and the accuracy of clustering in the methods was evaluated. The results showe that the proposed method is able to achieve better results in different data sets compare to other available methods. In the proposed method, the automatic determination of k parameter also obtained acceptable results.Keywords: Density-based clustering, neighborhood parameter, clustering with different density -
خوشه بندی یکی از شاخه های مهم موجود در داده کاوی است که هدف آن تقسیم داده ها به زیرمجموعه های معناداری است که خوشه نامیده می شوند. این تکنیک شامل فرآیند پیدا کردن گروه بندی طبیعی در مجموعه داده ها، بر اساس شباهت و تفاوت است به نحوی که اطلاعات قبلی کمی در مورد داده ها در دسترس است و یا اصلا اطلاعاتی در دسترس نیست. در طی دهه های متمادی الگوریتم های فراوانی برای خوشه بندی در رویکردهای مختلف و متفاوت و یا ترکیبی از آنها ایجاد شده اند. در این مقاله الگوریتمی بر پایه رویکردهای مبنی بر تراکم و سلسله مراتبی ارائه می شود. DBSCANیکی از الگوریتم های مطرح شده در رویکرد مبتنی بر تراکم است. این الگوریتم نیاز به دو پارامتر دارد که تعیین آن هنوز یک چالش بزرگ است. در روش پیشنهادی پارامترهای الگوریتم DBSCANطوری تنظیم می شود که بدون نیاز به دخالت کاربر، خوشه های احتمالی بصورت خودکار یافت شوند. سپس خوشه های نزدیک به یکدیگر به قدری باهم ادغام می شوند تا کیفیت خوشه های نهایی به نحو مطلوبی ارتقا یابد. بدین ترتیب خوشه های باکیفیت و دقیقی بدست خواهد آمد. در انتها برای آزمایش این الگوریتم ترکیبی جدید از داده های واقعی موجود در پایگاه داده UCIاستفاده شد. نتایج نشان می دهد که الگوریتم ترکیبی جدید کارایی بیشتر و دقیقتر و سرعت مناسبی نسبت به روش های قبلی دارد.
کلید واژگان: داده کاوی، خوشه بندی ترکیبی، خوشه بندی سلسله مراتبی، خوشه بندی مبتنی بر تراکمElectronics Industries, Volume:9 Issue: 1, 2018, PP 133 -143Clustering is one of the most important field of data mining that aims to divide data into meaningful subsets which are called clusters. This technique involves the process of finding natural groupings in the data set based on the similarities and di similarities which a little or no information about data are available. Over the decades, many clustering algorithms are created in different approaches or a combination of them. In this paper, an algorithm based on density and hierarchical approaches is presented. DBSCAN is one of the algorithms presented in the density-based approach. This algorithm requires two parameters that its determination is a great challenge. In the proposed method, DBSCAN algorithm parameters can be set without user involvement, so that potential clusters are found automatically. The clusters which are so close to each other are merged together until the quality of the final clusters to be enhanced properly. Thus, clusters could be more accurate and high quality. Finally, in order to test the new proposed algorithm, the real dataset in the UCI machine learning repository was used. The results indicate that the new algorithm is more efficient and accurate, and its speed is better than previous methods.
Keywords: data mining, combinational clustering, hierarchical clustering, density-based clustering
- نتایج بر اساس تاریخ انتشار مرتب شدهاند.
- کلیدواژه مورد نظر شما تنها در فیلد کلیدواژگان مقالات جستجو شدهاست. به منظور حذف نتایج غیر مرتبط، جستجو تنها در مقالات مجلاتی انجام شده که با مجله ماخذ هم موضوع هستند.
- در صورتی که میخواهید جستجو را در همه موضوعات و با شرایط دیگر تکرار کنید به صفحه جستجوی پیشرفته مجلات مراجعه کنید.