الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

۸۵ مطلب در دی ۱۳۹۲ ثبت شده است

DBSCAN مخفف density based spatial clustering of applications with noise یعنی خوشه بندی مکانی بر مبنای چگالی در کاربردهای دارای نویز.

زمان الگوریتمش nlogn است اگر با اندیس گذاری مکانی پیاده سازی بشه وگرنه n2. (فکر کنم یعنی اگه بشه تو logn همسایه های یک نقطه رو پیدا کرد.)

الگوریتم:

یک نقطه ی دلخواه انتخاب کن. همه ی نقاطی که در فاصله ی کمی (ورودی الگوریتم) از این نقطه هستند پیدا کن و تعداد آنها را حساب کن.

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

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

این کار را برای همه ی نقطه ها تکرار کن.

OPTICS(Ordering Points to Identify the Clustering Structure) یعنی مرتب کردن نقاط برای تشخیص ساختار خوشه

(پارامترها و زمان اجرا مثل قبلی- مزیت: اشکال وابسته بودن به پارامترهای ورودی رو حل کرده)

هسته: همسایه های یک نقطه که حداقل minpts نقطه دارند که در فاصله ی کمتر از epsilon هستند.

فاصله (دسترسی) هسته p با نقطه q: اگر q هسته نباشد تعریف نشده است. اگر q هسته باشد، اگر p درون همسایگی q باشد شعاع آن همسایگی و در غیر این صورت فاصله ی pq است.

توی مثال شکل سمت چپ فاصله ی هسته رو نشون میده سمت راست فاصله ی هسته ی p تا نقطه های q1 و q2 رو که هر کدوم از اونها هسته اند (فرض کنید minpts که توی شکل ننوشته طوری باشه که اینها هسته بشن مثلا 3) و q1 حالتیه که توی همسایگی اش p افتاده، q2 حالتیه که خارج همسایگی اش افتاده و فاصله ی pq شده.

بیشتر از این توضیح نداده بود ولی فکر کنم اول نقاط رو بر اساس چگالی شون مرتب می کنه بعد همون کار DBSCAN رو میکنه.

DENCLUE: using statistical density function

از توزیع های آماری برای چگالی استفاده می کند. (مثلا توزیع گوسی)

۵ نظر موافقین ۰ مخالفین ۰ ۱۰ دی ۹۲ ، ۱۳:۳۱
سپیده آقاملائی

الگوریتم PAM را روی چند نمونه از داده ها اجرا می کند.

PAM(partition around medoids)

فکر کنم همان الگوریتم local search است. میگه k تا نقطه ی دلخواه را نماینده بگیر، اگر جای نماینده و یک نقطه عادی رو عوض کردی و وضع بهتر شد این کار رو بکن. انقدر ادامه بده که دیگه تغییری نکنه.

CLARANCE(Randomized Clara)

ایده: جستجوی تصادفی

نمونه های تصادفی از همسایه ها می سازد.

معادل اینکه در یک گراف (نقاط=راسها، وزن یالها=فاصله نقاط - فکر کنم!) جستجو کنیم که هر گره می تواند جواب باشد. (نماینده)

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

ROCK(RObust Clustering using linKs)

لینک ها ملاک شباهت و تفاوت اند و فاصله تعریف نمی شود.

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

ملاک شباهت در ROCK: می دانیم ملاکی مثل فاصله جاکارد (تعداد اعضای اشتراک به اجتماع) کار نمی کند. (این الگوریتم مال داده های غیر عددی است. مجموعه در نظر بگیرید.)

ملاک همسایگی: اگر تعداد اعضای اشتراک آنها (با فاصله جاکارد) از یک حد آستانه بیشتر باشد همسایه اند.

ملاک لینک: تعداد همسایه های مشترک دو گره

الگوریتم: ماتریس شباهت را بر اساس ملاک لینک حساب کن.

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

وقتی داده ها زیاد باشند، از آنها نمونه برداری می کند و نمونه ها را خوشه بندی می کند.

*یک اشتباهی که در ترجمه های قبلی کردم این است که Robust رو غلط ترجمه کردم، معنی اش اینه که به خطا و نویز حساس نباشه.

۱ نظر موافقین ۰ مخالفین ۰ ۱۰ دی ۹۲ ، ۱۳:۱۴
سپیده آقاملائی

probabilistic hierarchical clustering

احتمال maximum likelihood مربوط به هر خوشه را حساب می کنیم. اگر دو خوشه را با هم ادغام کردیم و هزینه کمتر شد این کار را انجام می دهیم.

خوشه ها از هم مستقل اند و هزینه را احتمال آنها تعریف می کنیم که می شود ضرب احتمال خوشه ها در هم.

فاصله: منفی لگاریتم احتمال اجتماع خوشه ها تقسیم بر احتمال هر کدام از خوشه ها (در محاسبه ی فاصله ی دو خوشه)

۰ نظر موافقین ۰ مخالفین ۰ ۱۰ دی ۹۲ ، ۱۳:۰۶
سپیده آقاملائی

پیشنهاد می کنم شکل بکشید چون این طوری اصلا نمیشه جواب داد! :)

7-15- روشهای خوشه بندی: شکل خوشه، پارامتر الگوریتم، محدودیت ها

۰ نظر موافقین ۰ مخالفین ۰ ۱۰ دی ۹۲ ، ۰۹:۲۹
سپیده آقاملائی

hold out:

به صورت تصادفی به دو قسمت با اندازه 1/3 برای تخمین دقت و 2/3 برای ساخت مدل تقسیم می شود.
random sampling:
روش hold out را k بار تکرار کنیم و دقت را میانگین دقت دسته بندهای ساخته شده قرار دهیم.
cross validation: (k-fold)
به k زیرمجموعه افراز کنیم. k مرحله به این صورت انجام دهیم که با زیرمجموعه i-ام تست کنیم و با بقیه مدل بسازیم.
leave one out:
روش cross validation که k تعداد نمونه ها باشد. (کاربرد در داده های کم)
stratified cross validation:
روش k-fold که در آن فاصله ی داده ها در هر fold مشابه فاصله ی داده های مجموعه اصلی باشد.
Bootstrap:
به صورت تصادفی با احتمال یکسان و با جایگذاری تعدادی نمونه برای ساخت مدل انتخاب شود و بقیه برای تست باشند. (کاربرد در داده های کم).
.632 Bootstrap
pr(d unique samples) = (1-1/d)^d = 1/e = 0.368
1-0.368=0.632
که در آن d تعداد نمونه های انتخاب شده است. در این صورت دقت به صورت زیر محاسبه می شود:
accuracy(D) = 1/k*sum_i_1_k(accuracy(Ti)*0.368+accuracy(D-Ti)*0.632)
Ti = training set in i-th step (1<=i<=k)
بعد از اینکه با یکی از این روشها مقدار دقت را محاسبه کردیم، باید ببینیم این مقدار چقدر با مقدار واقعی تفاوت دارد. تست های آماری کافی بودن و بازه ی اطمینان برای این کار استفاده می شوند. (به دست آوردن دقت روی مجموعه اصلی از روی دقت نمونه)
می توانیم از توزیع نرمال یا از توزیع t استفاده کنیم.
Null Hypothesis: دسته بندهای M1 و M2 مثل هم عمل می کنند. (باید این فرض را رد کنیم)
مدلی که خطای کمتری دارد انتخاب می کنیم. (مقادیر نمونه را در توزیع می گذاریم و مقادیر دیگر را حساب می کنیم.)
significance level/2= confidence limit
(به دلیل تقارن توزیع)
۸ نظر موافقین ۰ مخالفین ۰ ۱۰ دی ۹۲ ، ۰۹:۰۷
سپیده آقاملائی

فرض کنید با یک روش ارزیابی به نرخ خطایی برای دو دسته بند M1 و M2 رسیده اید. (error rate = 1- accuracy)

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

مثال:

۰ نظر موافقین ۰ مخالفین ۰ ۰۹ دی ۹۲ ، ۱۸:۵۹
سپیده آقاملائی
مثال روشهای ensemble:
bagging, boosting, random forests
ensemble method: روشهایی که در آنها k دسته بند یا مدل یاد گرفته شده با هم ترکیب می شوند تا مدل قوی تری بسازند. دقت مدل ترکیبی از هر کدام از مدلهای اولیه بیشتر است. یکی از روشهای ترکیب دسته بندها رای اکثریت است.
روشهای ensemble:
1- bagging: boostrap aggregation
مرحله آموزش: هر بار d نمونه با جایگذاری بر می داریم و از روی آنها دسته بند می سازیم.
مرحله ی دسته بندی: هر نمونه را به همه ی دسته بندهای ساخته شده می دهیم و ماکزیمم تعداد رای ها را در نظر می گیریم. (رای اکثریت) برای داده های پیوسته میانگین جوابهای دسته بندها.
boosting: میانگین وزن دار جواب مجموعه ای از دسته بندها
adaboost (adaptive boosting)
مرحله آموزش: ابتدا به تاپلها احتمال انتخاب شدن یکنواخت می دهیم و نمونه برداری می کنیم و دسته بند می سازیم. سپس احتمال انتخاب داده هایی که اشتباه دسته بندی شده اند بیشتر می کنیم.
مرحله دسته بندی: وزن جواب هر دسته بند، دقت آن است. میانگین وزن دار جواب دسته بندها را بر می گردانیم.
random forests
دسته بندهایی که می سازد درخت تصمیم هستند. دو نوع دارد:
random input selection: صفتهایی که به عنوان جداکننده انتخاب می شوند رندم انتخاب کند. - درخت با CART ساخته می شود.
random linear combination: صفتهای جدیدی می سازد که ترکیب خطی صفت های قبلی هستند و با این کار همبستگی بین دسته بندها را کاهش می دهد.

۰ نظر موافقین ۰ مخالفین ۰ ۰۹ دی ۹۲ ، ۱۷:۵۶
سپیده آقاملائی
نمودار ROC
این نمودار برای مقایسه ی دو روش دسته بندی به کار می رود. محور عمودی آن TPR (نسبت مثبت های درست) و محور افقی آن FPR (نسبت مثبت های غلط) است.
TPR = TP/P
FPR = FP/N=1-specificity
این نمودار برای دسته بندی دو کلاسه (yes و no) نشان دهنده ی  trade off بین TPR و FPR است.
برای رسم این نمودار برای احتمال یک threshold در نظر می گیریم و بیشتر از آن را yes و کمتر از آن را no می دهیم. (با فرض اینکه روش دسته بندی ما برای هر نمونه یک احتمال تعلق به یک کلاس را برگرداند.)
مثال: در جدول زیر برچسب واقعی و احتمال برگردانده شده توسط دسته بند داده شده است. مقدار t مناسب را بیابید. (با رسم ROC)
برای این مثال از روی مقادیر دو ستون اول بقیه را محاسبه می کنیم. (نمونه ها بر حسب احتمال yes بودن مرتب شده اند.)
برای t=0.90 نمونه ی 1 را در دسته ی مثبت می گذاریم و از روی داده های اصلی می بینیم که درست دسته بندی کرده ایم. یک نقطه روی ROC در (0,0.2) می گذاریم. بعد t را کم می کنیم تا نمونه ی بعدی را شامل شود و همین کار را ادامه می دهیم تا نمودار کامل رسم شود.
نمودار ROC این مثال:
مقایسه ی دو دسته بند بر اساس نمودار ROC آنها
خط y=x در این نمودار نشان دهنده ی احتمال 1/2 برای تعلق به هر کلاس است. (حدس زدن). هر چه نموداری به این خط نزدیک تر باشد دقت آن کمتر است. در مثال زیر M1 از M2 دقیق تر است.

۸ نظر موافقین ۰ مخالفین ۰ ۰۹ دی ۹۲ ، ۱۷:۳۷
سپیده آقاملائی

MS Data Science Track


The increasing importance of big data in engineering and applied sciences motivates ICME and the Department of Statistics to collaborate on a MSc track that trains students in data science with a computational focus.

 

The focused MSc track is developed within the structure of the current MSc program in ICME. Students in the program will develop strong mathematical, statistical, computational, and programming skills through the ICME M.S. requirements and gain a fundamental data science education through 18 units of focused elective courses in the data science and related areas.

 

The program is geared towards two types of students: those with an engineering or applied sciences background who are interested in gaining a better understanding of mathematical and statistical underpinnings of data science; and those who are mathematically- and/or statistically- oriented and are looking to gain expertise in data science and applications.

 

Graduates from this program will be prepared to continue on to a Ph.D. in ICME, Statistics, MS&E, CS or application areas, or work as a data science professional in industry.

 

Degree requirements and details can be found by visiting: Data Science Track (Located at the bottom of the page after Requirement 5 of the Computational Science Track). 

 

Students may apply to the M.S. program directly through ICME and have the option to declare their preference for the Data Science program during the application process or anytime during the first year of their study. Selection of the students is made by the ICME admission committee which will have representation from the Data Science track steering committee.

 

Degree Requirements


The coursework follows the requirements of the traditional ICME M.S. degree with additional restrictions placed on the general and focused electives. As defined in the general Graduate Student Requirements, students have to maintain a grade point average (GPA) of 3.0 or better and classes must be taken at the 200 level or higher. In order to continue on to the Ph.D. in ICME, M.S. students have to maintain a GPA of at least 3.5. The total number of units in the degree is 45.

 

Requirement 1: Foundational (12 Units)

Students must demonstrate foundational knowledge in the field by completing the following core courses. Courses in this area must be taken for letter grades. Deviations from the core curriculum must be justified in writing and approved by the student’s ICME adviser and the chair of the ICME curriculum committee. Courses that are waived may not be counted towards the master’s degree.


THE FOLLOWING COURSES ARE REQUIRED: UNITS

CME 302 Numerical Linear Algebra 3

CME 304 Numerical Optimization 3

CME 305 Discrete Mathematics and Algorithms 3

CME 308 Stochastic Methods in Engineering (or an equivalent course approved by the committee) 3

Total Units


12

Requirement 2: Data Science Electives (12 Units)

Data Science electives should demonstrate breadth of knowledge in the technical area. The elective course list is defined. Courses outside this list can be accepted as electives subject to approval. Petitions for approval should be submitted to student services.


TAKE 12 UNITS OF THE FOLLOWING: UNITS

STATS 200 Introduction to Statistical Inference 3

STATS 203 Introduction to Regression Models and Analysis of Variance 3

STATS 305 Introduction to Statistical Modeling 3

STATS 315A Modern Applied Statistics: Learning 2-3

STATS 315B Modern Applied Statistics: Data Mining 2-3

Requirement 3: Specialized Electives (9 Units)

Choose three courses in specialized areas from the following list. Courses outside this list can be accepted as electives subject to approval. Petitions for approval should be submitted to student services.


TAKE THREE OF THE FOLLOWING: UNITS

BIOE 214 Representations and Algorithms for Computational Molecular Biology 3-4

BIOMEDIN 215 Data Driven Medicine 3

BIOS 221 Modern Statistics for Modern Biology 3

CS 224W Social and Information Network Analysis 3-4

CS 347 Parallel and Distributed Data Mining 3

CS 448 Topics in Computer Graphics 3-4

ENERGY 240 Geostatistics 2-3

OIT 367 Analytics from Big Data 4

PSYCH 240A Human Neuroimaging Methods 3

PSYCH 303 Human and Machine Hearing 3

STATS 290 Paradigms for Computing with Data 3

STATS 366 Modern Statistics for Modern Biology 3

Requirement 4: Advanced Scientific Programming and High Performance Computing Core (6 Units)

To ensure that students have a strong foundation in programming students are required to take 6 units of advanced programming, with at least 3 units in parallel computing. Approved courses for advanced scientific programming include:


ADVANCED SCIENTIFIC PROGRAMMING; TAKE 3 UNITS UNITS

CME 212 Advanced Programming for Scientists and Engineers 3

CME 214 Software Design in Modern Fortran for Scientists and Engineers 3

CS 107 Computer Organization and Systems 3-5

CS 249B Large-scale Software Development 3

PARALLEL/HPC COMPUTING; TAKE AT LEAST 3 UNITS UNITS

CME 213 Introduction to parallel Computing using MPI, openMP, and CUDA 3

CME 342 Parallel Methods in Numerical Analysis 3

CS 149 Parallel Computing 3-4

CS 315A Parallel Computer Architecture and Programming 3

CS 315B Parallel Computing Research Project 3

CS 316 Advanced Multi-Core Systems 3

CS 344C, offered in previous years, may also be counted


3

For DS students, the 1-unit course in MapReduce offered by ICME annually is also highly recommended. Courses outside this list can be accepted as electives subject to approval. Petitions for approval should be submitted to student Services.


Requirement 5: Practical Component (6 Units)

Students are required to take 6 units of practical components that may include and combination of:


A capstone project supervised by a faculty member and approved by the steering committee. The capstone project should be computational in nature. Students should submit a one-page proposal, supported by the faculty member, to the steering committee (gwalther@stanford.edu) for approval.


Clinics, such as the new Data Science Clinic offered by ICME starting Winter 2013.


Other courses that have a strong hands-on and practical component, such as STATS 390 Consulting Workshop.

۰ نظر موافقین ۰ مخالفین ۰ ۰۹ دی ۹۲ ، ۰۹:۲۶
سپیده آقاملائی

مرجع: تمرین های http://www.cs.uu.nl/docs/vakken/ga

تمرین 1:

1- مجموعه ای از n پاره خط مجزا و m دایره ی غیر متقاطع (می توانند متداخل باشند) داده شده است. همه ی دایره هایی که هیچ پاره خطی را قطع نمی کنند گزارش دهید. (راهنمایی: sweep)

هر دایره را به 2 قسمت بالا و پایین تقسیم می کنیم. بعد می توانیم مثل پاره خط در نظر بگیریم، چون در sweep فقط این مهم است که نسبت به قبل جای آنها جا به جا شده باشد. بقیه اش مثل قبل است.

تمرین 1: (شانس دوم!)

1- الف) چندضلعی ساده ی P داده شده است که تنها یک راس turn دارد (merge,split,start,end). یک الگوریتم O(n) ارائه دهید که آن را مثلث بندی کند.

(برای تعریف راس turn به sweep مربوط به مثلث بندی که در پست های قبلی موجود است نگاه کنید.)

ب) ثابت کنید که هر چندضلعی ساده که O(1) راس مقعر داشته باشد، O(1) راس turn دارد.


۰ نظر موافقین ۰ مخالفین ۰ ۰۹ دی ۹۲ ، ۰۸:۵۶
سپیده آقاملائی