维数约减算法研究及其在大规模文本数据挖掘中的应用

摘要

随着网络的快速发展，人们处在这个“信息爆炸”的时代，常常面对海量数据分析和处理的任务，且这样的数据仍在以几何级数增长。同时，在现实中这些海量数据往往又是高维而稀疏的，且存在着大量的冗余。因而能对高维海量数据做压缩处理，且保持其内在属性的有效处理方法成为人工智能、机器学习、数据挖掘等领域的重要研究课题之一。高效的维数约减算法是对高维海量数据处理的一种有效方法，且具有一定的实际应用价值。本文的关注点集中在适用于高维海量数据的快速维数约减算法的研究及其具体应用。 本文分别提出了两种新的维数约减算法：（1）基于期望扰动的直接随机映像算法（On the Expected Distortion Bound of Direct Random Projection，简称DRP）；（2）基于锚点集的最小平方误差等距嵌入算法（Anchor points based Isometric Embedding under least square error criterion，简称AIE）。 基于期望扰动的直接随机映像算法DRP具有O（dn）的时间复杂性，这样的性能评价是建立在对期望扰动分析的基础上的。并证明了1）DRP算法的期望扰动的界。2）在适当的给定条件下，可在O（1）的随机时间内找到一个将期望扰动限定在一个合适范围之内的DRP映像。进而提出了一种获得中肯DRP的启发式算法。此算法具有稳固的渐进加速比，相对于其他随机映像算法具有更好的稳定性。而且在流数据模式下，可采用增量策略，DRP算法的时间复杂性为O（d log d）。 基于锚点集的最小平方误差等距嵌入算法AIE具有O（n log（n））的时间复杂性，而且在获得测地线距离后的计算时间复杂度达到对嵌入点数的线性关系，且可以完全并行实现。与Isomap、LLE等非线性维数约减算法相比较，具有更优化的时间复杂性。 当前主流的搜索引擎根据查询词在网页中的出现频率，辅以网页权威性等信息，生成查询结果。但用户提供的查询词往往非常简单，在许多情况下，搜索引擎难以确定用户的查询意图。本文提出了一种利用Web日志中的海量点击数据进行网页内容相关性挖掘的方法，在此基础上给出了一种反馈式搜索引擎（Feedback Search Engine，简称FSE）框架及相关算法。FSE根据网页相关性动态生成查询结果，以期提供给用户更中肯和个性化的信息。

目录

文摘

英文文摘

声明

第一章 绪论

1.1研究背景和研究目的

1.2研究现状

1.2.1机器学习

1.2.2维数约减

1.2.3 Web挖掘及搜索引擎的研究

1.3本文主要研究内容

1.4本文组织结构

第二章 机器学习和数据挖掘

2.1机器学习

2.1.1机器学习定义

2.1.2机器学习的研究内容

2.1.3机器学习的分类

2.1.4流形和流形学习

2.2数据挖掘

2.2.1数据挖掘中的相关概念

2.2.2数据挖掘的基本过程和过程模型

2.2.3数据挖掘的基本功能

2.2.4数据挖掘的典型应用

第三章 线性维数约减算法的研究

3.1主要线性维数约减算法简介

3.1.1主成分分析法(PCA)

3.1.2经典多维尺度分析(CMDS)

3.1.3小结

3.2随机映像算法

3.2.1随机映像算法概述

3.2.2随机映像算法理论

3.3基于期望扰动的直接随机映象算法DRP

3.3.1算法的提出

3.3.2主要结论

3.3.3引理3.2的证明

3.3.4.一种获得中肯DRP的启发式算法

3.4算法比较实验

3.4.1实验设置

3.4.2基于人工生成数据集的实验

3.4.3基于文献数据集的实验

3.5算法讨论

第四章 非线性维数约减算法的研究

4.1主要非线性维数约减算法简介

4.1.1等距映射算法(Isomap)

4.1.2局域线性嵌入(LLE)

4.1.3拉普拉斯特征映像(Laplacian Eigenmaps)

4.1.4随机邻域嵌入(SNE)

4.1.5小结

4.2基于锚点集的最小平方误差等距嵌入算法AIE

4.2.1算法的提出

4.2.2算法证明

4.2.3算法复杂性分析

4.2.4自适应邻域选择算法

4.3算法比较实验

4.3.1基于无噪声Swiss数据集的实验

4.3.2基于伪自由度噪声Swiss数据集的实验

4.3.3基于贯通型噪声Swiss数据集的实验

4.4算法讨论

第五章 基于内容相关性挖掘的反馈式搜索引擎框架

5.1搜索引擎技术现状

5.2 FSE框架的提出

5.3 FSE系统框架

5.4网页相关性矩阵

5.5两种计算概率可达性的算法

5.5.1基于最大可靠路的概率可达性算法

5.5.2基于Markov chain Monte Carlo(MCMC)的概率可达性算法

5.6实验

5.6.1使用DRP算法基于真实数据的实验

5.6.2使用AIE算法的仿真实验

第六章 总结与展望

参考文献

发表论文和科研情况说明

致 谢