Deeplearning Algorithms tutorial

谷歌的人工智能位于全球前列，在图像识别、语音识别、无人驾驶等技术上都已经落地。而百度实质意义上扛起了国内的人工智能的大旗，覆盖无人驾驶、智能助手、图像识别等许多层面。苹果业已开始全面拥抱机器学习，新产品进军家庭智能音箱并打造工作站级别Mac。另外，腾讯的深度学习平台Mariana已支持了微信语音识别的语音输入法、语音开放平台、长按语音消息转文本等产品，在微信图像识别中开始应用。全球前十大科技公司全部发力人工智能理论研究和应用的实现，虽然入门艰难，但是一旦入门，高手也就在你的不远处！ AI的开发离不开算法那我们就接下来开始学习算法吧！

等度量映射(IsometricMapping,Isomap)

等度量映射(Isomap)是最经典的非线性映射降维方法之一，它在MDS的基础上引入了“测地距离”的概念，直接解决了MDS使用欧氏距离无法应对非线性流形的问题。 测地距离(Geometric Distance)是高维流形中两点之间的最短距离，高维流形中，空间是不规则的，所以最短距离不一定是直线距离(欧氏距离)。就像蚂蚁从立方体的一面爬到另一面，不能直接横穿立方体一样。

等度量映射(IsometricMapping,Isomap) - 图1

图中左边的两个点的最近距离是蓝色实线的距离，而不应该是虚线的距离。

通常情况下真实的测地距离是非常难以求出的，但是等度量映射基于流形局部近似于欧式空间的定义提出了一种近似的求解方式。

我们通常的做法是:

  1. 求得原样本的KNN图，并依据定义保留其欧式距离。
  2. 所有非KNN的点间的距离规定为无穷大。
  3. 用dijkstra或floyd求出任意两点的最短路便可近似表示两点间的测地距离。
  4. 然后等度量映射(Isomap)将得到的测地距离矩阵输入MDS完成降维。

最后等度量映射(Isomap)将得到的测地距离矩阵输入MDS完成降维。

最后的结果是这样的。

等度量映射(IsometricMapping,Isomap) - 图2

应用示例:

  1. from IsomapCuda import *
  2. from DataUtils import *
  3. import getopt,sys
  5. GPU_MEM_SIZE = 512
  7. def Isomap(dataSet,outfile,srcDims,trgDims,k,eps=1000000000., CIsomap=False):
  8.     """
  9.     Classical isomap
  10.     """
  12.     #first do KNN
  13.     knnRefs,knnDists,knnm = KNN(dataSet,k,eps,srcDims)
  14.     mdists = []
  15.     if CIsomap:
  16.         mdists = C_Isomap(knnDists,knnm,k)
  18.     #then do APSP
  19.     pathMatrix = APSP(knnRefs,knnDists,knnm,eps)
  20.     del knnRefs
  21.     del knnDists
  22.     del knnm
  24.     #then normalize the matrix
  25.     normMatrix = NormMatrix(pathMatrix,mdists)
  26.     del pathMatrix
  27.     del mdists
  29.     #then get eigenvalues
  30.     #embedding = EigenEmbedding(normMatrix,trgDims)
  31.     embedding = QEig(normMatrix,trgDims)
  32.     del normMatrix
  34.     return embedding
  37. def NMIsomap(dataSet,outfile,srcDims,trgDims,k,eps=1000000000., saveSteps = False):
  38.     """
  39.     Non-Metric Isomap
  40.     """
  42.     #first do KNN
  43.     knnRefs,knnDists = loadSplitTable(KNN(dataSet,k,eps,srcDims))
  45.     #then do APSP
  46.     pathMatrix = APSP(knnRefs,knnDists,eps)
  47.     del knnRefs
  48.     del knnDists
  50.     #XXX:hacky way of saving this info
  51.     if saveSteps:
  52.         saveTable(pathMatrix,outfile[:-4]+'_distances.csv')
  54.     #then get the rank matrix
  55.     origDims = len(pathMatrix)
  56.     rankMatrix = RankMatrix(pathMatrix)
  57.     del pathMatrix
  59.     #then get the NMDS embedding
  60.     embedding = NMDS(rankMatrix, loadMatrix(dataSet)[:,:trgDims], origDims, trgDims)
  62.     return embedding
  66. if __name__ == '__main__':
  67.     arg_values = ['nonmetric=','outdims=','indims=','if=','of=','k=','eps=','help','h']
  68.     optlist, args = getopt.getopt(sys.argv[1:], 'x', arg_values)
  70.     trgDims = 3
  71.     srcDims = 10000000000
  72.     k =6
  73.     eps = 1000000000.
  74.     infile='swissroll.csv'
  75.     outfile='embedding.csv'
  76.     nonmetric=False
  79.     for o in optlist:
  80.         if o[0].strip('-') == 'outdims':
  81.             trgDims = int(o[1])
  82.     for o in optlist:
  83.         if o[0].strip('-') == 'indims':
  84.             srcDims = int(o[1])
  85.     for o in optlist:
  86.         if o[0].strip('-') == 'if':
  87.             infile = o[1]
  88.     for o in optlist:
  89.         if o[0].strip('-') == 'of':
  90.             outfile = o[1]
  91.     for o in optlist:
  92.         if o[0].strip('-') == 'k':
  93.             k = int(o[1])
  94.     for o in optlist:
  95.         if o[0].strip('-') == 'nonmetric':
  96.             if o[1].strip(' \r\n\t') == 'True' or o[1].strip(' \r\n\t') == 'true':
  97.                 nonmetric = True
  99.     for o in optlist:
  100.         if o[0].strip('-') == 'help' or o[1].strip('-') == 'h':
  101.             print "The following commands are available:"
  102.             print "\t--if=inputfile\tDefaults to swissroll.csv"
  103.             print "\t--of=outputfile\tDefaults to embedding.csv"
  104.             print "\t--k=k_nearest_neighbours\tDefaults to 12"
  105.             print "\t--outdims=embedding_dimensions\tDefaults to 3"
  106.             print "\t--indims=input_dimensions\tDefaults to all in the input file"
  107.             print "\t--nonmetric\tEnables non-metric MDS embeddings"
  108.     result = None
  109.     if not nonmetric:
  110.         result = Isomap(infile,outfile,srcDims,trgDims,k,eps,False)
  111.     else:
  112.         result = NMIsomap(infile,outfile,srcDims,trgDims,k,eps,False)
  114.     saveTable(result,outfile)