本来我想用前面那个Human Activity Recognition Using Smartphones Data Set来完成我的Data mining的结业小论文，但后来在将该Dataset转换为Weka的arff格式时碰到点问题，所以就放弃了，最终将以下面这个Image Segmentation Data Set来写，同时相对来说，这个Dataset也跟我的工作更加相关、相近一些。 本Dataset源于：http://archive.ics.uci.edu/ml/datasets/Image+Segmentation
Postgraduate
From: http://archive.ics.uci.edu/ml/datasets/Human+Activity+Recognition+Using+Smartphones Download: Data Folder, Data Set DescriptionAbstract: Human Activity Recognition database built from the recordings of 30 subjects performing activities of daily living (ADL) while carrying a waist-mounted smartphone with embedded inertial sensors. Data Set Characteristics: Multivariate, Time-Series Number of Instances: 10299 Area: Computer Attribute Characteristics: N/A Number of […]
Human Activity Recognition Using Smartphones Data Set
与去年相比，今年的考研分数线总体上升。学术型学位中除哲学、经济学、军事学分数线略有下降外，包括教育学、历史学、管理学等10门学科的分数线均有所提高。 教育部公布《2013年全国硕士研究生招生考试考生进入复试的初试成绩基本要求》。与去年相比，今年的考研分数线总体上升。学术型学位中除哲学、经 济学、军事学分数线略有下降外，包括教育学、历史学、管理学等10门学科的分数线均有所提高。专业型学位中，除临床医学的总分略降外，审计、教育(汉语言 国际教育)、应用心理、艺术等11门学科的分数线均有所提高。各硕士生招生单位即将全面启动复试、录取工作。【进入2013考研复试专题】 教育部要求各省级教育部门和招生单位要高度重视、精心组织复试录取工作；加强复试考核，着力强化对考生创新精神和能力、专业兴趣和素养等方面的考 查；充分发挥和规范导师群体在复试选拔中的作用；规范复试录取工作程序，严肃招生纪律，大力推进信息公开，确保招生录取公平公正。 教育部同时要求各省级招生考试管理机构、各招生单位要切实加强针对复试考生的服务工作。为方便考生调剂，4月1日至5月5日，教育部将在“中国研究生招生信息网”(公网网址：http://yz.chsi.com.cn,教育网网址：http://yz.chsi.cn)开通“全国硕士研究生招生调剂服务系统”。符合条件且有调剂愿望的考生可及时上网了解调剂信息和调剂系统的使用方法，按要求申请调剂，招生调剂单位要认真细致地做好相关工作。【微博热议2013考研国家线】 附： 2013年全国硕士研究生招生考试考生进入复试的初试成绩基本要求(学术型学位类) 学科门类(专业)名称 A类考生* B类考生* 备 注 总分 单科（满分=100分） 单科（满分>100分） 总分 单科（满分=100分） 单科（满分>100分） 哲学 280↓ 38 57 270↓ 35↓ 53↓ *A类考生：报考地处一区招生单位的考生。 *B类考生：报考地处二区招生单位的考生。 一区系北京、天津、河北、山西、辽宁、吉林、黑龙江、上海、江苏、浙江、安徽、福建、江西、山东、河南、湖北、湖南、广东、重庆、四川、陕西等21省(市)； 二区系内蒙古、广西、海南、贵州、云南、西藏、甘肃、青海、宁夏、新疆等10省(区)。 * 工学照顾专业:力学[0801]、冶金工程[0806]、动力工程及工程热物理[0807]、水利工程[0815]、地质资源与地质工程[0818]、矿 业工程[0819]、船舶与海洋工程[0824]、航空宇航科学与技术[0825]、兵器科学与技术[0826]、核科学与技术[0827]、农业工程 [0828]。 *中医类照顾专业：中医学[1005]、中西医结合[1006]。 *享受少数民族政策的考生： 报考地处二区招生单位，且毕业后在国务院公布的民族区域自治地方就业的少数民族普通高校应届本科毕业生考生；或者②工作单位在国务院公布的民族区域自治地方，为原单位定向或委托培养的少数民族在职人员考生。 经济学 340↓ 49↓ 74↓ 330↓ 46↓ 69↓ 法学 315 42 63 305 39 […]
2013年全国硕士研究生考试复试分数线划定
We finished our last class of data mining, and Professor Zhu(朱明) would like to close this course by a thesis about data mining, and the data material would better if relevant to our job. Here are the detail requirements: The five steps about writing this thesis: 1) 业务需求分析 比如：为了研究XXX数据，对YYY有帮助，bla bla […]
Preparing a thesis of data mining
Early this morning, I got a message from PJBS that tomorow(2013/3/9) will be our special english exam, it’ll be a closed-book exam. No cellphones, no tablets, only dicts are allowed. Wondering why this course is so important? It’s not a professional course (is it??). Anyway lucky me, Lucy has a […]
Exam for special english
题目： 输入一棵二叉查找树，将该二叉查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 /\ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二叉查找树节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child […]
把二叉查找树转变成排序的双向链表
最近才捡起的算法设计与分析.分析不准确的地方谅解,请各位看官指正. 1. 分治法与动态规划主要共同点: 二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解. 2. 分治法与动态规划实现方法: ① 分治法通常利用递归求解. ② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解. 3. 分治法与动态规划主要区别: ① 分治法将分解后的子问题看成相互独立的. ② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分. 例如: 在求解斐波那契数列过程中,求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).其中,求解fibonacci(4)时,需要求解fibonacci(3). 在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),即使求解fibonacci(4)子问题的时候已经求解过,也就是说,求解了二次子问题fibonacci(3). 动态规划为了避免类似子问题fibonacci(3)的重复求解,将已经求解过的子问题的解保存下来,在需要的时候将解值取出来,省去子问题解的重复求解过程. 4. 分治法与动态规划适用条件: ① 原问题具有最优子结构性质的前提下,分解出的子问题都绝对相互独立. ② 原问题具有最优子结构性质的前提下,分解出的子问题并不相互独立,求解一个子问题可能要用到已经求解过的子问题的解,子问题间具有重叠性,即适合具有重叠子问题性质的原问题. 5. 分治法与动态规划复杂度分析: ① 分治法因为对子问题进行了多次求解,所以效率比动态规划低一点.(时间复杂度相对高) ② 动态规划求解需要将子问题的解保存下来,所以会比分治法多用一些空间.(空间复杂度相对高) 其实,算法世界里,要么用时间换空间,要么用空间换时间.
分治法与动态规划小结
动态规划和贪心算法都是一种递推算法, 均有局部最优解来推导全局最优解.但它们的不同是… 相同点： 动态规划和贪心算法都是一种递推算法 均有局部最优解来推导全局最优解 不同点： 贪心算法： 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。 动态规划算法： 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解 3.边界条件：即最简单的，可以直接得出的局部最优解 ============================================================================== 贪心算法与动态规划 贪心法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解 贪心算法最经典的例子，给钱问题。 比如中国的货币，只看元，有1元2元5元10元20、50、100 如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？ 如果用贪心算，就是我每一次拿那张可能拿的最大的。 比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元 也就是3张 10、5、1。 每次拿能拿的最大的，就是贪心。 但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数 贪心只能得到一个比较好的解，而且贪心算法很好想得到。 再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了 比如某国的钱币分为 1元3元4元 如果要拿6元钱 怎么拿？贪心的话 […]
动态规划和贪心算法的区别
本文的文字部分转载自博客园，但由于其Dijkstra算法的代码存在一些问题，故特修改了一版该算法，更新上去。供大家参考。 本文相关的习题： 试举例说明如果允许带权有向图中某些边的权为负实数，则Dijkstra算法不能正确求得从源到所有其他顶点的最短路径长度。 Dijkstra算法 算法流程： (a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径； (c) 修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替。 (d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。 假设一共有N个节点，出发结点为s，需要一个一维数组prev[N]来记录前一个节点序号，一个一维数组dist[N]来记录从原点到当前节点最短 路径（初始值为s到Vi的边的权值，没有则为+∞），一个二维数组weights[N][N]来记录各点之间边的权重，按以上流程更新prev[N]和 dist[N]。 参考代码： //第四章：贪心算法 ////////////////////////////////////////////////////////////////////////// //FUNCTION: Dijkstra 4.4 单源最短路径问题, P105 //INPUT: // 带权有向图G=(V, E) // V = {1, 2, …, n}, 顶点v是源点 // c是一个二维数组，c[i][j]表示边(i, j )的权，当<i, j> 属于E时，c[i][j]是一个大数(无穷大） // dist[i]表示当前从源点到顶点的i 的最短路径长度. //OUTPUT: // 路径数组prev[] ////////////////////////////////////////////////////////////////////////// […]
单源最短路径算法–Dijkstra算法和Bellman-Ford算法
要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处 理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计 算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1） 选一个方程的近似根，赋给变量x0； （2） 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3） 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)； /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，xn-1） 设方程组为： xi=gi(X) (I=0，1，…，n-1) 则求方程组根的迭代算法可描述如下： 【算法】迭代法求方程组的根 { for (i=0;i x[i]=初始近似根; do { for (i=0;i […]
常用算法设计方法
最少费用购物 Description ?问题描述： 商店中每种商品都有标价。例如，一朵花的价格是2元。一个花瓶的价格是5 元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价售。例如，3朵花的价格不是6元而是5元。2 个花瓶加1 朵花的优惠价是10 元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。 ?编程任务： 对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。 Input 由文件input.txt提供欲购商品数据。文件的第1行中有1 个整数B（0≤B≤5），表示所购商品种类数。接下来的B 行，每行有3 个数C，K 和P。C 表示商品的编码（每种商品有唯一编码），1≤C≤999。K 表示购买该种商品总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，一次最多可购买5*5＝25件商品。由文件offer.txt提供优惠商品价数据。文 件的第1行中有1 个整数S（0≤S≤99），表示共有S 种优惠商品组合。接下来的S 行，每行的第一个数描述优惠商品组合中商品的种类数j。接着是j 个数字对（C，K），其中C 是商品编码，1≤C≤999。K 表示该种商品在此组合中的数量，1≤K≤5。每行最后一个数字P（1≤ P≤9999）表示此商品组合的优惠价。 Output 程序运行结束时，将计算出的所购商品应付的最少费用输出到文件output.txt中。 Sample Input input.txt 2 7 3 2 8 2 5 offer.txt 2 1 7 3 5 2 7 1 8 2 […]
最小费用购物问题
用2 台处理机A 和B 处理n个作业。设第i 个作业交给机器A 处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性 能关系，很可能对于某些i，有ai>=bi，而对于某些j，j≠i，有aj<bj，既不能将一个作业分开由2 台机器处理，也没有一台机器能 同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。 input 6 2 5 7 10 5 2 3 8 4 11 3 4 output15 //独立任务调度 #include<iostream> #include<vector> using namespace std; const int n=6; int a1[]={2,5,7,10,5,2}; int b1[]={3,8,4,11,3,4}; class tree { public: int a,b; }; int main() { cout<<“******************************************”<<endl; cout<<” 任务调度情况如下:”<<endl; cout<<” (1)作业数目:”<<n<<endl; cout<<” (2)各作业处理时间:”<<endl; cout<<” “; for(int aj=0;aj<n;aj++) cout<<a1[aj]<<” “; cout<<endl; cout<<” “; for(int bj=0;bj<n;bj++) cout<<b1[bj]<<” […]
独立任务最优调度问题
【实验目的】 练习掌握动态规划算法。 【实验内容】 设计一个O(n*n)时间的算法，找出由n个数组成的序列的最长单调递增子序列。 【实验条件】 Microsoft Visual C++ 6.0 【需求分析】 题目要求在O(n*n)的时间内找出n个数组成的序列的最长单调递增子序列,需要用到排序算法，查找最长公共子序列的算法。 【设计原理】 将数组a复制到数组x,先用排序算法将数组x排序，在调用查找最长公共子序列的算法求出数组a和数组x中的最长公共子序列，因为数组x是单调递增的，所以由此求出来的最长公共子序列就是题设所求的最长单调递增子序列。 【概要设计】 数据： N：数组元素个数。 a[N]：用于存放数组。 X[N]：复制数组a[N]，并排序。 c[i][j]：存储a和x的最长公共子序列的长度。 b[i][j]：记录c[i][j]的值是由哪一个资问题的解得到的。 函数： int Partition(int a[],int p,int t,int x); //数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。 void Swap(int &x,int &y); //交换元素x和y。 void QuickSort(int a[],int p,int r); //快速排序。 void LCSL(int m,int n,int *x,int *y,int **c,int **b); //计算最长公共子序列长度。 void LCS(int […]
在O(n*n)时间内出由n个数组成的序列的最长单调递增子序列。
/* 课本0-1背包。 程序功能：将物体只能一次放入包中，要不超过总量 且 价值最大 经过vc8.0编译通过 * */ #include <iostream> using namespace std; #define N 10 #define C 50 void knapsack(int * v,int *w,int wlength,int c,int(*m)[C+1]) { int n=wlength-1; int jmax=std::min(w[n]-1,c); for(int j=0;j<=jmax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i–) { jmax=std::min(w[i]-1,c); for(int j=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=std::max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=std::max(m[1][c],m[2][c-w[1]]+v[1]); } […]
0-1背包
/* 课本 0-1背包 加上体积限制。 程序功能：将物体只能一次放入包中，要不超过总量、总体积且 价值最大 经过vc8.0编译通过 * */ #include <iostream> #include <iomanip> using namespace std; #define N 10 //物品的可选数量 #define C 40 //包的最大可容纳重量 #define E 28 //包的最大可容纳体积 //动态规划算法 void knapsack(int * v,int *w,int wlength,int c,int *e,int ee,int (*m)[C+1][E+1]) { int n=wlength-1; //—————————————– //递归计算的第一步 //求出当物品只有n的解 int jmax = std::min(w[n]-1,c); int jmax2 = std::min(e[n]-1,ee); for(int j=0;j<=jmax;j++) for(int k=0;k<=jmax2;k++) m[n][j][k] = 0; […]