文章 47
评论 4
浏览 11472
利用Hadoop平台实现分布式谱聚类算法思路

利用Hadoop平台实现分布式谱聚类算法思路

传统谱聚类算法实现步骤 构建邻接矩阵 W 计算度矩阵 D 计算拉普拉斯矩阵矩阵 L 计算 L 的特征向量,k 个最小的特征值对应的特征向量对应的特征向量组成矩阵 Z 标准化 Z 使用 K-mean 进行最后的聚类 并行谱聚类算法 引入并行的目的 为何要将传统的分布式算法改进为并行的分布式谱聚类算法呢?目得无外乎提升聚类速度与解决矩阵过大无法一次性载入内存。 所以我们追求的目标为:尽量使矩阵成为稀疏矩阵,这样既节省存储空间又利于加速聚类。 构造邻接矩阵 以往使用全连接法,每个节点之间都需要计算距离这显然是不符合我们的要求的。故此次我们采用“ε近邻法”构造进阶矩阵。 伪代码: 1节点作为全局变量存在HBase中,最后构造出的邻接矩阵也存于HBase中 2 3input : <key,null> 4ouput : <key,null> 5index = key 6anotherIndex = n-key+1 7 8for i in [index,anotherIndex]: 9 i_node_data = getNodeData(i) 10 f....

关于动态规划的一点小想法

关于动态规划的一点小想法

最近一直在做动态规划的题,也算有了一些自己的小感悟,暂时总结一下 首先看一道例题 题目链接 描述 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角,出口在右下角。 小明被带到地宫的入口,国王要求他只能向右或向下行走。 走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。 当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。 请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。 输入 输入一行 3 个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12) 接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 输出 要求输出一个整数,表示正好取 k 个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。 输入样例1 2 2 2 1 2 2 1 输出样例1 2 输入样例2 2 3....

谱聚类再次整理

谱聚类再次整理

常读常新啊,又更新一次,理解又加深一次!

最小生成树算法

最小生成树算法

引入问题 首先来看这样一个问题 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数 N(≤1000)和候选道路数目 M(≤3N);随后的 M 行对应 M 条道路,每行给出 3 个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从 1 到 N 编号。 输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出 −1,表示需要建设更多公路。 根据题目的描述,我们可以得知这是一道图论的题目,图为带权无向图,边上的权值即为题中描述的道路修建成本。 现在需要我们根据已有的图,求该图的最小(权值和最小)生成树。 这时候就需要引入解决问题的最小生成树算法了。 Prim 算法思路 首先读入所有的边,边的数据结构是一个结构体,主要包括:起点、终点、权值。 读入边之后按照边的权值由小到大排序。初始化一个数组记录边加入生成树的状态,初始时全部边为未加入。再初始化一个数组记录结点加入生成树的情况。 将某一个结点加入生成树(改变状态标志),因为所....

整型数二进制1的个数

整型数二进制1的个数

这是由BBfat推荐给我的一道经典面试题

模板题——连续子序列和的最大值

模板题——连续子序列和的最大值

题目: 给定一个长度为 n 的整形数组 nums,求从数组索引 l 至 索引 r 的整数序列中,连续序列和的最大值为多少。 思路: 本题的主要思路,可分为两种 使用遍历的思想,遍历出序列的每种情况,逐一求和,计算最大值 但这种思路及其耗费时间,不可取。 使用动态规划的思想,使用一个数组 dp 记录,从索引 l 起包含位置 k 连续序列和的最大值 (l<=k<=r),最大值可由下面的公式推导。 dp[k] = max{ num[k] , num[k] + dp[k-1] } 公式解释: 这个公式的意思很明了,即某个位置之前的序列和若为正,那么包含之前的序列,肯定会使包含当前位置的序列和增大。 这个公式不好理解之处在于,若一个位置的值为负还要包括他吗?举个例子来说明: 若位置 i 处值为负,之前序列和为正,那么虽然包括了他使到这个位置为止的序列和减小,但是起到了连接 i+1 位置的作用,若 i+1 位置的值很大,那么包含 i 位置使序列和减小的损失就可以忽略了,因为到 i+1 处的序列和是增大的了。 若之前序列和为负,那么包含之前序列就没有任何意义,到 i ....

30米大刀硬是剪不动这个枝😭——经典DFS+剪枝(求一份AC代码)

30米大刀硬是剪不动这个枝😭——经典DFS+剪枝(求一份AC代码)

题目链接 我的代码如下: #include<iostream> #include<algorithm> #define long long ll using namespace std; int wood_length = 0; int * num, *state; int p, lenght, lastnum; int cmp(int a, int b) { return a > b; } bool dfs(int exist_num, int exist_length) { if (exist_num == 0 && exist_length == 0) return true; // 木棒用光,剩余长度也为0,成功 if (exist_num == 0 && exist_length != 0) return false; // 木棒用光,还有剩余长度,失败 if (exist_length == 0) exist_length = lenght; // 刚好拼完一根,继续拼下一根 int s = 0; if (exi....

报数游戏

报数游戏

线性表实验

最短路径

最短路径

计算图的最短路径有几种经典的算法: 弗洛伊德(Floyd)算法 迪杰斯特拉(Dijkstra)算法 贝尔曼福德(Bellman-Ford)算法 SPFA 算法 弗洛伊德算法 弗罗伊德算法的思想来自于动态规划。 基本思路为: 我们知道若给定任意结点 A、B,若想使两点之间的距离减小只有引入第三个点。 首先引入 结点 1 ,是否能使任意两个结点之间距离缩短呢?若能则更新距离。接着引入 结点 2 ,是否能在结点 1 的基础上继续缩短距离呢?这样一直到 结点 N。 因为每次引入 结点 i+1 都是在 结点 i 的基础上,所以最终的结果就是任意两点间的最短距离。 算法模板: cin>>n>>m; //n为节点数,m为路径数 for(i=0;i<m;i++){ cin>>begin>>end>>len; route[begin][end]=len; //读入路径 } for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if....

多项式求和

多项式求和

因为参加了CCF的认证考试,加之这假期事情比较少,所以决定静下心来学习几个算法,按照CSP网站上的题目去做,第二道题便是多项式求和。以前在数据结构课上,便了解过多项式求和利用的是栈这个数据结构。不过一直以来遇到需要自己实现的数据结构,我便有点犯怵。不过这次既然决定学习了,所以便决定解决这个问题。 要求如下: ‘+’、‘-’、‘x’、‘/’ 分别表示加减乘除四个基本操作 ‘(’、‘)’分别表示左右括号 要求计算最后结果 思路 分别需要两个栈来分别存放,操作数和操作码。 将多项式作为字符串进行输入。 之后遍历字符串,遇到操作数直接进栈,遇到操作码则较为复杂。 遇到操作码,需要和栈顶存放的操作码进行比较,若高于栈顶操作码,说明之后的出栈的顺序不会影响操作码的计算结果,操作码直接进栈即可。(因为出栈时是后入栈的先出栈,也先计算) 若低于栈顶操作码,则需要将栈顶操作码出栈,操作数出栈两次将结果进行计算,之后再将结果入栈。 若遍历结束,也即遇到'\0'符号,若这是操作码栈中不为空,则需依次出栈计算结果。直到操作码栈为空。 C/C++代码: #include <iostream>....

闻道