基于云计算的数据挖掘

    一年多没有跟新我的博客了，回过头来看看，总觉得缺点什么，于是决定重新开始更新我的blog。这一年多，我经历了很多事情。当然，最主要的是思想观念的提高。言归正传，最近在做一个云计算的项目。“云计算”的概念我就不炒了，还是干点实事吧。我们这个项目主要是把云计算应用到电信企业的数据挖掘和知识获取上。至于主要内容，一方面是把一些经典的数据挖掘算法在并行计算平台上实现（主要是hadoop上），另一方面是研究具体的应用，以提供商业解决方案。

 

    至于具体算法，个人认为能否并行，也就是能否应用在Map/Reduce上，还是比较鲜明的。也就是说，有些算法一眼就能看出其并行策略，或很容易制定出并行策略，另外一些算法则很难并行，很少有那种很难断定能否并行的算法。下面列出的一些算法是我们已经实现的：

 

Association Analysis:

    Apriori

Classification:

    Nearest-Neighbor

    Naive Bayesian

Clustering:

    K-means

    Canopy

    Fuzzy K-means

Others:

    PageRank

 

   此外，我们还利用hbase做了一个抽取个人中心网络的应用，并用flex展示出来如下：

 

接下来还要实现一些算法，包括：

    Neural Network

    SVM

    Logistic regression

    Graph Mining

    Cluster Evaluation

    Sequence Patterns Mining

等。

 

这里把Mahout Goal post出来，做个对比，同时也知道我们分析：

    High-performance, distributed matrix (both sparse and dense)
    Clustering (Canopy, K-Means, Mean Shift, etc) with distancing (Manhattan, Pearson, Tanimoto, etc)
    Naive Bayes classification and Bayesian network
    Backpropogation (Neural Network)
    Expectation Maximization (e.g. Probabilistic Latent Semantic Indexing)
    Locally-Weighted Linear Regression (LWLR) and logistic regression
    Support Vector Machine
    Gaussian Discriminant Analysis
    Singular Value Decomposition, Principal Components Analysis, Independent Component Analysis

这其中有些我们已经实现了，不过还要继续努力。

<!---->

搭个云字不太确切， 叫 data intensive computing 比较恰当
你的工作跟mahout重的很多
SVM, Neural network mahout还没做，前者google有实现，虽然基于mpi，但改成mapreduce应该很容易
能做这么多东西，你的工作还是挺有意思的

不知道楼主怎么测试在hadoop之下的大数据集聚类效果呢?

to yingfeng
SVM, Neural network mahout还没做，前者google有实现，虽然基于mpi，但改成mapreduce应该很容易。

google张智威教授的通过并行化Incomplete Cholesky Factorization(一种矩阵分解)的方法实现了并行的SVM，此算法不适合在MapReduce模型。而且他的算法具有通用性,但目前不是最快的SVM算法，有些算法在单机执行会比PSVM还快很多倍。SVM类型及解法种类繁多，c-svm, v-svm, ls-svm等等，既可以通过原问题来求解,又可以通过对偶问题来求解。目前最有效的解法前后数据依赖性比较大。SVM的研究在这些年非常活跃,08年末就有几个很有质量的算法提出。

你的redpoll还进行吗，好像有段时间没更新了

我对psvm的实现比较有兴趣(不过还没阅读)，google 应当最初是基于map reduce，因为要开源，而c++的可用框架尚且没有，因此才修改为基于mpi开源出来的。
从理论上说， mpi和mapreduce的思考方式是有一定差异的，因为后者完全基于数据划分来思考，而前者则基于消息，至于是基于数据划分还是任务划分，倒是没有限制。 对于 psvm来说，它对于这么大矩阵的数据是怎么划分呢？难道是基于共享？也就是说一个大矩阵存放在一个dfs上，各节点按需索取数据？ 如果是这样的话，性能低下就不足为其了。那么猜测一下，google 内部会如何实现呢？Incomplete Cholesky Factorization我刚瞅了瞅，的确比较难以划分，应当说，这是个比较典型的All-pairs 问题。 而All-pairs问题，我所知道的解决方案，是用bigtable来存储大矩阵，这种方式的性能会如何，我觉得也很难说，毕竟这没有利用到文件的子块来进行有效的节点间任务调度，跟mpi的共享存储方案比较接近，只不过由于gfs对io做了一些优化而速度快一些

我感觉Google的map-reduce及其实现平台最重要的还是容错性，编程模型简单，适合作为底层平台为客户提供弹性的服务。相比之下如果是实验室内的科学计算，运行环境相对稳定，还是MPI比较合适。两个模型的应用场景不同。