普适环境下轻量级垂直搜索中数据挖掘理论研究

摘要

在追求“以人为本，如影相随”普适环境下，由于人所携移动设备、手持设备及提供普适计算服务环境的特殊性，给传统垂直搜索带来了新挑战。在诸多的挑战中，针对适合普适计算环境下的轻量级垂直搜索，我们选择了垂直搜索必须的分类理论以及推荐理论展开了研究。在分类理论中，研究围绕分类理论两个重要的问题展开:如何寻求一种优秀的特征提取方法和探索出能适合普适计算应用的分类器算法。而在推荐理论中，针对普适计算需求实时响应的特点，侧重于能提高推荐精度而又能提高其推荐速度的推荐算法的研究。其主要贡献体现在以下几个方面:
　　 1)针对传统潜在语义LSI(Latent Semantic Indexing)降维模型，提出了一种奇异值矩阵的调整算法。我们推荐的基于该算法的LSI降维公式，给奇异值矩阵一个正强化形式的权重。因为运用雅克比定理，我们能揭示出，赋予反强化形式权重的传统降维公式会过早出现性能下降，在高维上降维性能差，这些缺点源自于Lanczos近似算法不精确性。我们的调整算法能有效地降低反强化形式权重带来的冲击。同时，我们运用雅克比定理展现出，现存的多种降维公式，可以归结到如何去选择SVD空间下的一个向量，从而消除了不同LSI降维公式以及不同解释带来的疑惑。三个测试集上测试结果表明，在不增加计算复杂度前提下，调整算法不仅可以提升传统LSI降维公式在文本分类上的性能，而且我们建议的LSI降维公式在性能也能超过最新算法SVR(Singular Value Rescaling)。
　　 2)提出了一种高性能的快速降维理论—不精确谱系分析。该降维仿效单边雅克比(Jacobi)算法模型，根据一个向量的模值，来对一个原始矩阵进行排序，然后按照模值大小，直接选择近似矩阵来替代原始矩阵，原空间下一向量直接与近似矩阵相乘，得到降维的向量。运用支持向量机，通过简单的推理，我们发现，不精确谱系分析在降维功能上等价于潜在语义分析(LSI)中的一个降维公式。我们实验验证了该LSI降维公式在降维中的可行性，从而也验证了不精确谱系分析在理论上的可行性。而且，我们给出该方法降维带来的误差。三个测试集上的测试结果一致表明，不精确谱系分析极快的降维效果可以达到或超过经典LSI降维公式。
　　 3)提出一种基于错误反馈和调整的推荐算法。我们将向错误学习的方法引入协同过滤（Collaborative Filtering）领域，用于改进最基础的推荐算法。在行推荐算法UPCC(User-based Pearson Correlation Coefficient)中，我们引入并定义预测误差，根据UPCC实际值和预测值的差值作为一个用户预测误差。我们用列推荐算法IPCC(Item-based Pearson Correlation Coefficient)来预测一个用户的习惯性的偏差。在实际使用UPCC预测用户在一个项目(Item)上的偏好时，我们用预测值减习惯性偏差，得到最后的用户可能偏好。四个测试集的测试结果一致表明，用户提供的样例数目超过五个时，预测一个用户习惯性偏差可以有效补偿UPCC预测方法本身不精确的缺陷。
　　 4)提出了一种有偏放大法用于提升列推荐算法(IPCC)的推荐精度。在列推荐算法(IPCC)上试图使用个例放大法(Case Amplification)时，我们发现，当只有一个项(Item)时，传统的个例放大法会给仅有的一个项过多的权重(100％)，去预测用户在其他项上的偏好。这样反而会降低列推荐算法(IPCC)推荐的精度。导致推荐精度降低的原因是在分子和分母上放上同等权重值。我们提出的有偏放大法保持分子和分母不同放大权重，来克服这一缺点。同时，我们引入用户的样例数目作为一个调节器，由调节器来自动分配预测公式中分子和分母的放大权重，当用户的样例数目很少时，有偏放大法将降低现有样例的依赖，当用户提供的样例相对较多时候，有偏放大法能自动调整权重，增加对于用户提供样例的依赖。四个测试集的测试结果表明，我们在可以不增加IPCC计算负担的基础上，有效地提高IPCC算法的推荐精度。
　　 5)提出了一种半稠密法来加速支持向量机训练和分类速度和推荐算法的推荐速度。我们发现并能揭示，目前最新的两个向量对比的稀疏算法存大量在重复遍历的场景。我们提出半稠密算法来克服重复遍历的缺陷:将被选择的稀疏向量先就近稠密化，然而保持其他稀疏向量的稀疏性。在进行批次对比过程中，重复遍历被选择稀疏向量的缺陷被就近的稠密化向量所解决，重复判断的缺陷也由此解决。半稠密法被用在线程加速上。针对半稠密法的特点，我们包装了一个线程池，用于多线程间加速。而在进程级别上，我们采用读取共享压缩文件的方法取代消息传递。我们选择被业界认同很耗时的列推荐算法(IPCC)作为加速对象，在四个测试集上，加速效果很好。
　　 在垂直搜索上的实践表明，我们提出的挖掘理论能有效地服务于实践。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 本课题的历史与现状

1．2．1 垂直搜索

1．2．2 垂直搜索与综合搜索

1．2．3 问题呈述与切入点选择

1．3 本文主要研究内容

1．4 本文组织结构

第二章 相关背景知识介绍

2．1 文本分类一般过程

2．1．1 文本预处理

2．1．2 特征降维

2．1．3 文本表示

2．1．4 分类器选择

2．1．5 分类性能评价

2．2 支持向量机SVMTorch

2．3 稀疏矩阵上的SVD近似算法Lanczos

2．4 推荐一般过程

2．4．1 行推荐与列推荐

2．4．2 测试集

2．4．3 评价标准

2．5 本章小结

第三章 潜在语义检索

3．1 基于SVD的潜在语义

3．2 LSI投影模型公式

3．3 dlsi=dTUΛ-1精度问题

3．4 大稀疏矩阵上的SVD

3．5 雅克比分解

3．5．1 雅克比简介

3．5．2 LSI与PCA

3．6 经典LSI降维公式中奇异值矩阵Λ影响分析

3．7 投影模型dlsi=dTUΛl-1

3．8 正则化下的投影模型

3．9 实验验证

3．9．1 测试集和参数设置

3．9．2 总体比较

3．9．3 RSVD-1 vs．SVD-1

3．9．4 RSVD1 vs．SVD1

3．9．5 参数b

3．9．6 讨论

3．10 小结

第四章 不精确谱系模型

4．1 背景

4．2 相关工作及问题的提出

4．3 不精确谱系

4．3．1 构造类间正交趋势的初始矩阵H

4．3．2 ISA的原理

4．3．3 ISA的误差分析

4．3．4 ISA中整合形心向量

4．4 分类上的实验验证

4．4．1 测试集和实验设置

4．4．2 实验效果总览

4．4．3 LSI降维公式dlsi=dTUΛ的降维效果

4．4．4 SVD1 vs．ISA

4．4．5 ISA和EISA降维生成文档的稀疏性比较

4．4．6 性能开销

4．4．7 不同计分构造初始矩阵H对降维效果影响

4．5 小结

第五章 用错误反馈提升推荐精度

5．1 问题提出及相关工作

5．2 错误反馈机制提升推荐精度设计

5．2．1 抽取预测误差

5．2．2 预测习惯性偏差

5．2．3 FPCC算法复杂度分析

5．3 实验验证

5．3．1 试验目标

5．3．2 参与对比的实验方法

5．3．3 测试集和参数设置

5．3．4 推荐精度对比

5．3．5 结果分析与讨论

5．4 小结

第六章 有偏放大法提升列推荐精度

6．1 问题的背景

6．2 问题提出

6．3 不均衡放大技术

6．3．1 为列项CF算法设计的有偏放大法

6．3．2 预测公式分子和分母上有偏放大

6．3．3 有偏放大法原理法原理分析

6．3．4 有偏放大法中的调节器

6．3．5 有偏放大法复杂度分析

6．4 实验设计

6．4．1 试验目标

6．4．2 参与对比的实验方法

6．4．3 数据集以及实验设定

6．5 实验评估

6．5．1 推荐精度总览

6．5．2 有偏放大法与个例放大法

6．5．3 率定参数b

6．5．4 率定参数q

6．5．5 扩展性和推荐速度

6．5．6 亮点总结

6．6 结论

第七章 用半稠密算法加速稀疏向量间批次运算

7．1 传统稀疏向量间向乘

7．2 半稠密算法

7．2．1 半稠密算法

7．2．2 半稠密算法实现

7．2．3 半稠密算法的性能分析

7．2．4 半稠密算法实现方式

7．2．5 讨论

7．3 基于线程池的半稠密算法

7．3．1 线程池设计和实现

7．3．2 在线程池上的半稠密算法

7．4 MPI下基于线程池的半稠密算法

7．5 用半稠密算法加速SVMTorch

7．5．1 问题的提出和切入点的选择

7．5．2 在SVMTorch中用半稠密算法替代经典稀疏算法方案

7．5．3 实验验证半稠密算法对SVMTorch加速效果

7．5．4 参数设定

7．5．5 加速效果

7．5．6 WebKB上的效果

7．5．7 20-newsgroup上的效果

7．5．8 实验结论

7．6 用半稠密算法加速协同过滤

7．6．1 问题的提出和切入点的选择

7．6．2 实验设计

7．6．3 测试场景和数据集

7．6．4 实验验证

7．6．5 实验结论

7．7 小结

第八章 总结与展望

8．1 理论应用及效果总结

8．1．1 校园搜索

8．1．2 学习搜索

8．2 本文工作总结

8．3 展望

参考文献

致谢

个人简历、在学期间的研究成果及发表的论文