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!

It’s in point of fact a great and useful piece of information. I’m happy that you just shared this useful info with us.

Please sgay us informed like this. Thank you for sharing.

Great beat ! I would lke to apprentice whilst you amend your web site, how can i subscribe for a weblog website? The account aided me a applicable deal. I had been a little bitt acquainted of this your broadcast offered shiny transparent idea

With havin so much content and articles do you ever run into any problems of plagorism or copyright violation? My site has a lot of exclusive content I’ve either written myself or outsourced but it looks like a lot of it is popping it up all over the web without my authorization. Do you know any techniques to help stop content from being ripped off? I’d definitely appreciate it.

Wow, superb blog layout! How long have you been blogging for?

yoou mzke blogging look easy. The overalll liok of your website is magnificent, as well as the content!

Everything is very open with a really clear description of the challenges. It was definitely informative. Your website is useful. Many thanks for sharing!

Helko this is somewhat of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding experience so I wanted to get adsvice from someone with experience. Any help would be greatly appreciated!

Riցht nnow it sounds ⅼike Movable Type is thhe bеst bloggving platform ߋut thеre rigһt now.

(from what Ι’ve read) Iѕ that ԝhat yοu’re using on yoսr blog?

You’ve made some really good points there. I checked on the web for more info about the issue and found most individuals will go along with your views on this web site.

I was curious if you ever thought of changing the structure of your website? Its very well written; I love whast youve got to say. But maybe you could a little more in the wayy of content so people could connectt with it better. Youve got an awful lot of text for only having 1 or 2 images. Maybe you could space it out better?

Unquestionably believe that which yoս stated. Yߋur favourite justification appeared t᧐ ƅе on the internet tһe simplest tһing to have in mind of. I say to yoᥙ, I ceгtainly get annoyed whilst оther people consіder worries tһat they plainly do not understand about. You controlled tо hit the nail upon the hіghest and also defined out tһе whоle thing with no need siԁe effect , folks could tаke a signal. Will probably Ьe again to gеt mοre. Thank you

Hmm it seems like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I submitted and say, I’m thoroughly enjoying your blog. I as well am an aspiring blog blogger but I’m still new to everything. Do you have any recommendations for inexperienced blog writers?

I’d really appreciate it.

I am really loving the theme/design of your blog. Do you ever run into any internet browser compatibility issues?

A small number of my blog readers have complained about my blog not working correctly in Explorer but looks great in Chrome. Do you have any recommendations to hdlp fix this problem?

I was curious if yyou ever thought of changing the structure of your website? Its very well written; I love what youve got to say. But maybe yoou could a little more in the way of content so people could connect with it better. Youve got an awfuhl lot of text for only having one or two pictures. Maybe you could space it out better?

I feel that is among thee most significant info foor me. And i’m happy studying yoyr article. But want to statement onn some normal things, The web site taste is ideal, the articles is in point of fact nice : D. Good activity, cheers

I’ve been exploring for a little bit for any high-quality articles or blog posts in this sort of area . Exploring in Yahoo I finally stumbled upon this site. Studying this information So i am satisfied to show that I have a very just right uncanny feeling I came upon just what I needed. I such a lot for sure will make certain to do not put out of your mind this site and give it a glance regularly.

Helo very nice blog!! Man .. Excellent .. Superb .. I’ll bookmark your website and take the feeds also? I amm saatisfied to seek out a lot of helpful information right here in the put up, we need work out extr techniques on this regard, thank youu for sharing. . . . . .

My partner and I stunbled over here coming from a different website and thought I might check things out. I like what I see so now i am foollowing you. Lookk forward too going over yoiur web page repeatedly.

I used to be recommended this website by my cousin. I’m now not sure whether or not this put up is written by means of him as nobody else know such targeted approximately my trouble. You’re incredible! Thank you!

Heyy I now this is off topic but I was wondering if you knerw of any widgets I could add to my blokg that automatically tweet my newest twitter updates. I’ve been looking for a plug-in lik this for quite some time and was hoping maybe you would have some experience with something like this. Please let mme knoow if you run into anything. I truly enjoy reading your blokg aand I llok forward to your new updates.

Hey there! I know this is kinda off topic nevertheless I’d figbured I’d ask. Wouild you be interested in exchanging links or maybe guest authoring a blog article oor vice-versa? My blog coveres a lot of the ssame subjects as yours andd I belive we could greatly benefit from each other. If you’re interested feel frree to send me an email. I loook forward too hearing from you! Excellewnt blog by the way!

Wow, fantastic blog layout! How long have you been blogging for?

you mafe blogging lopok easy. The overall look of your site is great, let alone the content!

Thanks for another informative site. Where else may just I get that kind of information written in such an ideal method? I’ve a mission that I’m simply now working on, and I have been at the look out for such information.

Wonderful goods from you, man. I have remember your stuff previous to and you’re just too wonderful. I really like what you have received here, certainly like what you are stating and the way during which you say it. You’re making it entertaining and you continue to take care of to keep it sensible. I cant wait to read far more from you. This is really a tremendous site.

Hi there! Would you mind if I share your blog with my zynga group? There’s a lot of folks that I think would really enjoy your content. Please let me know. Cheers

Hi there all, here every one is sharing such familiarity, so it’s pleasant to read this web site, and I used to visit this blog every day.

This post offers clear idea designed for the new viewers of blogging, that in fact how to do blogging and site-building.

Hi! I know this is kinda off topic but I’d figured I’d ask. Would you be interested in trading links or maybe guest authoring a blog post or vice-versa? My website goes over a lot of the same topics as yours and I believe we could greatly benefit from each other. If you are interested feel free to shoot me an e-mail.

I look forward to hearing from you! Superb blog by the way!

Ӏ am гeally loving thee theme/design ᧐f у᧐ur website. Ⅾo yyou еver run іnto any internet brrowser compatibility рroblems?

A number of my blopg visitoors have complained ɑbout my website not operating correctly іn Explorer but looks ցreat in Opera. Do youu һave any advice to hеlp fix thіs prоblem?

Αn intriguing discussion is worth сomment. Ӏ think tһat you shοuld publish mօre ɑbout tis issue, іt may nott ƅe а taboo matter but uѕually people do not speak aƄout tһese topics. To tһe next! Aⅼl the bеѕt!!

Heya i’m for thhe first time here. I cme across this bpard and I tto find It really helpful & it helped me out much. I hokpe tto give one thing back annd help others like you aided me.

Ꮋi! I coulԁ have sworn I’vе visited tһis web site ƅefore Ƅut after ⅼooking at many of thе posts I realized іt’s new to me. Ꮢegardless, I’m ɗefinitely pleased I discovered іt and I’ll Ƅe book-marking itt аnd checking bаck frequently!

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

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

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