SimRank 算法开发

#### 输入数据

* 带权二分图

* 节点总数：500w

* 边数：7000w

* 分布：

* 二分图分为A、B两组数据（原始数据并没有区分）

* A组节点的出度符合长尾效应，类似于20%节点用于全部出度的80%

* 数据格式：((u, v), value)

* u: Int，节点ID

* v: Int, 节点ID

* value: Double, 边权

#### 输出数据

* A组节点相互间的相似度，B组节点相互间的相似度

#### 算法

* SimRank

#### 计算过程

* 根据公式，可以使用矩阵运算迭代计算相似矩阵

* L：带权邻接矩阵

* S：相似矩阵

* 伪代码

NL <= L列规范化

S <= 初始化为单位矩阵

迭代计算 {

S(k) <= NL * S(k-1) * L^T

}

返回S

#### 待优化问题

此博客中的热门博文

Spark 矩阵相乘实现

矩阵相乘计算的意义十分重要，比如我们做数据分析经常使用到的join操作就可以理解成为矩阵相乘的一个部分，矩阵相乘在很多分布式计算框架都有自己的实现，这些实现也可以根据不同大小的矩阵做不同的优化，比如在MapReduce上就有两种基本的实现：大矩阵乘小矩阵我可以把小矩阵放到DistrubutedCache，让每个mapper读取，这就是hive的MapJoin的实现。两个大矩阵相乘相乘中两个矩阵都是超大矩阵的话，为了减少MapReduce过程中产生的巨大数据，使用的带宽。都会采用矩阵分块的做法，以下会详细介绍这种实现方法。 Spark介绍官网介绍超大矩阵拆分计算方法单机（单线程）矩阵相乘假设有矩阵 A ， B ，相乘的结果为 C ，那么相乘的伪代码： C = 0 for(i <- 0 to A.lenght) for(k <- 0 to A[i].lenght) if(A[i][k]!=0) for(j <- B[k].lenght) { C[i][j] += A[i][k] * B[k][j] } 单机的计算中，时间复杂度是 O(n^3)，如果 n 增长到一定程度的时候，那么计算用时就会非常大，所以下面会说一下并行计算方法。并行矩阵相乘在计算的过程中，我们很容易发现每个 A[i][k] * B[k][j] 都可以单独计算，因此我也可以单独计算这些组合，最后做一个累计就可以获得 C 矩阵了，相乘伪代码如下： A = ((row, column), value) => (column, (row, value)) B = ((row, column), value) => (row, (column, value)) Temp = A.join(B) => (k, (rowA, valueA), (columnB, valueB)) => ((rowA, columnB), valueA * valueB) => ((rowC, columnC), valueC) C = Temp.reduceByKey =...

阅读全文

iphone 自动打包脚本

最近做ios开发，经常需要给老大打ipa包，这个虽然在xcode中编译并打包是很简单的事，不过每次都得花几分钟的时间做一些手动的放入Payload并压缩成zip包的操作。比较麻烦的是，在开发过程中，突然就说要一个可以执行的包做测试。那么，思路断了，正在写的代码要注释掉，这样持续下去浪费的时间会很多，所以还是需要写一个打包脚本。打包具体用到的命令是这些： xcodebuild: 主要用于编译项目 xcrun: 主要用于打ipa包具体打包流程就是编译，然后打一个发布包，一个ipa包，其实用脚本来说话就好了。另外，我用一个conf.dat来存放target和configuration,这些都在xcode里面指定好了，用xxx:xxx这样的格式来存放，xcodebuild在编译的时候会自动找到对应的配置。打包脚本如下: #!/bin/sh basePath=`pwd` distDir="target" distDir="${basePath}/${distDir}" rm -rdf "$distDir" mkdir -p "$distDir" baseName="xxx" #.app 的名字 projectDir=$(cd ../mobile/xxx; pwd) # 进入xcode工程目录 cd $projectDir for line in $(cat ${basePath}/conf.dat) do targetName=`echo $line | cut -f1 -d':'` conf=`echo $line | cut -f2 -d':'` releaseDir="${projectDir}/build/${conf}-iphoneos" rm -rdf "$releaseDir" echo "======build ${baseName}.app start..." echo "======clean ${conf}..." xcodebuild clean -configuration "$...

阅读全文

【转】ELO-对弈与排名（有触感的排名）

原文： https://www.cnblogs.com/leoin2012/p/4854442.html ELO介绍 ELO等级分制度是指由匈牙利裔美国物理学家 Elo创建的一个衡量各类对弈活动水平的评价方法，是当今对弈水平评估的公认的权威方法。被广泛用于国际象棋、围棋、足球、篮球等运动。网络游戏英雄联盟、魔兽世界内的竞技对战系统也采用此分级制度。历史 ELO等级分制度是基于统计学的一个评估棋手水平的方法。美国国际象棋协会在1960年首先使用这种计分方法。由于它比先前的方法更公平客观，这种方法很快流行开来。1970年国际棋联正式开始使用等级分制度。 Elo模型原先采用正态分布。但是实践显明棋手的表现并非呈正态分布，所以现在的等级分计分系统通常使用的是 Logistic distribution 。计分方法假设棋手A和B的当前等级分分别为和，则按Logistic distribution A对B的胜率期望值当为类似B对A的胜率为假如一位棋手在比赛中的真实得分（胜=1分，和=0.5分，负=0分）和他的胜率期望值不同，则他的等级分要作相应的调整。具体的数学公式为公式中和分别为棋手调整前后的等级分。在大师级比赛中通常为16。例如，棋手A等级分为1613，与等级分为1573的棋手B战平。若K取32，则A的胜率期望值为，约为0.5573，因而A的新等级分为1613 + 32 · (0.5 − 0.5573) = 1611.166 国际象棋中的等级分国际象棋中，等级分和棋联称号的大致对应为 2500分以上：国际特级大师 2400-2499分：国际大师 2300-2399分：棋联大师

阅读全文

自由的雏鸟

搜索此博客