奇迹园
yangliuy · 共 134 篇文章
数据挖掘-基于贝叶斯算法及KNN算法的newsgroup18828文档分类器的JAVA实现(下)
本文接数据挖掘- 基于贝叶斯算法及KNN算法的newsgroup18828文档分类器的JAVA实现(上) 本分类器的完整工程可以到 点击打开链接 下载,详细说明的运行方法,用eclipse可以运行,学习数据挖掘的朋友可以跑一下,有问题可以联系我,欢迎交流:) 上文中描述了newsgroup18828文档集的预处理及贝叶斯算法的JAVA实现,下面我们来看看如何实现基于KNN算法的newsgroup文本分类器 1 KNN算法的描述 KNN算法描述如下: STEP ONE:文本向量化表示,由特征词的TF*IDF值计算 STEP TWO:在新文本到达后,根据特征词确定新文本的向量 STEP THRE…
2012-03-27T23:47:00Z · 评论(0)
数据挖掘-基于贝叶斯算法及KNN算法的newsgroup18828文档分类器的JAVA实现(上)
本文主要描述基于贝叶斯算法及KNN算法的newsgroup18828文档分类器的设计及实现,包括数据预处理、贝叶斯算法及KNN算法实现。本分类器的完整工程可以到 点击打开链接 下载,详细说明的运行方法,用eclipse可以运行,学习数据挖掘的朋友可以跑一下,有问题可以联系我,欢迎交流:)。本文主要内容如下: 对newsgroup文档集进行预处理,提取出30095 个特征词 计算每篇文档中的特征词的TF*IDF值,实现文档向量化,在KNN算法中使用 用JAVA实现了KNN算法及朴素贝叶斯算法的newsgroup文本分类器 1、Newsgroup文档集介绍 Newsgroups最早由Lang于1…
2012-03-27T23:06:00Z · 评论(0)
面试题-在一本书的乱序页码中找缺失的页码
这是我面试A公司时碰到的算法题,题目大意是一本书缺了一页,然后书页顺序被打乱,问如何迅速找到缺失的那一页? 思路:其实就是在乱序数组里面找缺失的一个数,有以下方法 1、直接排序,然后遍历一次 时间复杂度O(NlogN),不需要额外空间 2、用bitmap思想,开一个大数组,可以用bitset以节省空间,遍历一遍该数组,出现的数字置位为1,遍历完毕后,没有置位的那一位对应的数就是缺失的数字,时间复杂度O(N),但是需要O(N)的额外空间 3、原地桶排序思想,遍历数组,如果脚标与值相等不做任何处理;否则交换该数到其值索引的那个位置,对于被占用位置的数字,采用同样的方法放到其值索引的位置,直到数组…
2012-03-17T23:16:00Z · 评论(0)
awk学习笔记
Table of Contents 原文链接 http://man.lupaworld.com/content/manage/ringkee/awk.htm 1. awk简介 2. awk命令格式和选项 2.1. awk的语法有两种形式 2.2. 命令选项 3. 模式和操作 3.1. 模式 3.2. 操作 4. awk的环境变量 5. awk运算符 6. 记录和域 6.1. 记录 6.2. 域 6.3. 域分隔符 7. gawk专用正则表达式元字符 8. POSIX字符集 9. 匹配操作符(~) 10. 比较表达式 11. 范围模板 12. 一个验证passwd文件有效性的例子 13. 几个…
2012-03-07T11:57:00Z · 评论(0)
数据挖掘—决策树ID3分类算法的C++实现
数据挖掘课上面老师介绍了下决策树ID3算法,我抽空余时间把这个算法用C++实现了一遍。 决策树算法是非常常用的分类算法,是逼近离散目标函数的方法,学习得到的函数以决策树的形式表示。其基本思路是不断选取产生信息增益最大的属性来划分样例集和,构造决策树。信息增益定义为结点与其子结点的信息熵之差。信息熵是香农提出的,用于描述信息不纯度(不稳定性),其计算公式是 Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望,可以区分训练样本中正负样本的能力,其计算公司是 我实现该算法针对的样例集合如下 该表记录了在不同气候条件下是否去打球…
2012-03-05T19:04:00Z · 评论(0)
SVM算法入门
课程文本分类project SVM算法入门 转自: http://www.blogjava.net/zhenandaci/category/31868.html SVM入门(一)至(三)Refresh 按:之前的文章重新汇编一下,修改了一些错误和不当的说法,一起复习,然后继续SVM之旅. (一)SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中[10]。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小…
2012-03-04T02:13:00Z · 评论(0)
文本分类入门
最近要做文本分类相关的课程project,因此上网找了一下文本分类的资料,下面这个感觉比较通俗易懂,收录在这里。 来源 http://www.blogjava.net/zhenandaci/category/31868.html?Show=All 文本分类入 门(一)文本分类问题的定义 文本分类系列文章,从文本分类问题的定义开始,主要讲解文本分类系统的构成,主流的统计学习方法以及较为优秀的SVM算法及其改进。 一个文本(以下基本不区分“文本”和“文档”两个词的含义)分类问题就是将一篇文档归入预先定义的几个类别中的一个或几个,而文本的自动分类则是使用计算机程序来实现这样的分类。通俗点说,就好比…
2012-03-04T02:08:00Z · 评论(0)
数据挖掘—概念空间挖掘FindS算法的C++实现
该算法是概念空间挖掘最简单的算法,只考虑了正实例,不断做泛化,实际上求得了一个最特化边界 概念挖掘需求 C++实现 测试数据 测试结果
2012-03-03T11:08:00Z · 评论(0)
数据挖掘—概念学习Candidate-Elimination算法的C++实现
Candidate-Elimination算法是数据挖掘中的一种概念学习算法,部分解决Find-S的不足,可以输出所有与训练样本一致的概念,同时利用概念间偏序关系来指导搜索,其伪代码描述如下 花了几个小时的时间总算把这个算法用C++实现测试通过了,采用了STL中的二维Vector容器保存字符串,在调试部分浪费不少时间。主要是用VC++ 6.0查看STL容器中的变量值不太方便,比如Vector,需要在调式窗口里输入s._first,10 才可以看到全部的数据;也可以加输出的测试代码,但是比较麻烦。好了,废话不多说了,贴上代码,希望各位批评指正。 【概念挖掘需求】 基本的算法思想是,泛化边界初始…
2012-02-27T22:09:00Z · 评论(0)
STL Contianers容器精辟总结
STLContianers容器精辟总结 一、序列容器( Sequence containers ) 1、 Vector :一种序列容器,实现为动态数组,元素保存在连续的存储位置,支持迭代器和索引访问。与数组不同的是,可以自动分配存储空间,容易改变容器大小。当需要频繁从序列尾部增加或者删除数据时,可以表现出高效的性能。size记录了当前容器大小,capacity记录了当前已分配的最大空间。 2、 List:一种序列容器,实现为双向链表。与其他容器如vector和deques相比,list在容器内部插入、删除元素操作中性能更好。主要缺点是不支持元素直接按索引访问,需要迭代遍历。 3、 Deque…
2012-02-26T19:06:00Z · 评论(0)
NYU AI作业习题-活动安排问题 BFS+DFS Iterative deepening depth-first search
题目链接 http://cs.nyu.edu/courses/spring12/CSCI-GA.2560-001/prog1.html 题目大意:给定n个任务的时间、价值及先后序关系,求一个可行的任务子集,使得时间之和不大于deadline,价值之和不小于targetVaule,且不可出现逆序。 算法思路:题目已经给出算法,转化为状态空间搜索问题(tree-structured state space search problem),先对结点拓扑排序,存储前序的结点关系,然后先对状态搜索树进行BFS,可行的状态压入队列,到达到限制值后,再以队列中的状态为起点进行迭代深入搜索(Iterativ…
2012-02-16T01:28:00Z · 评论(0)
POJ 1664 求m个苹果放入n个盘子的不同放法数目 递归 分类讨论
通过分类讨论,将规模较大的问题转换成规模较小的相同问题,学会”降维“,将索引值不断降小,就可以递归求解 设f(m,n)为把m个苹果放到n个盘子中的方法数,m>=0,n>=0. 若m和n中任何一个等于0,那么f(m,n) = 1,注意不是等于0,因为相当于就那么一种结果,就是不往盘子里面放(没有苹果),或者,连盘子都没有。 若n=1,显然对于任意的m>=0 有f(m,1) = 1 若m=1,显然对于任意的n>=0 有f(1,n) = 1 接下来讨论m>1 && n>1的情况: 若 m < n 则 f(m,n) = f(m,m)。即空哪几个盘子都是一样的 若 m>=n 则 大体有两种放法: 第1…
2012-02-11T18:42:00Z · 评论(0)
POJ 1163 求数字三角形由顶到底边的最大数字和 动态规划
这题是求数字三角形由顶到底边最大数字和对应的路径,在准备夏令营的时候红皮教材上面有,当时没有学动态规划算法,不是很理解,经过这一阵对算法的学习和POJ训练,总算在10分钟内独立思考AC,其实挺简单,满足最优子结构和无后效性,是经典的动态规划问题。 一般的思考方法是,由特殊情况比如题目给的示例数据入手,分析如何计算辅助数组dp的值,dp[i][j]记录以r[i][j]为顶点向下走到底边可以得到的最大和,dp数组底边的值就是数字三角形底边数字,然后从底向上计算,dp数组的计算方程(即动态规划状态方程)为 dp[i][j] = max(r[i][j] + dp[i+1][j] , r[i][j] …
2012-02-11T16:27:00Z · 评论(0)
POJ 2499 求二叉树结点到根结点的路径长度 递归 二叉树
这题主要求二叉树结点到根结点的路径长度,基本的思路是 比较a与b,如果a大则当前结点是左孩子,a-b作为父结点的左数,父结点的右数与当前右数相等;如果b大则当前结点为右孩子,同理可以求父结点,直到父结点为(1,1)遍历结束。 当用原始的递归算法会超时,需要考虑a=1或b=1的特殊情况,同时利用a与b的倍数关系加快遍历速度 Source Code Problem: 2499 User: yangliuACMer Memory: 244K Time: 0MS Language: C++ Result: Accepted 参考了http://www.cnblogs.com/allensun/arc…
2012-02-11T15:31:00Z · 评论(0)
POJ 2388 求中位数 qsort用法
这题就是求中位数,直接用qsort排序取中,算法复杂度为O(NlogN) 当然求中位数的最优算法是O(N)的Select算法 Source Code Problem: 2388 User: yangliuACMer Memory: 284K Time: 63MS Language: C++ Result: Accepted
2012-02-11T13:23:00Z · 评论(0)