期中检查（姜昊茗 PB13000422）

1. 工作总结

这个工作是基于暑假在伯明翰大学做情感分析时的一些思考。数据分析中常常会受限于数据集的不平衡性。而解决数据不平衡性的办法，主要可以分为数据层面，和算法层面两大类。常见的算法层面的解决方案有cost sensitive learning， ensemble learning。而对于效果较好的ensemble learning（如Adaboost.NC）在面对高纬度的大量数据时，由于学习算法复杂度很高在实际应用中会变得非常耗时。而高维大数据是的处理是非常有实际意义的，比如在Kaggle的一个关于航空公司微博评价的数据集中负情感样本远远高于中性情感和正面情感。这是一个NLP的任务，样本（每一条句子）的特征维数很大，而且总的数据量很大如果调用Adaboost之类的算法将非常耗时。另外一个解决途径是数据层面的解决方案，如常用的SMOTE算法。对数据运用SMOTE算法重采样之后建立简单的分类器就能达到较好的效果。但是在维数较高的情况下直接应用SMOTE算法，算法的表现并不理想。

所以这次毕业设计的目标是通过改进SMOTE算法使得算法能够快速准确地对高维大数据重采样。

由于R语言是数据分析最常用的平台之一。所以以R语言为平台，编写相应的R package以便使用。

目前为止地的工作主要是：

1.1 SMOTE算法

调研了R中已有的SMOTE算法，DMwR包最广为应用。利用MNIST对其进行测试，将‘0’视为少数类，其他数字作为多数类，对其进行200%的重采样，耗时约1.7小时。

参考http://r-pkgs.had.co.nz/学习，并在RStudio中建立R package开发环境，编写了Brute Force版本的SMOTE算法。测试效果与DMwR相近。

1.2 KNN算法

调研了相关的K邻近算法，包括对不同K邻近算法实现的比较。比如参考了重要的benchmark（https://github.com/erikbern/ann-benchmarks）

将经典的ANN库移植进入R语言环境。测试结果表明k-d Tree；Cover Tree对高维数据失效。其在MNIST上的测试结果与暴力搜索几乎一致。

根据benchmark，NMSLIB的效果最好，但由于其库文件比较繁杂，难以移植进R的环境。所以放弃。

参考了LargeVis（Jian Tang etc. 2016）相关工作，将改进的随机投影森林移植进入R包中。加速效果突出。将原来的1.7小时降到23秒。

1.3实验结果记录

Data Description: MNIST, minority: class'0', majority: others
60,000 records in total, 5,500 records for minority.
Oversample rate: 200%
Results
DMwR runtime: 1.795415 hours
Brute Force: 1.680842 hours
k-d Tree: 1.734261 hours
cover Tree: 1.69047 hours
rpforest: 26.4661 secs

2. 工作目标

现在算法速度上得到了很大的提升，希望对SMOTE算法改进去适应更高维度的数据。由于很高维数据是很稀疏的，所以容易受到噪声的影响，直接应用SMOTE算法的效果并不好。利用嵌入学习中的办法对数据进行降维是否可以达到更好的效果。目前希望通过Auto-encoder寻找可靠的低维表示，再在其上做SMOTE以提升算法的效果。也希望研究是否也可以针对任务的目标——不平衡数据集的重采样来修改自编码器的目标函数，以达到更好的效果。

接下来的工作主要是：
1. 完成Auto-encoder的实现。
2. 并寻找不同的数据集，不仅从时间的角度考虑算法效果，可以利用分类结果去考虑算法效果。做更加完备的实验。
3. 针对任务目标修改Auto-encoder的目标函数，期望达到更好的效果。可以利用将低维表示可视化以后，来看是否能找到突破口。