- 浏览: 829998 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (379)
- struts (5)
- hibernate (16)
- spring (16)
- ssh (20)
- MySQL (16)
- 数据库脚本 (2)
- DownLoad (1)
- GAE (5)
- Java (103)
- LoadRunner (2)
- VF (1)
- 学习资料 (24)
- 软件使用 (21)
- 通信类 (4)
- 生活 (3)
- J2ME (1)
- 心理学 (1)
- Linux (26)
- Android (3)
- Oracle (1)
- 面向对象概念&面试准备 (11)
- ExtJs (2)
- Google Map (1)
- Flex (47)
- 算法研究 (1)
- share (20)
- python (1)
- MongoDB (7)
- centos6 (13)
- C++ (8)
- DB2 (3)
- C# (1)
- 代码片段 (24)
- Lucene (2)
- php (1)
- NodeJS (1)
- Express (1)
最新评论
-
shua1991:
已阅,我表示同意。
Eclipse统计代码行数 -
nakedou:
写的不错,挺详细的
在CentOS中使用 yum 安装MongoDB及服务器端配置 -
sjp524617477:
好方法
Eclipse统计代码行数 -
simpletrc:
<script>ale ...
Java写到.txt文件,如何实现换行 -
csdn_zuoqiang:
Apache Ftp Server,目前是1.0.4,非常好的 ...
Apache FtpServer在64位系统下服务不能启动解决方法
前记
随着文本信息量的快速增长, 文本分类己成为信息检索、知识挖掘和管理等领域的关键技术。文本分类的精确程度取决于特征提取的科学性和分类算法的科学性。现有的文本分类方法主要有支持 向量机(SVM)、k 最近邻(KNN)、决策树、线性最小二乘法估计(LLSF)和贝叶斯分类算法(Bayes)等。KNN 算法是 VSM(向量空间模型)下最好的分类算法之一。
1. 何为KNN?
以下是引用wiki的一个定义:
k -nearest neighbors algorithm (k -NN) is a method for classifying objects based on closest training examples in the feature space. k -NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification. The k -nearest neighbor algorithm is amongst the simplest of all machine learning algorithms: an object is classified by a majority vote of its neighbors, with the object being assigned to the class most common amongst its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of its nearest neighbor.
K 最近邻 (k-Nearest Neighbor , KNN) 分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的 k 个最相似 ( 即特征空间中最邻近 ) 的样本中的大多数属于某一个类别,则该样本也属于这个类别。 KNN 算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN 方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于 KNN 方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说, KNN 方法较其他方法更为适合。
KNN 算法不仅可以用于分类,还可以用于回归。通过找出一个样本的 k 个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值 (weight) ,如权值与距离成正比。
2. KNN算法的决策过程
如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。
3. 存在的不足
该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中 大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都 要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适 用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
4. 改进的KNN算法
a. 快速KNN算法。FKNN:http://www.docin.com/p-9581757.html * *(实际应用中结合lucene)**
b. 加权欧氏距离公式。在传统的欧氏距离中,各特征的权重相同,也就是认定各个特征对于分类的贡献是相同的,显然这是不符合实际情况的。同等的权重使得特征向 量之间相似度计算不够准确, 进而影响分类精度。加权欧氏距离公式,特征权重通过灵敏度方法获得**。(根据业务需求调整,例如关键字加权、词性加权等)**
5. 算法的实现
以下实现语料库基于搜狗文本分类语料库: http://www.sogou.com/labs/dl/c.html
a. 传统knn实现
。主要分为训练和计算两个步骤,以下是代码片段:
1. 训练文本,构建语料库。
(1)训练指定文件夹中的语料 - 》 (2)读取单个文件,构建语料库 -》 (3)对文本进行分词(基于中科院分词器),构建 词组 向量模型 -》重复(2)(3)
|
|
b. 改进的KNN算法实现
1. 利用lucene对所有语料库建立索引
|
2. 改进lucene search score机制
|
|
|
待续
7. 后感
文本分类的进一步改进不在算法方面,应该 立足于影响文本分类最底层、最根本的因素:文本表示中的特征项, 提高 特征项的完整独立程度。 关键短语是具有强文本表示功能的特征短语,在表示文本时,能将文本的内容特征(如主题类别)鲜明地表示出来。 关键短语具有结构稳定、语义完整和强统计意义的特点,能克服向量空间模型和其他算法的缺点,更适合作为文本表示的特征,有利于提高文本分类的效果。
发表评论
-
IDEA 常用配置以及快捷
2012-09-01 10:38 50841. IDEA内存优化 ... -
Ubuntu 10.04 TinyOS
2012-08-20 00:42 1542sudo gedit /etc/apt/sources.lis ... -
我看用户体验与用户价值
2012-07-01 14:55 1030不知道从什么时候开始,各个信息源都开始充斥着用户体验的讨 ... -
在windows 7上安装Maven2.2.1
2012-06-18 17:00 1212Maven是一个java工具,所以请确保jdk环境已经正确安装 ... -
产品经理如何赢得开发人员的尊重和支持?
2012-06-14 09:08 943对于产品经理来说, ... -
Apache FtpServer在64位系统下服务不能启动解决方法
2012-06-10 21:29 6792Apache FTPServer是一款用Java开发的 ... -
Java 集合类
2012-06-07 22:03 1553Java 集合类 1. 为什么要了解J ... -
Java集合工具类之List - ArrayList & LinkedList
2012-06-07 21:21 18971.ArrayList 的数据结构 ... -
网络爬虫调研报告
2012-06-06 11:17 6007网络爬虫调研报告 调研背景 项目中要对 ... -
海量数据处理
2012-06-05 10:02 1864一:常见的题目:- 1 ... -
short、int、long与byte之间的转换工具类
2012-05-31 11:05 4472/** * 各基础类型与byte之间的转换 * ... -
Ubuntu 12.04 改造指南
2012-05-28 10:47 1394升级12.04已经有一段时间了。作为一个从08年就开始用 ... -
使用apt-get方式为Linux Mint 13安装PHP+MYSQL+Apache
2012-05-25 17:48 4764使用apt-get方式为Ubuntu安装PHP+MYSQ ... -
Linux Mint 13 配置JAVA 环境
2012-05-24 22:35 26170.1--下载 JAVA ... -
CentOS 5.5下搭建部署独立SVN服务器全程详解
2012-05-10 10:08 1126SVN服务器有2种运行方式: 1、独立服务器 (例如:s ... -
centos下使用Heartbeat实现集群
2012-05-09 11:44 1401Linux 包括 CentOS 下高可用性(HA:High A ... -
处理JSON最快的Java库
2011-12-19 16:35 1073FastJSON http://code.alibab ... -
SVN小文件清除脚本
2011-09-23 14:36 1081@echo off echo ************** ... -
Java代码片段
2011-08-31 10:11 639if(null != str && ... -
软件工程-数据流图(DFD)画法
2011-08-26 14:59 3952概念----数据流图(DFD) ...
相关推荐
模式识别中的KNN算法实现,基于Matlab的实现,以及剪辑近邻法的matlab实现。
这里通过python的绘图工具Matplotlib包可视化实现机器学习中的KNN算法。 需要提前安装python的Numpy和Matplotlib包。 KNN–最近邻分类算法,算法逻辑比较简单,思路如下: 1.设一待分类数据iData,先计算其到已...
KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN算法实现鸢尾花数据集分类 C语言实现 KNN...
Java实现kNN算法
kNN算法又称为k近邻分类。KNN是通过测量不同特征值之间的距离进行分类。它的的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K通常是...
KNN算法 C#程序
这是我发表的第一篇论文《一种基于层次分析法的改进KNN算法》的代码文档。这里面包含了AHP-KNN算法、FCD-KNN算法和论文实验代码,以及相关论文。
Python实现KNN算法 Python实现KNN算法 Python实现KNN算法
介绍了中心向量算法和KNN算法两种分类方法。针对KNN分类方法在计算文本...实验结果表明,改进的KNN算法较中心向量法和传统的KNN算法在处理中文文本分类问题上有较好的分类效果,验证了对KNN算法改进的有效性和可行性。
机器学习实战 - k近邻算法(KNN算法)总结 适合机器学习实战入门新手 K-近邻算法,又称为 KNN 算法,是数据挖掘技术中原理最简单的算法。 KNN 的工作原理:给定一个已知类别标签的数据训练集,输入没有标签的新数据...
C语言实现的KNN算法,在data文件中导入自己的数据集,在KNN.h中更在自己的K值。array.m中是自己曾经写的一些方便自己的函数,拿在这个算法中将一部分作为套用。
基于改进kNN算法的人脸识别研究.pdf
通过knn算法,实现WiFi室内定位在matlab环境下的仿真
本算法是Iris数据集使用KNN算法的代码,KNN算法的实现是比较简单的,我使用的是最简单的KNN算法,可以作为借鉴。
knn算法代码实现及应用实例的所需数据,与代码片“knn算法实现及应用实例代码”配套使用。
邻近算法,或者说K最近邻(KNN,K-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是K个最近的邻居的意思,说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据...
KNN算法综述,详细介绍knn算法的原理与过程
KNN,模式识别中常用的一种分类算法,C语言实现
K最邻近结点算法(k-Nearest Neighbor algorithm)的缩写形式,是电子信息分类器算法的一种。KNN方法对包容型数据的特征变量筛选尤其有效。
KNN算法通过matlab得简单实现。