数据挖掘（协同过滤、关联推荐、聚类分类）一些资料

   协同过滤关联推荐的话目前大家可以参考亚马逊网上书店的效果，总感觉当当网什么都没有给我推荐过滤过，倒是China-Pub命中过一次（置信度100%啊，只向我推荐过一次 :) 就忽悠我把《什么是数学》给买下来了，还是以比当当网贵20%的价格啊），按理来说当当网在数据的支持上，是要比China-pub丰富不少的，我经常去当当，而且在当当也购买了金额超过1000的书籍了，居然人家还没抓住我想要什么（还有很多我在当当的浏览搜索记录），相反China-pub我就去过那么一两次买过一次书最后因为所获得问题交易还没有成功 :),看来当当要加油啊！其实在Item-Based、User-Based上当当都是在国内拥有最丰富的数据了，结果也非常好评估啊！

    前天刚好做了一个用户兴趣度、吸引力的分析，由于只是一个演示模型，让我看看速度和结果，所以也就是用的Java+稀疏矩阵+行列相似性（Consin相似度来处理的），感觉还不是特别麻烦啊，处理速度和结果感觉也都还可以。（当然前期做了大量的数据调整工作，恩，确实数据质量决定了最后的结果，所以数据预处理、调整、规整上多花点时间是相当值得的）。真要好好做的话很多地方都要很细致的考虑了，为了效率最后应该会用C来实现，数据量太大的时候（大到你无法想象，光是维数就超过你的内存的时候就要考虑分块处理了，可以参考我以前的PageRank的计算时候所用到的一些解决办法）；然后感觉这里相似度的计算又回到了我熟悉的文本相似的问题上来了，看来算法、思想都是相同只是用在不同的地方，然后需要进行一下预处理变换，规整到余弦定理上来啊:)

 

第一个最重要的关联算法Apriori algorithm（要特别注意里面的枝剪的处理，要不复杂度就膨胀得很厉害的。尽管扫描次数太多效率不高，接下来自己可以不断解决的）(抄的一段话：Agrawal等引入了修剪技术（Pruning）来减小候选集Ck的大小，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。文[6]中，还引入杂凑树（Hash Tree）方法来有效地计算每个项集的支持度。

3.1.2频集算法的几种优化方法
虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。

1.         基于划分的方法。Savasere等[14]设计了一个基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在[2,11,17]中找到。

2.         基于hash的方法。一个高效地产生频集的基于杂凑(hash)的算法由Park等[10]提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。

3.         基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法，Mannila等[8]先考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由Toivonen[16]进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham在[7]中讨论了反扭曲(Anti-skew)算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次数少于2次，算法使用了一个采样处理来收集有关数据的次数来减少扫描遍数。

Brin等[4]提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项集时，一旦我们认为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生“相关规则”（Correlation Rules）的一个新方法，这是基于他们的[3]工作基础上的。

4.         减少交易的个数。减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的大项集，则必然不包含长度为k+1的大项集。从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个数。这个就是AprioriTid的基本思想

)

当向量描述不是Boolean（二元的，一般用0，1来表示）的时候你可能需要Slope One来简单地解决这个问题

Weka Java实现的一个比较完整的Data Mining包，做原型还是Java的多啊，比如Lunece，呵呵，当年看的一点Java还是能派上用处的

复旦大学的数据挖掘讨论组还是蛮不错的，呵呵主要带头人就是写《数据挖掘》那本是的朱老师:),这个网站我关注有好几年了，入门不错的！

Taste Java实现的一个实现了主要的推荐算法的包（又是Java），主要介绍非常详细，有很好的Demo，值得一看，然后你可以在这个基础上不断改进揉入你的特定需要，在这种情况下尤其感觉数据与处理的重要性了

聚类算法：K-means(可以做一些改进)，当然还有效果更好不过复杂度更高的K-medoids算法（真正工程应用不现实，我看了看复杂度还是可以简化一下的，不过对边界孤立点就又要敏感一点了，两难全啊），当然真正大规模数据的时候可以随机抽样来确定K个中心，这样就可以不怎么考虑复杂度了！

还有非常典型的贝叶斯定理（我那大学概率啊）在分类、统计上的应用（例子：用贝叶斯定理来进行分类）

KNN：In pattern recognition, the k-nearest neighbor algorithm (k-NN) is a method for classifying objects based on closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification. It can also be used for regression.（从Wili上扒拉过来的一段话），简单的说KNN就是从已知的分类中找出和要分类的目标最近的几个点，然后看这几个点在哪个类别中占的比重多就认为目标也在这个类别中，简单吧

其实这个方向再配合上对数据的敏感度+海量数据处理能力（做搜索的锻炼得比较多吧）还是很有趣的，下次再补充。

评论

1 楼 yajie 2009-05-24  

写的一知半解，丁你个费！