سوال خوشه بندی تو کتاب هندسه! :))

ادامه ی تمرین های کتاب فصل درختهای هندسی

جواب:

2D range tree: درخت روی نقاط دو سر بازه ها که مینیمم هر دو برگ مقدار پدرشان است.

یک بعد نقطه ی شروع پاره خط ها است. در بعد دیگر نقطه های پایان این پاره خط ها را نگه می داریم.

جواب:

priority search tree:

تمرین های کتاب (ادامه)

جواب تمرین های خودمون

مروری بر مشخصات درخت ها

segment tree

build: O(nlogn)

storage: O(nlogn)

query: O(logn+k)

----------------------------------

interval tree

build: O(nlogn)

storage O(n)

query: O(logn+k)

----------------------------------

range tree

build: O(nlogn)

storage: O(n)

query: O(logn+k)

تمرین های کتاب - فصل جستجوی بازه ها (درخت های هندسی)

جواب:

الگوریتم:

1- تصویر بازه ها روی محور x را حساب می کنیم و یک درخت بازه روی آن می سازیم. (interval tree)

2- در هر نود درخت بازه ی ساخته شده، یک درخت محدوده (range tree) روی تصویر پاره خطها روی محور y (یک نقطه به ازای هر پاره خط) می سازیم.

3- کوئری را اول روی درخت بازه جواب می دهیم بعد روی درخت محدوده ی آن.

اثبات درستی:

در قدم اول [x,x'] را پیدا می کنیم و در قدم دوم بازه ی y را هم چک می کنیم.

زمان، پیش پردازش، کوئری:

برای درخت بازه ها: تعداد پاره خط ها = تعداد پاره خط های ورودی = n

برای درخت محدوده: تعداد نقاط = تعداد پاره خط های ورودی = n

درختهای هندسی (ادامه)

تفاوت range tree و interval tree در این است که در range tree ما یک سری نقطه داریم و می خواهیم نقاط درون این بازه را به دست بیاوریم، اما در interval tree در درخت بازه ها را نگه می داریم و می خواهیم بازه های شامل نقطه ی داده شده را پیدا کنیم. در پیاده سازی کاری که می کنیم این است که در interval tree یک درخت روی نقاط سر بازه ها می سازیم، اما در range tree روی نقاط درخت می سازیم.

سوال دیگری که مانده بود این بود که ارتباط segment tree و range tree چیست. (دو بعدی)

در segment tree ما از ریشه که به سمت برگها می رویم، در طول مسیر بازه ها را گزارش می کنیم (شکل سمت راست) اما در range tree ما جایی که دو مسیر جدا می شوند زیر درخت های راست سمت چپی و چپ سمت راستی را گزارش می کنیم. (از این نظر فرقی بین range tree و interval tree نیست)

کاربردها و انواع segment tree

1- پیدا کردن بازه های شامل یک نقطه: segment tree معمولی

2- پیدا کردن مساحت مستطیل ها (اجتماع بازه ها): semi static segment tree

3- پیدا کردن پاره خطهای متقاطع با یک پاره خط عمودی: augmented segment tree

(در هر گره یک BST نگهداری می کنیم که ترتیب خطهای عمودی را نگه می دارد. شبیه کاری که در سوئیپ می کردیم)

4- پیدا کردن مستطیل های شامل یک نقطه: multi-level segment tree

 segment tree دو بعدی

Delauney vs. Delaunay

Voronoi Diagrams and Delauney triangulations are data structures to reason about points and regions in space...
... not to be confused with the abstract, Paul Klee like work of Robert Delaunay.

http://www.cse.wustl.edu/~pless/546/

ساخت گراف برای خوشه بندی

linkage measures

بر اساس معیارهای زیر می توانیم گرافهای متفاوتی برای خوشه بندی نقاط بسازیم. اولین چیزی که به ذهن آدم می رسد یک گراف کامل است که فاصله ی هر دو نقطه را وزن یال قرار بدهیم، اما این کار هزینه ی زیادی دارد.

1- کمترین فاصله: فاصله ی هر نقطه از یک خوشه را تا یک نقطه از خوشه ی دیگر مینیمم کند.

به این روش ها نزدیک ترین همسایه می گویند. کلا هر روشی که بر مبنای نزدیک ترین خوشه به یک نقطه عمل کند single linkage است.

در ساخت گراف آن، به این معنی است که بین نزدیک ترین دو نقطه ی دو خوشه (نزدیک ترین خوشه ها) متفاوت یک یال رسم کنیم. (راسهای گراف نقاط هستند). چون همیشه یالها بین خوشه های متفاوت رسم می شوند، گراف ساخته شده یک درخت است. به همین دلیل به این روشها minimal spanning tree هم می گویند.

(هر نقطه به نزدیک ترین مرکز خود وصل است)

(نزدیک بودن محلی)

2- بیشترین فاصله: فاصله ی بین نقاط دو خوشه متمایز را ماکسیمم می کند. (بین هر دو خوشه نه، بین هر خوشه تا نزدیک ترین خوشه ها به آن)

به این روشها دورترین همسایه می گویند. اگر تا جایی ادامه دهیم که فاصله ی دو خوشه از یک حد آستانه مشخص شده توسط کاربر بیشتر شود، به آن اتصال کامل می گویند.

با این روش گرافی که ساخته می شود، هر خوشه آن یک زیرگراف کامل است.

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

(نزدیک بودن سراسری)

** هر دوی روشهای بالا به داده های پرت (که با داده های دیگر فاصله زیاد دارند) و نویز (خطای تصادفی) حساس هستند. به همین دلیل روش های دیگری ارائه شد که بین این دو روش افراطی بودند:

3- فاصله میانگینها: بین میانگین دو خوشه فاصله را مینیمم کنیم.

** این روش مشکل قبل را حل می کند و محاسبه ی آن ساده است، اما برای داده های غیر عددی جواب نمی دهد، در نتیجه ملاک دیگری ارائه شد:

4- میانگین فاصله ی نقاط دو خوشه

1/(n1*n2) * sum (pi, qj)

pi in C1, q in C2

بر خلاف تعریف فاصله ی مرکزها، میانگین را می توانیم برای داده های غیرعددی هم تعریف کنیم. (مثلا مد یا میانه)

**** این روشها برای خوشه بندی سلسله مراتبی هستند.