MLLib Issue整理

优化部分

ADMM

SPARK-1543 实现了ADMM框架，依靠它可以实现很多的机器学习算法(L1-logistic regression, lasso, SVMs)，作者把这个issue关闭了，还有一些实现的细节没有讨论清楚。除了作者的PR，社区有人另外实现了另外一个版本

ADMM需要保持关注。

使用ADMM和IPM来进行ALS非负矩阵分解

OWL-QN算法

SPARK-1892， OWL-QN算法是L-BGFS算法的一个变体，更适合L1正则的优化问题。

TFOCS算法

SPARK-1503，和梯度下降法一样也是一阶展开，比梯度下降算法收敛快很多，实现出来和SGD与L-BGFS比较。

新增算法

支持稀疏矩阵(CCS)和更多的BLAS操作

SPARK-3418，支持3级的矩阵运算，以及稀疏矩阵。

分布式的块矩阵以及分布式矩阵乘法

SPARK-3434， SPARK-3435，要尽量减少通信开销。 Intel研究院的尹旭森在今年暑假指导过南京大学的顾荣完成了一个版本，项目的Github，以及报告。

KNN分类和回归

SPARK-2335， SPARK-2336, 说好的实现呢？

统一距离接口

SPARK-3102 统一各种距离（欧式距离，曼哈顿距离）的计算到一个接口, 用于其他的算法实现。

多个模型同时训练

SPARK-1486 SPARK-2372

每一种类型的算法一个统一的接口

SPARK-3507, 这样更方便测试新的算法，Databricks内部正在实现。

SPARK-2430，统一聚类接口。

SPARK-3702， Databricks公司正在进行的大改动，统一MLLib中的所有算法，重新定义了类型的层次结构。

多分类的逻辑回归

SPARK-2309 现在MLLib中的LR只支持二分类，可以简单的扩展公式实现多分类，不过通用的GeneralizedLinearModel需要修改，作者提的PR不知道为什么突然关掉了，应该是GitHub的bug。

标注(tag)问题

标注问题属于监督学习的一种，对于一个输入X，输出的y是一个向量，表示x的tag。 SPARK-2401，还没有实现。

SVM使用RBF核

SPARK-3692

高斯混合模型

SPARK-3588，已经有人实现了PySpark的版本，只需要改成Scala版。

层次化聚类

SPARK-2429，社区正在实现。

自动推测类的数目

SPARK-2206 现在的决策树需要用户输入numofClasses，可以根据数据自动检测类的数目，预计实现在1.2版本中。

分布式PLSA

SPARK-2199，现在有研究说明PLSA比LDA有时性能更好，这个PR已经通过了单元测试，应该会被合并。

Fuzzy C-Means聚类算法

SPARK-2344

Robust线性回归

SPARK-3181, 普通的线性回归使用least square作为loss function，这基于错误时正态分布的假设，对于长尾的错误不成立，需要使用Robust Regression。

优化ALS内存使用

SPARK-3561, 现在的ALS使用了很多的小对象，增大了GC的压力，使用原生数组来保存数据。

特征离散化

SPARK-1303 SPARK-1216

这两个issue的PR现在都没有人管， GitHub上面的状态显示有错误(Error — The Travis CI build could not complete due to an error)，他们提交的代码的时间已经很久了，可能是和Spark现在API不兼容导致的。

特征选择

SPARK-1473，还是用卡方测试的方式进行特征选择，卡方测试已经发布到了1.1版本，这个PR不知道为什么没有合并。

决策树

Random Forest

Gradient Boosting

SPARK-1547 SPARK-3525

现在还没有开始实现，预计在随机森林之后。

现在社区有人实现了一个版本：https://github.com/apache/spark/pull/2394，以及commitor实现的版本： https://github.com/manishamde/spark/compare/gbt?diff=unified

AdaBoost

一些性能改进

SPARK-3158，在父节点分隔的时候计算好子节点的impurity信息，下一层可以直接使用，避免重复计算。

SPARK-3159，如果分隔的两个子节点的predict值一样，就不进行分隔了。

分布式地计算bestSplit

SPARK-3366, 现在发现大部分的时间都用在aggregate上面，如果能够在各个executor完成bestSplit的计算， driver就不会成为性能的瓶颈。或许一开始的设计就有一点问题，应该按照节点把计算量划分，数据相应跟着节点划分，然后在executor完成节点的bestSplit的计算。这个需要考虑得深入一些。重点跟进一下。

K-Means

K-Means现在的版本有些慢：

MiniBatch K-Means

SPARK-2308，有一个人实现Minibatch的K-Means，但他不满足只提一个PR，他说已经重写了K-Means，好厉害的样子。

KMeans性能改进以及bug修正

SPARK-3218, SPARK-3219, SPARK-3261, SPARK-3424，增加了新的距离度量，减小了一轮迭代的时间复杂度。

评估方法

评估ranking

SPARK-3568

评估多分类

SPARK-2329，虽然现在就只有决策树实现了多分类。社区应该抽象出一个One-VS-All类似的框架，利用这个组合二分类器实现多分类，只要实现本地版就行，像scikit-learn中一样。

Bug

和本地BLAS的兼容性

SPARK-3403，因为在Spark中一个task是一个线程，如果调用多线程版本的BLAS就会造成冲突。

接口大改动

SPARK-3530

未完待续。

chouqin / daily-spark

MLlib的JIRA #1