عنوان

تشخیص پهنای همسایگی تطبیقی کرنل گوسین در خوشه بندی کوانتومی با استفاده از دایره آپولونیوس

پ۲۹۵۲۴

per

تشخیص پهنای همسایگی تطبیقی کرنل گوسین در خوشه بندی کوانتومی با استفاده از دایره آپولونیوس

نسیم عبدالملکی

مهندسی برق وکامپیوتر

۱۴۰۲

۹۳ص.

سی دی

دکتری

مهندسی کامپیوترگرایش شبکه های کامپیوتری

۱۴۰۲/۰۶/۱۹

چکیده: در سال¬های اخیر ایده استفاده از مکانیک کوانتومی در مسائل یادگیری ماشین پیشرفت قابل¬توجهی داشته ¬است. روش¬ خوشه¬بندی کوانتومی (QC) به¬عنوان نوع جدیدی از خوشه¬بندی¬های مدرن توجه بسیاری را به خود جلب کرده ¬است. روش QC بر مبنای تئوری کوانتوم به¬وجود آمده¬ است و از تابع احتمال موج در معادله شرودینگر به¬عنوان یک برهم¬نهی از توابع احتمال گوسین به مرکز نقاط داده برای تخمین توزیع چگالی نقاط داده استفاده می¬کند و پس از تشکیل تابع پتانسیل، خوشه¬ها را با تأکید برکمینه‌های تابع پتانسیل مکان‌یابی می‌کند. کمینه¬های تابع پتانسیل مراکز خوشه و تعداد آن¬ها، تعداد خوشه¬ها می¬باشند. خوشه¬بندی کوانتومی یک روش قدرتمند برای تشخیص خوشه¬ها در داده¬ها با تراکم درهم¬آمیخته است. با این وجود این روش، در داده‌ها با ابعاد بالا دارای پیچیدگی محاسباتی بالایی می¬باشد. همچنین به پارامتر مقیاس (پهنای کرنل) در معادله شرودینگر که شکل کرنل گوسین را کنترل می¬کند و بر تعداد کمینه¬ها در سطح تابع پتانسیل و نتایج نهایی خوشه¬بندی اثر می¬گذارد، بسیار حساس می¬باشد. در این رساله، با در نظر گرفتن چالش¬های مذکور و با الهام از دقت بالای الگوریتم ساخت همسایگی توسط ناحیه آپولونیوس (NCAR) در تشخیص و ساخت همسایگی نقاط مبتنی بر ساختار هندسی دایره¬های آپولونیوس، یک روش خوشه¬بندی کوانتومی مبتنی بر دایره¬ آپولونیوس به نام (ACQC) معرفی می‌شود. روش ACQC با شناسایی نقاط در مناطق پرچگال به¬عنوان نقاط هدف شروع می¬شود. سپس پهنای همسایگی کرنل در معادله شرودینگر با ساخت گروه¬های همسایگی بر مبنای دایره¬های آپولونیوس توسط نقاط هدف بدون نیاز به هیچ دانش قبلی در مورد ساختار داده و خوشه¬ها، به صورت اتوماتیک و تطبیقی بدست می¬آید. همچنین برای افزایش دقت و کارایی روش پیشنهادی درمجموعه¬داده¬ها با ساختارهای پیچیده و نامتعادل، از خوشه¬بندی کوانتومی مبتنی بر دایره¬ آپولونیوس با استفاده از پتانسیل لنارد-جونز (ACQC-LJP) استفاده می¬شود. پتانسیل لنارد-جونز یک نوع پتانسیل جفتی برای اتم¬ها و مولکول¬های ساده است که در روش ACQC-LJP با تمرکزبر غربال¬کردن نقاط هدف مناسب در مناطق پرچگال استفاده می¬شود. بعلاوه برای بهینه-سازی محاسبات، تابع موج بر اساس نقاط ¬داده در گروه همسایگی ساخته¬شده توسط دایره¬های آپولونیوس تخمین ¬زده می¬شود. به¬عبارتی محاسبات مربوط به فرآیند QC به صورت محلی انجام می¬شود. بنابراین، روش¬های پیشنهادی علاوه بر اینکه از ویژگی¬های ذاتی مکانیک کوانتومی بهره ¬می¬برند، پیچیدگی زمانی محاسبات را کاهش ¬داده و همچنین دقت خوشه¬بندی را با تعیین تطبیقی پارامتر مقیاس افزایش می¬دهند.روش¬های پیشنهادی ACQC و ACQC-LJP با تعدادی از روش¬های خوشه¬بندی مانند (QC)، (KECA-QC) و (PQC) مقایسه شده¬اند. این مقایسات بر روی مجموعه¬داده¬های واقعی و مصنوعی انجام¬ شده¬اند. نتایج تجربی بهبود در عملکرد و کارایی محاسبات در روش¬های پیشنهادی ACQC و ACQC-LJP را نسبت به سایر روش¬ها نشان می¬دهند. طوریکه راندمان محاسباتی از نظر زمان اجرا، کاهش % 3/38 و بیش از 90% را به ترتیب برای روش¬های ACQC و ACQC-LJP در مقایسه با روش QC پایه نشان می¬دهند. همچنین نتایج تجربی در روش¬های پیشنهادی ACQC و ACQC-LJP نسبت به روش QC پایه به ترتیب % 17/41 و % 50 بهبود در تشخیص تعداد صحیح خوشه¬ها را نشان می¬دهند.

Abstract :In recent years using quantum mechanics in machine learning problems has made significant progress. The quantum clustering method (QC) has attracted more attention as a new type of modern clustering. The QC method uses the wave probability function in the Schrödinger equation as a superposition of the Gaussian probability functions to the data point centers to estimate the density distribution of the data based on quantum theory. And after forming the potential function, clusters are located by emphasizing the function’s minimums. The minima of the potential function are cluster centers, and their number is the cluster numbers. Quantum clustering is a powerful method to detect clusters in complex datasets. However, this method has high computational complexity in high-dimensional data. It is also significantly sensitive to the scale parameter (kernel bandwidth) in the Schrödinger equation, which controls the shape of the Gaussian kernel and affects the number of minima in the surface of the potential function and the final results of clustering. In this thesis, considering the mentioned challenges and inspired by the high accuracy algorithm of the Neighborhood Construction by Apollonius Region (NCAR) in detecting and constructing neighborhoods of points based on the geometric structure of Apollonius circles, an Apollonius Circle-based Quantum Clustering method is introduced as (ACQC). ACQC method starts by identifying points in dense regions as Target Points. Then, the kernel neighborhood bandwidth in Schrödinger's equation is obtained automatically and adaptively by constructing neighborhood groups based on Apollonius circles with Target Points without any prior knowledge regarding the data structure and clusters. Also, the Apollonius Circle-based Quantum Clustering using Lennard-Jones Potential (ACQC-LJP) is used to increase the accuracy and efficiency in datasets with imbalanced and complex structures. Lennard-Jones potential is a pair potential for simple atoms and molecules, which is used in ACQC-LJP method to identify Target Points in dense regions. In addition, the wave function is estimated based on data points in the neighborhood group constructed by Apollonius circles to optimize calculations. The proposed methods take advantage of the quantum mechanic inherent features and adaptively determine the scale parameter. So these methods reduce the time complexity of calculations and increase the clustering accuracy. The proposed ACQC and ACQC-LJP methods are compared with other clustering methods such as (QC), (KECA-QC), and (PQC). These comparisons are made on real-world and synthetic datasets. Experimental results of the proposed ACQC and ACQC-LJP methods show significant performance improvement compared to state-of-the-art methods. The experimental results of ACQC and ACQC-LJP compared to the original QC method indicate an improvement in calculation efficiency by approximately 38.3% and more than 90% reduction in terms of running time, and a 41.17% and 50% improvement in detecting the correct number of clusters, respectively.

Adaptive Neighborhood Bandwidth Detection of Gaussian Kernel in Quantum Clustering Using the Apollonius Circle

عبدالملکی،‏

‏ نسیم

تهیه کننده

محمدخانلی،‏

هاشم زاده،

پوربهرامی،

‏ لیلی

‏ مهدی

‏ شهین

استاد راهنما

استاد راهنما

استاد مشاور

‏تبریز