Skip to main content
SUPERVISOR
Reyhaneh Rikhtegaran,Ghahreman Taherian
ریحانه ریخته گران (استاد مشاور) سیدقهرمان طاهریان (استاد راهنما)
 
STUDENT
Babak Tahmasebi
بابک طهماسبی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1392

TITLE

Linear manifold clustering in high dimensional spaces by stochastic search
The subject of clustering can be defined as the partitioning of a set of points in a multidimensional space into groups called clusters such that the points in each group are in some sense similar to one another . Finding these clusters is important because their points correspond to observations of different A kind of latent information that may be of interest are correlations in a data set . A correlation is a linear dependency between two or more features (attributes) of the data set . Amongst the dataset , there are points that have a kind of correlation; such as the points of a line or a plan . In this thesis we have tried to cluster a group of data based on a special kind . In this new approach , the points on a linear manifold situate into a cluster . Knowing about the existence of a relationship between features may enable us to learn hidden causalities . In this thesis we have tried to cluster a group of data based on a special kind . In this new approach , the points on a linear manifold situate into a cluster . Consider K as the maximum dimension for clusters to include . For k=1,..,K , we select a set of k+1 points from the whole dataset in a way that construct a set of k linearly independent vectors . Then , using the Gram–Schmidt process , we deduce an orthonormal basis for a k-dimensional manifold . Then we calculate the distances of the rest of points in the dataset from the center of this manifold , and make the distance histogram for the dataset . In the next step , we employ Kittler-Illingworth's method to find a minimum error threshold in the histogram . The points of the dataset are separated according to this threshold and the points with distances less than it are put into the k-dimension cluster . If this separation is good enough , the above procedure is repeated for this cluster with k=k+1 to find higher dimensional clusters , if any , until we cannot find any more clusters . Therefore in addition to construct new clusters , we can find clusters that exist in previous clusters . The process is restarted for the rest of the dataset with k=1 . Finally outliers are clustered in a single cluster , which clearly does form a manifold .
در الگوریتم‌های خوشه‌بندی کلاسیک مرکز خوشه یک نقطه‌ی منفرد در نظر گرفته می‌شود. خوشه‌هایی که حول یک نقطه‌ی منفرد متمرکز نیستند، انتخاب مناسبی برای رهیافت خوشه‌بندی کلاسیک محسوب نمی‌شوند. در این پایان‌نامه روش جدید خوشه‌بندی مطرح می‌شود که در آن مرکز خوشه به جای یک نقطه یک منیفلد خطی است. در این رهیافت، خوشه‌ها گروه‌هایی از نقاط هستند که حول یک منیفلد خطی متمرکز هستند. یک منیفلد خطی با بعد صفر یک نقطه است؛ بنابراین خوشه‌بندی حول یک نقطه حالت خاصی از خوشه‌بندی منیفلد خطی است. خوشه‌بندی منیفلد خطی ( LMCLUS) زیرمجموعه‌هایی از داده‌ها را یکسان در نظر می‌گیرد که در منیفلدهای خطی دلخواه جهت‌دار با ابعاد کمتر قرار می‌گیرند. در این روش زیرمجموعه‌های مینیمال نقاط، مکرراً در منیفلدهای خطی آزمایشی با ابعاد مختلف دسته‌بندی و هیستوگرام‌های فواصل نقاط برای هر منیفلد آزمایشی محاسبه می‌شوند. سپس نمونه‌گیری متناظر با هیستوگرامی که دارای بهترین تفکیک بین یک حالت نزدیک صفر با دیگر موارد است انتخاب شده و نقاط بر پایه‌ی بهترین تفکیک افراز می‌شوند. نمونه‌گیری تکراری به‌طور بازگشتی روی هر بلوک از داده‌های افراز شده ادامه پیدا می‌کند. یک ارزیابی گسترده از 100 آزمایش روی مجموعه داده‌های ساختگی و واقعی مزیت کلی این الگوریتم را نسبت به الگوریتم‌های رقیب برحسب دقت و زمان محاسبه نشان می‌دهد. زمان مورد انتظار مضربی از بعد مجموعه داده‌ها و اندازه‌ی مجموعه داده‌ها است. دقت این روش نزدیک 0/9 تا 0/99 بسته به آزمایش گسترده است و به‌طور کلی خیلی بیش از دقت الگوریتم‌های رقیب است.

ارتقاء امنیت وب با وف بومی