{"id":113,"date":"2011-02-08T11:24:44","date_gmt":"2011-02-08T19:24:44","guid":{"rendered":"http:\/\/zhanxw.com\/blog\/?p=113"},"modified":"2011-02-10T09:19:01","modified_gmt":"2011-02-10T17:19:01","slug":"laplacian-eigenmap-%e7%9a%84r-code-%e5%92%8c%e7%bb%93%e6%9e%9c","status":"publish","type":"post","link":"https:\/\/zhanxw.com\/blog\/2011\/02\/laplacian-eigenmap-%e7%9a%84r-code-%e5%92%8c%e7%bb%93%e6%9e%9c\/","title":{"rendered":"Laplacian Eigenmap \u7684R code \u548c\u7ed3\u679c"},"content":{"rendered":"

\u5229\u7528\u77e9\u9635\u7684\u5206\u89e3\u548c\u5206\u6790\u56fe\u662f\u4e2a\u5f88\u6709\u610f\u601d\u7684\u8bdd\u9898\u3002\u5f53\u6211\u4eec\u80fd\u7528\u8fd9\u4e2a\u6280\u672f\u6765\u6539\u8fdbPCA\u7684\u65f6\u5019\uff0c\u6216\u8005\u964d\u7ef4\u7684\u65f6\u5019\uff0c\u6211\u4eec\u6709\u53ef\u80fd\u76f8\u4fe1\u6709\u610f\u601d\u7684\u7ed3\u679c\u4f1a\u8e66\u51fa\u6765\u3002\u8fd9\u91cc\u4e3b\u8981\u53c2\u8003\u4e86\u6587\u732e\u30101\u3011\u548cPluskid\u7684blog\u30102\u3011\u3002\u5176\u4e2d\u30101\u3011\u7ed9\u51fa\u4e86\u63a8\u5bfc\u8fc7\u7a0b\uff1a\u76ee\u6807\u51fd\u6570\u662f\u4e8c\u6b21\u578b\u7684\u77e9\u9635\uff0c\u7ea6\u675f\u540c\u6837\u662f\u4e8c\u6b21\u578b\u7684\uff1b\u8fd8\u6709\u8be6\u7ec6\u7684Algorithm\uff1a\u91cc\u9762\u6700\u5173\u952e\u7684\u4e00\u6b65\u662fGeneralized eigenvector problem\uff08wiki\u6709\u975e\u5e38\u7b80\u77ed\u7684\u4ecb\u7ecd\uff09\uff0c\u7406\u8bba\u4e0a\u53ef\u4ee5\u7528Golub Matrix Computation Chapter 8 \u7684\u65b9\u6cd5\uff08\u6211\u6ca1\u8bfb\uff0c\u5dee\u4e0d\u591a\u5fd8\u4e86Numerial Method\u8bfe\u7684\u77e5\u8bc6\u4e86\uff09\uff0c\u4f46\u6211\u5e76\u6ca1\u6709\u4f7f\u7528\u3002\u53e6\u5916\u30102\u3011\u91cc\u7684\u6587\u5b57\u6d41\u7545\uff0c\u8a00\u7b80\u610f\u8d45\uff0c\u662f\u5165\u95e8\u7684\u597d\u6587\u7ae0\u3002<\/p>\n

\u7b80\u5355\u6765\u8bb2\uff0c\u5f53\u5229\u7528k-neighbor \u6216[latex] \\epsilon [\/latex]\u65b9\u6cd5\u6784\u9020\u4e34\u8857\u77e9\u9635\uff0c\u5229\u7528Simpled minded\uff080 or 1\uff09\u6216\u8005Heat Kernel\u6765\u6784\u5efaWeight\u77e9\u9635\u540e\uff0c\u6211\u4eec\u7684\u95ee\u9898\u662f\u6c42\u89e3\uff1a<\/p>\n

$$ L f = \\lambda D f \\quad st. \\quad f^T D f = 1 \\quad \\mathrm{and} \\quad f^T D \\mathbf{1} = 0 $$<\/p>\n

\u6211\u4eec\u5df2\u7ecf\u77e5\u9053D\u662f\u4e00\u4e2a\u5bf9\u89d2\u9635\uff0c\u6240\u4ee5\u6c42\u89e3$$ D^{-1} L f = \\lambda f $$\u5373\u53ef\u3002<\/p>\n

\u8003\u8651\u5230\u7ea6\u675f\u6761\u4ef6\uff0c\u6211\u4eec\u53ea\u9700\u5bf9\u6bcf\u4e00\u4e2a[latex]f[\\latex]\u505a\u5982\u4e0b\u53d8\u6362\uff1a<\/p>\n

$$ f^T D f = 1 \\Rightarrow f = f \/ \\sqrt{\\sum_i f_i^2 d_i} $$<\/p>\n

$$ f^T D \\mathbf{1} = 0 \\Rightarrow f = f – \\frac{ \\sum_i f_i d_i } { \\sum_i d_i} $$<\/p>\n

R code<\/strong><\/p>\n

LaplacianEigenmap.R Link<\/a><\/p>\n

LaplacianEigenmapTest.R Link<\/a><\/p>\n

\u7ed3\u679c\uff1a<\/strong><\/p>\n

\"\"<\/a><\/p>\n

\u4ece [latex] 0 = \\lambda_0 \\le \\lambda_1 \\le \\lambda_2 \\ldots \\lambda_n [\/latex] \u4e2d\u53d6\u6700\u5c0f\u7684\u4e24\u4e2a\u975e\u96f6\u7684\u7279\u5f81\u6839[latex] \\lambda_1\\, \\lambda_2 [\/latex]\u5bf9\u5e94\u7684\u7279\u5f81\u5411\u91cf\uff0c\u4eff\u7167paper\uff0c\u5f97\u5230\u7ed3\u679c\u5982\u4e0b\uff1a<\/p>\n

\u6ce8\u610f\uff0c\u8fd9\u91cc\u7684\u56fe\u6848\u548cpaper\u4e0d\u7b26\uff0c\u4f46\u6211\u7684\u9a8c\u7b97\uff0c\u68c0\u67e5\u662f\u5426\u662f\u7279\u5f81\u503c\u3001\u7ea6\u675f\u6761\u4ef6\uff0c\u8868\u660e\u6211\u7684\u8ba1\u7b97\u8fc7\u7a0b\u5e94\u8be5\u662f\u6b63\u786e\u7684\u3002<\/p>\n

\u53e6\u5916Pluskid \u7684Blog\u4e0a\u7684\u56fe\u6848\u4e2d\uff0cLaplacian Eigenmap\u7684\u7ed3\u679c\u662f\u4e00\u4e2a\u5f69\u5e26\uff0c \u6211\u8ba4\u4e3a\u6709\u53ef\u80fd\u662f\u4f7f\u7528\u4e86[latex] \\lambda_0, \\lambda_1 [\/latex]\u5bf9\u5e94\u7684\u7279\u5f81\u5411\u91cf\u3002<\/p>\n

\u53c2\u8003\uff1a<\/strong><\/p>\n

\u30101\u3011Mikhail Belkin and Partha Niyogi, \u201cLaplacian Eigenmaps for Dimensionality Reduction and Data Representation,\u201d Neural Computation 15, no. 6 (February 6, 2011): 1373-1396.<\/p>\n

\u30102\u3011\u6f2b\u8c08 Clustering (\u756a\u5916\u7bc7): Dimensionality Reduction\u00a0http:\/\/blog.pluskid.org\/?p=290<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

\u5229\u7528\u77e9\u9635\u7684\u5206\u89e3\u548c\u5206\u6790\u56fe\u662f\u4e2a\u5f88\u6709\u610f\u601d\u7684\u8bdd\u9898\u3002\u5f53\u6211\u4eec\u80fd\u7528\u8fd9\u4e2a\u6280\u672f\u6765\u6539\u8fdbPCA\u7684\u65f6\u5019\uff0c\u6216\u8005\u964d\u7ef4\u7684\u65f6\u5019\uff0c\u6211\u4eec\u6709\u53ef\u80fd\u76f8\u4fe1\u6709\u610f\u601d\u7684\u7ed3\u679c\u4f1a\u8e66\u51fa\u6765\u3002\u8fd9\u91cc\u4e3b\u8981\u53c2\u8003\u4e86\u6587\u732e\u30101\u3011\u548cPluskid\u7684blog\u30102\u3011\u3002\u5176\u4e2d\u30101\u3011\u7ed9\u51fa\u4e86\u63a8\u5bfc\u8fc7\u7a0b\uff1a\u76ee\u6807\u51fd\u6570\u662f\u4e8c\u6b21\u578b\u7684\u77e9\u9635\uff0c\u7ea6\u675f\u540c\u6837\u662f\u4e8c\u6b21\u578b\u7684\uff1b\u8fd8\u6709\u8be6\u7ec6\u7684Algorithm\uff1a\u91cc\u9762\u6700\u5173\u952e\u7684\u4e00\u6b65\u662fGeneralized eigenvector problem\uff08wiki\u6709\u975e\u5e38\u7b80\u77ed\u7684\u4ecb\u7ecd\uff09\uff0c\u7406\u8bba\u4e0a\u53ef\u4ee5\u7528Golub Matrix Computation Chapter 8 \u7684\u65b9\u6cd5\uff08\u6211\u6ca1\u8bfb\uff0c\u5dee\u4e0d\u591a\u5fd8\u4e86Numerial Method\u8bfe\u7684\u77e5\u8bc6\u4e86\uff09\uff0c\u4f46\u6211\u5e76\u6ca1\u6709\u4f7f\u7528\u3002\u53e6\u5916\u30102\u3011\u91cc\u7684\u6587\u5b57\u6d41\u7545\uff0c\u8a00\u7b80\u610f\u8d45\uff0c\u662f\u5165\u95e8\u7684\u597d\u6587\u7ae0\u3002 \u7b80\u5355\u6765\u8bb2\uff0c\u5f53\u5229\u7528k-neighbor \u6216[latex] \\epsilon [\/latex]\u65b9\u6cd5\u6784\u9020\u4e34\u8857\u77e9\u9635\uff0c\u5229\u7528Simpled minded\uff080 or 1\uff09\u6216\u8005Heat Kernel\u6765\u6784\u5efaWeight\u77e9\u9635\u540e\uff0c\u6211\u4eec\u7684\u95ee\u9898\u662f\u6c42\u89e3\uff1a $$ L f = \\lambda D f \\quad st. \\quad f^T D f = 1 \\quad \\mathrm{and} \\quad f^T D \\mathbf{1} = 0 $$ \u6211\u4eec\u5df2\u7ecf\u77e5\u9053D\u662f\u4e00\u4e2a\u5bf9\u89d2\u9635\uff0c\u6240\u4ee5\u6c42\u89e3$$ D^{-1} L f = \\lambda f $$\u5373\u53ef\u3002 \u8003\u8651\u5230\u7ea6\u675f\u6761\u4ef6\uff0c\u6211\u4eec\u53ea\u9700\u5bf9\u6bcf\u4e00\u4e2a[latex]f[\\latex]\u505a\u5982\u4e0b\u53d8\u6362\uff1a $$ f^T D f = […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[15],"tags":[20,16,19],"class_list":["post-113","post","type-post","status-publish","format-standard","hentry","category-statistics","tag-dimension-reduction","tag-machine-learning","tag-statistics-2"],"_links":{"self":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/posts\/113","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/comments?post=113"}],"version-history":[{"count":0,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/posts\/113\/revisions"}],"wp:attachment":[{"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/media?parent=113"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/categories?post=113"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zhanxw.com\/blog\/wp-json\/wp\/v2\/tags?post=113"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}