关于redpoll中使用mahout模块,而没有沿用其中算法的解答

接到mail, 公布出来省得再有提问 :)

 

 

首先, 我要实现的canopy和kmeans算法都是固定的,本来我不必要重新实现这些算法。我是暂时加入mahout-*.jar,因为里面的SparseVector,省得我再去实现一遍。

但我没用其中的算法,　因为我去年就发现mathout的实现有以下以个问题:

 

1. 它的CanopyMapper默认读取的是SparseVector.asFormatString之后的字符串形成的Text。我估计他们没有做过大数 集的测试，因为这个String占的空间非常大。SparseVector的每个元素由index和value组成, index是int型占4字节, value是double型占8字节, 他们转成字符串加起来远不止12字节。这势必会造成空间上的膨胀，事实上我测试过用一个4.1m的新闻分词后，如果采用这种形式建立VSM，将是11M.

2. 他们对Canopy算法的理解有误区。这是canopy提出者的原文http://www.kamalnigam.com/papers/canopy-kdd00.pdf
注意它摘要的话:
The key idea involves using a cheap,approximate distance measure to efficiently divide the data into overlapping subsets we call canopies. Then clustering is performed by measuring exact distances only between points that occur in a common canopy .
作者提出的这两点，第一点mahout是采用命令行参数指定的Distance Measure，这很灵活，虽然使用者可能不懂canopy,没体现cheap这特点，但也不能说mathout有错。　关键是第二点，在k-means 这一步只需要计算出现在同一canopy中所有数据点的精确距离。这是canopy之所以高效至关重要的一点。这一点，mathout的代码没有体现。事 实上我去年打过patch给他们，由于我对apache的format不熟，而且没有写JUnit相关的test,所以没有被接受。我怀疑mahout的 canopy实现作者只看过google的那段canopy视频。

3. 注意mathout中org.apache.mahout.clustering.canopy.Canopy这个类中的计算canopy质心的方法:

	public Vector computeCentroid() {
		Vector result = new SparseVector(pointTotal.cardinality());
		for (int i = 0; i < pointTotal.cardinality(); i++)
			result.set(i, new Double(pointTotal.get(i) / numPoints));
		return result;
	}

 它构造一个稀疏矩阵,　但这个矩阵每个元素都是赋了值的，就算是为0也赋值。用SparseVector去存，反而会极大地增大其容量。再者在大规模数据中，词条向量应该会有百万级别的元素，这样存太没道理了。加上按照刚才1. 中指出的存成String，光存一个canopy质心就可以达到数百K字节.

4. 如果读者测试了mathout的Naive Bayes关于20_newsgroups的示例，你会发现它根本不能工作。代码不能工作就提交上去。我们作了一些改动，结果它的算法精确度非常之低，结 果自己重写了，当然也避免重复劳动，用了些mahout已有的代码。对搜狐新闻，拿Je MMAnalyzer分词器分词，分类精度提到90.2%。另外，也是存储空间的问题, 20_newsgroups解压下来只有90.4MB，这当然不会有问题。但它计算词频采用的key是label, term,代表类与词;value是这个类中该词条的词频。有时候数据集大了词条非常多，在我的实验当中多至数百万，而且类有N个的话。那么它要数百 万*N个记录。这一点完全可以避免。

评论

2 楼 diddyrock 2009-08-20  

nutch 也没有实现排序算法，其实有很多时候扯淡是存在的

1 楼 conservatism 2009-03-03