论文研究-用于大数据分类的KNN算法研究.pdf

所需积分/C币:10 2019-07-22 21:55:04 1.13MB .PDF
9
收藏 收藏
举报

针对KNN算法在处理大数据时的两个不足对其进行了研究,提出多层差分KNN算法。算法对已知样本根据类域进行分层,既避免了传统改进算法中剪辑样本带来的判别误差,又大大降低了无效的计算量;同时在最后一层采用差分的方法进行决策,而不是直接根据最近邻进行分类,大大提高了分类的准确性。实验结果表明,该算法在对样本容量大、涉及邻域多的大数据样本进行分类时能取得较好的分类效果。
1344 计算机应用研究 第31卷 与训练样本库屮样本之间的相似度计算。按照传统的KNN 将传统KN分关器分类效果与之比较,结果如图7~9所示。 算法中直接计算测试样本与训练集中每个样本的相似度的方 法,其时间复杂度为0(n2);而 DM-KNN算法中构建树状分层 时J人√八一N 结枃,计算相似度时不需要对n个样木集都进行计算,只需要 0.75 与分层之后相似层下的样本进行相似度计算,算法的复杂度降 0.7 为O( n lou n)。也就是说改进后的算法时间复杂度远小于 张耍世 KNN算法或者类似于KNN算法的时间复杂度。 文本类别 3实验结果与分析 图7KNN与DM-KNN查准率比较 -KNN 3.1实验数据 本文对上述方法的分类效果进行了实验。实验数据为某 以A~八一 公安机关提供的8990篇社区民情民意文本,其文本符合大数 0.75 据的数据量大、数据种类多、类域交叉等多个特点,本实验将数 据分为三层、39个类别。文本类别与文本如图4-6所示。 签非 5000 文本类别 4000 图8KNN与nM-KNN查全率比较 餐3000 KNN 2000 DM-KNN 1000 0.85 治安隐患类居民需求类社区秩序类 0.75 文本类别 0.7 图4第一层 张红 1500 文本类别 1000 图9KNN与DM-KNNF1值比较 从以上实验可以发现,从查准率来看,采用DM-KNN算法 的查准率高于传统的KN算法,但是从查全率来看,改进后的 算法虽然整体上有所提高,但是提高得不是很明显,而且针对 一些稀有样本杳全率反而降低,因此采用了综合测试因子F1 文本类别 来评佔两种算法的精度。由图7可以看出 DM-KNN算法的精 图5第二层 度相比KNN算法有了显著提高,证明改进后的效果是令人满 意的。 HtitntiHt 实验2本实验把公安机关提供的8990篇社区民情民意 文本分为三份数据,分别为 Database、 Database2、 Database3。 其中 Database和 Database2分别包含3000篇文本, Database3 包含2990篇文本。然后分别采用KN和DM-KNN算法对其 进行分类,记录其分类用时并进行比较,实验结果如表1所示。 文不类别 表1KNN和 DM-KNN分类时间比较 图6第三层 KNN/s DM-KNN/S 3.2实验设置与结果分析 Datal用时 2617.9 1582.3 Daa2用时 2493.4 实验1木文就改进算法进行了实验。木实验使用了中 Daa3用时 2521 1423.9 科院提供的 ICTCLAS免费中文分词系统。首先从公安机关提 由表1可以看出,DⅥ-KNN算法在时间上胡显优于传统的 供的社区民情民意文本中随机抽出500份,由行业专家进行人KNN算法,是一种对于社区民情文本不仅准确率高且分类速 工分类,然后对此300份文本用文中的算法进行测试,循坏测度快的文本分类算法。 试三次,取平均值为测试结果。经过反复实验,最终确定KNN 算法中的参数k=17。分类效果评指标使用常用的查准率、4结束语 查全率以及F1测试值(对应方法的值以下标进行标注)。 倉准率=分类的正确文本数/头际分类文本数 随着信息化的深入发展、大数据时代的到来,如何有效地 查全率=分类的正确文本数/应有文本数 将网络技术和计算机技术融入到现实生活中,使其发挥作用 查准率×查全率×2 成为待研究的课题。在此背景下,木文提出了用于大数据分类 查准率+查全率 的改进KNN算法,以在合理的时间内从海量数据(下转第1373页) 第5期 吴学雁,等:基于分层动态时间弯均的序列相似性度量方法研究 1373 示每组数据使用两种方法分别得到的聚类精度。从图4中可 以看到,DTW方法得到的聚类精度的取值在0.65~0.9,而 结束语 HDTW算法得到的聚类精度的取值在0.75~0.9,并且除了第 本文提出和基于分层功态时间弯曲的序列相似性度量 10组数据之外,HDTW算法得到的聚类精度总是高于DTW算方法,对较长时间序列进行多层次的分段后再进行相似性度 法的。图5展示了10组数据的总平均聚类精度和运算时间的量,并在算法中充分考虑了时间序列的形态特征和趋势。实验 对比,从图5中可以看到Iw算法的结果是远远优于mTW结果证明,该方法具有较好的效果。 算法的,通过HDTW算法进行相似性度量得到的聚类精度比 DTW算法要高出近10%。另外,从运算时间来看,HDTW算法参考文献 与DTW算法相比大约减少了30%。 [Ⅰ』李海杺,郭崇慧.时间序列数据挖掘中特征表示与相似性度量硏 究综述[冂].计算机应用研究,2013,30(5):1284 二0.84 [2 KEOGH E Data mining and machine learning in time series databases 24 1600 [Cl//Proc of the 4 th IEEE International Conference on Data Mining. 0.55 800 0.74 l2345678910 DTW HDTW HDTW 平均聚类精度运算时间 [3 BERNDT D, CLIFFORD J. Lsing dynamie time warping to find pat- 图4两种算法在数据集1中图5两种算法在数据集1中的总 terns in time series C|//Proc of AAAI Workshop on Knowledge Dis- 的分组聚类精度对比 平均聚类精度和运算时冋的对比 coverv in databases. 1994. 359-371 2.2.3两种算法在数据隽2上的结果对比 [4 KEOGH E, PAZZANI M Derivative dynamic time warping[ C]//proe 图6展小了DTW算法和HDTW算法在每组数据上得到 of the lst slAM International Conference on Data Mining. 2U01: 1-11 的聚类精度的对比,横轴表示数据集2中的10组数据,纵轴表 5」陈肚利,李俊奎,刘小东.基于提前终止的加速时间序列穹曲算法 [J].计算机应月,2010,30(4):1068-1071 示每组数据使用两种方法分别得到的聚类精度。从图6中可 [6〗尚福华,孙达辰,吕海霞.提高DIW运算效率的改进算法[J].计 以看到,DW方法得到的聚类精度的取值在0.65~0.95,并且 算机工趕与设计,2010,31(15):3518-3520 不同的数据组得到的聚类精度的波动很大。HDTW算法得到[71 LEMIRE D. Faster retrieval with a two- pass dynamic time warping 的聚类精度的取值在0.8-0.9,并且不同的数据组得到的聚 lower bound[ J]. Pattern Recognition, 2009, 42(9): 2169-2180 类精度值波动较小.除了第7组数据之外,HDTW算法得到的8] MARTFAU P F. Time warp edit distance with stiffness adjuslment for 聚类精度总是高于DTW算法。图7展示了10组数据的总平 time series matching J. IEEE Trans on Pattern Anal d ma- 均聚类精度和运算时间的对比,同样,从图7中可以看到 chine Intelligence Archive, 2009, 31(2): 306-318 HDTW算法的结果优于DTW算法 [9]陈乾,胡谷雨.一种新的DTW最佳弯曲窗卩学习方法[J].计算 机科学,202,39(8):191-195. 坐0.88 4000 [l0]吴学雁,黄道平,莫赞基于极值点特征的时间序列相似性查询方 法[J].计算机应用研究,2010,27(6):2068-2070 800回 物C.78 [I1] GAVRILOV M, ANGUELOV D, INDYK P, et aL. Mining the stock 23456 DTW IIDTW markel: which measure is hesl[C//Prix of the Gth ACM SIGKDD 总平均娶类精度—运算时句 图6两种算法在数据集2中图7两种算法在数据集2中的总 Intermational Conference on Knowledge Discovery and Data Minin 的分组聚类精度对比 平均聚类精度和运算时间的对出 Boston: ACM Press, 2000: 487-496 (上接第1344页)中提取对企业或者社会有用的信息。而且实[6 TSANGI W, Kwok J T, CHEUNG P M. Core vector machines fast 验通过对社区民情民意文本进行分类,证明了该方法在对大数 SVM training on very large data setsLJ. Journal of Machine Learn 据分类时效果是令人满意的。 ng Research,2005,6:363-392 [7」蔡磊,程国建,潘华贤,等,分类大规模数揉的核向量机方法研究 参考文献 冂].西安石油大学学报:自然科学版 [l] YANg Yi-ming, PEDERSEN J O. A comparative study on feature se-[8]陈光喜,徐建,成彦.一种聚簇消减大規模敚据的支持向量分类算 lection in text categorization[C]//Proc of the 14th International Con 法[J].计算机科学,2009,36(3):184-188 ference on Machine Learning. 1997: 412-420 [9 YANG Yi-ming, LIU Xin. A re-examination of text categorization 2 CHAKRABARTI S, DOM B, AGRAEAL R, et al. Using taxonomy, dis- methods[C]// Proc of the 22nd Annual International ACM SIGIR criminants, and signature for navigating in text databases C//Proc of C and Development in Informatin Ret rieval the 23rd VLDB Conference. 1997. 446-455 Berkeley: ACM Press, 1999: 42-49 [3 NG H T, GOH W B, LOW K L Feature selection, perceptron learn 「10]江涛,陈小莉,张玉芳,等,基于聚类算法的KNN文本分类算法硏 ng and a usability case study for lext calegorizaion[ C 1//Proc of the 究[J].计算机二程与应用,2009,45(7):61-65 20th Annual International ACM SIGIR Conference on Research and [1]鲁婷,乇浩,姚宏亮.一种基于中心文档的KNN中文文本分类算 法[J].计算机工程与应用,2011,47(2):41-44 Development in Information Retrieval. 1997: 67-73 12 TAN Song bo. Neighbor-weighted K-nearest neighbor for unbalanced [4 JOACHIMS T. Text categorization with support vector machines text corpus[J]. Expert Systems with Applications, 2005, 28(4) learning with many relevant features[ C]//Proc of the 10th European (7-671 Conference on ML. 998:137-152 [13]郝秀兰,陶晓鹏,徐和祥,等.KNN文本分类器类偏斜问题的一种 15. YANG Yi-ming, CIIUTE C G An example-based mapping method for 处理对策「J.计算机研究与发展,2009,46(1):5261 text categorization and retrieval J 1. ACM Trans on nformation[14]李荣陆,胡运发.基于密度约KN文本分类器训练样本裁剪方法 Systems,1994,12(3):252-277 [J].计算杌研究与发展,2004,41(4):539-545

...展开详情
试读 4P 论文研究-用于大数据分类的KNN算法研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39841365 欢迎大家使用并留下宝贵意见
2019-07-22
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
最新推荐
论文研究-用于大数据分类的KNN算法研究.pdf 10积分/C币 立即下载
1/4
论文研究-用于大数据分类的KNN算法研究.pdf第1页

试读结束, 可继续读1页

10积分/C币 立即下载 >