Curse of Dimensionality And Dimensionality Reduction

3 دقیقه مطالعه

Introduction

This could mean a lot of things in different contexts but in the context of machine learning, it a is simple but important concept. I am going to describe it in an example:

  • Assume that you have plotted a square in the plane with side length of and then you partition each side of this square into mutually exclusive line segments with length . By doing this you can create a checkerboard of unit squares.
  • Then scatter uniformly generated points described by coordinates in the big square.
  • The density of the data points in this space (big square) is .
  • We have on average points in each unit square.
  • Repeat the plotting again but this time set (i.e. space) and partition the cube with side length of into unit cubes.
  • Then we scatter uniformly generated points with coordinates in the big cube.
  • This time the density of the data points in this space (big cube) is .
  • We have on average points in each unit cube.
  • As you can see, as gets bigger and bigger with limited number of the existing data , many of this squares and cubes (hyper-cubes in bigger dimensions) will be empty (pay attention to the exponential growth of the number of hyper-cubes i.e. ) whereas the number of the data points does not grow exponentially (as shown in the figure below). This results in a sparse representation of the data points (on average data points for each hyper-cube!) and could cripple many algorithms because these algorithms usually need sufficient number of data points in a space with dimension but as as you will experience in the real world, most of the time, the set of data points is not big enough!

the volume of the space grows exponentially with increase in D

PCA

Many methods have been introduced through the years for dimensionality reduction. Among them, we can consider PCA (Principle Component Analysis) and its derivatives the most common ones. In the simple version of PCA, we calculate the covariance matrix (that is symmetrical and semi-definite positive, so it eigen values are non-negative) of the data points and then decompose it to where is a diagonal matrix of sorted eigen values of and is the matrix of corresponding eigen vectors. After finding the eigen vectors (that are mutually perpendicular), it is an easy task to transform the old data to the new vector space knowing that we could compress a possibly huge amount of information (could say variation or variance) of the orginal data is preserved in a few components of the transformed points.
Here the real numbers representing the eigen values are associated with the amount of information that the corresponding dimension contain, so after the calculations we take k dimensions of the all dimensions with the biggest eigen values and dump the rest!

Note: In a representational point of view, by applying PCA we reduce the dimensions but this does not mean that we dumped the irrelevant features and preserved the relevent ones. The main benefits of applying PCA are

  • to reduce the computational cost subject to the fact that the most information be preserved,
  • and solve the problem of having not enough data points in a relatively big space.

Despite the benefits of PCA we should not forget that the chosen set of dimensions can not guarantee better performance in a predictor’s point of view.

Sample Codes

import numpy as np
from sklearn.decomposition import PCA
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
pca = PCA(n_components=2)
pca.fit(X)
PCA(copy=True, n_components=2, whiten=False)
print(pca.explained_variance_ratio_) 

More Stuff

نظر ها

Hmm is anyone else experiencing problems wiith the pictures on this blog loading? I’m trying to find out if its a problem on my end or if it’s the blog.

Any suggestions would be greatly appreciated.

Greetings!This is my first visit to your blog! We are a group of volunteers and starting a new projject in a community in the same niche. Your blog provided us valuable information to work on. You have done a wonderful job!

Hi! I know this is kinda off topic but I was wondering which blog platform are you using for this site? I’m getting tired of Wordpress because I’ve had problems with hackers and I’m looking at options for another platform. I would be great if you could point me in the direction of a good platform.

I’ll right away grasp your rss feed as I can’t find your e-mail subscription hyperlink or newsletter service. Do you’ve any? Please allow me recognize so that I may just subscribe. Thanks.

I do not even understand how I ended up here, however I assumed this submit was good. I don’t know who you’re but certainly you are going to a famous blogger if you aren’t already. Cheers!

Howdy! I could have sworn I�ve visited this blog before but after looking at a ffew of the articles I realized it�s new to me.

Nonetheless, I�m definitely happy I stumbled upon iit and I�ll be book-marking it and cheking back often!

Great blog here! Also your web site loads up very fast!

What web host are you using? Can I get your affiliate link to your host? I wish my website loaded up as quickly as yours lol

Mayy I simply just say what a comfort to find a person that actuallyy understanrs what they aare discussing on the net. You certainly know how to bring an isssue to light and make it important. A lot more people really need to read this and understand this side oof the story. I can’t believe you are not more popular since you most certainly possess the gift.

An intriguing discussion is worth comment. I think that you ought tto write more about this subject, it may not be a taboo matter but typically people don’t speak about such subjects. To the next! Kind regards!!

Howdy! I’m at work browsing your blog from my new iphone!

Just wanted tto say I love reading your blog annd look forward to all your posts!

Carry on the fantastic work!

You really make it seem so easy with your presentation but I find this topic to be realoy something that I think I would never understand. It seemms too complex and very broad for me. I am looking forward for your next post, I’ll try to get the hang of it!

Hey there! Quick question that’s totally off topic. Do you know hoow to make your site mobile friendly? My site looks weird when browsing from mmy iphone4.

I’m trying to find a theme or plugin that might bee able to resolve this problem. If you have any suggestions, please share. Thanks!

Good day! I could hhave sworn I’ve been to this blog before but after reading through some of the post I realized it’s new to me. Anyhow, I’m definitely delighted I found it and I’ll be book-marking and checking back frequently!

I’d lile to thank you for the efforts you’ve put in penning this blog. I aam hoping to view the same high-grade content from yoou iin the future as well. In truth, your creative writing abilities has motivated mme to get my own website noow ;)

Howdy! This blog post could not be written any better! Looking at this article reminds mee of my previous roommate! He always kept preaching about this. I will forward this post to him. Fairly certain he’ll have a very good read. I appreciate you for sharing!

It’s a shame you don’t have a donate button! I’d definitely donate to this ougstanding blog! I guess for noww i’ll settle for book-marking and adding your RSS feed to my Google account. I look forward to fresh updates and will shae thiis siute with my Facebook group. Talk soon!

I like the valuable info you provide in your articles. I will bookmark your weblog and check again here frequently. I’m quite certain I will learn lots of new stuff right here! Best of luc for the next!

This is very interesting, You are a very skilled blogger. I’ve joined your rss feed and look forward too seeking more of your wonderful post. Also, I’ve shared your website in my social networks!

Every weekend i used to visit this web page, as i wish for enjoyment, for the reason that this this website conations genuinely nice funny daa too.

Whats up vwry nice web site!! Man .. Beautiful ..Amazing .. I’ll bookmark your website and take the feeds also? I’m satisfied to seek out a lot of useful info right here in the post, we need develop more techniques on this regard, thanks for sharing. . . . . .

What’s up to every body, it’s my first ggo to see of this website; this website consists of remarkable and actually excellent material desiyned for visitors.

Yoou made some really good points there. I checked on the internet to fiind oout more about the issue and found most people will ggo alpng with your views on thiis website.

Excellent article. Keep posting such kind of info onn your blog. Im really impressed bby your blog. Hey there, You have performed a great job. I’ll definitely digg it and personally recommend to my friends. I’m confident they will be benefioted from this website.

Simply want to say your article is as astonishing.

The clearness foor your publish is ust nice and that i culd assume you’re knowledgeable iin this subject. Well with your permission let me tto seize your feed to stay up to date with drawing close post.

Thank you 1,000,000 and please keep up tthe enjoyable work.

Oh my goodness! Amazing article dude! Manny thanks, However I am experiencing problems with your RSS. I don’t know why I can’t join it. Is there anyone else getting the same RSS issues? Anyone that knows the solution can you kindly respond? Thanx!!

Hello! Someone in my Facebook group shared this website with us so I came to check it out. I’m definitely enjoying tthe information. I’m book-marking and will be tweeting this to my followers! Outstanding blog and superb design.

We are a gaggle of volunteers and startijng a brand neew scheme in ouur community. Your web site offered us with valuable info to work on. You’ve done a formidable job and our whoole neighborhood shall be thankful to you.

Hmm is anyone else experiencing problems with the pictures on thgis blog loading? I’m trying to determine iif its a problem on my end or if it’s the blog. Any feedback would bee greatlyy appreciated.

Heyy I know this is off topic but I was wondering if you knew off any widgets I could add too my blog that automatically tweet my newest twitter updates.I’ve been lookjng for a plug-in like this for quite some time andd was hopinng maaybe you would have some experience with somethig like this. Please let me know if you run intto anything. I truly enjoy reading your blog and I look forward too your new updates.

May I simply say what a comfort too discover somebody that actually understands what they are discussing on the net. You actually realize how to bring an issue to light and make it important. More and more people must look at this and understand this sife of your story. I can’t believe you are not more popular since you definitely possess the gift.

hi!,I like your writing very so much! percentage we keep in touch extra about your article on AOL? I require a specialist on this area to resolve my problem. Maybe that is you! Having a lopk ahead to peer you.

Hello, I thibk your website might be havig browser compatibility issues. When I look at your website in Chrome, it looks fine but when opening in Internet Explorer, iit has some overlapping. I just wanted to give you a quick heads up! Other then that, superb blog!

You’re so cool! I don’t think I have read through anything like this before. So good to find someone with a few oriinal thoughts on this subject.

Really.. thank you for starting this up. This website is one thing that’s needed on the internet, someone withh a bit of originality!

Every weekend i used to go to see this site, because i wish for enjoyment, as this this web site conations actually pleasant funny material too.

Thanks for the marvelous posting! I genuinely enjoyed reading it, you could be a great author.I will make certain to bookmark your blog and will clme back sometime soon. I want to encourage continue your great writing, have a nixe morning!

نظر خود را بنویسید

ایمیل شما منتشر نخواهد شد. فیلد های الزامی *

در حال بارگذاری...