我的读书笔记(一)：数据信息中的相似度计算算法

第一篇：我的读书笔记(一)：数据信息中的相似度计算算法

我的读书笔记

（一）：数据信息中的相似度计算算法

无意中发现这本貌似不错的书 Mining of Massive Datasets，随便记一下学到的东西。因为对数据挖掘没什么研究，理解肯定很肤浅，请过往大牛指教。下面内容来自此书第三章的前面部分。

在数据挖掘中经常需要用到比较两个东西的相似度。比如搜索引擎要避免非常相似的文档出现在结果的前几页，再比如很多网站上都有的“查找与你口味相似的用户”、“你可能喜欢什么什么”之类的功能。后者其实是很大的一块叫做“协同过滤”的研究领域，留待以后详谈。

首先我们定义两个集合S,T的Jaccard相似度: Sim(S,T)= |S,T的交集| / |S,T的并集|。直观上就容易感觉出这是一个很简单而且比较合理的度量，我不清楚有没有什么理论上的分析，在此省略。下面先主要说一下文档的相似度。

如果是判断两个文档是否完全相同，问题就变得很简单，只要简单地逐字符比较即可。但是在很多情况下并不是这样，比如网站文章的转载，主体内容部分是相同的，但是不同网页本身有自己的Logo、导航栏、版权声明等等，不能简单地直接逐字符比较。这里有一个叫做Shingling的方法，其实说起来很圡，就是把每相邻的k个字符作为一个元素，这样整篇文档就变成了一个集合。比如文档是“banana”，若k=2，转化以后得到集合为

{“ba”,“an”,“na”}，于是又变成了前述集合相似度的问题。关于k值的设置，显然过小或过大都不合适，据说比较短的比如email之类可以设k=5，比如长的文章如论文之类可以设k=9。

当然，这是一个看上去就很粗糙的算法，这里的相似度比较只是字符意义上的，如果想进行语义上的比较就不能这么简单了（我觉得肯定有一摞摞的paper在研究这个）。不过同样可以想见的是，在实际中这个粗糙算法肯定表现得不坏，速度上更是远优于复杂的NLP方法。在实际工程中，必然糙快猛才是王道。

有一点值得注意的是，Shingling方法里的k值比较大时，可以对每个片段进行一次hash。比如k=9，我们可以把每个9字节的片段hash成一个32bit的整数。这样既节省了空间又简化了相等的判断。这样两步的方法和4-shingling占用空间相同，但是会有更好的效果。因为字符的分布不是均匀的，在4-shingling中实际上大量的4字母组合没有出现过，而如果是9-shingling再hash成4个字节就会均匀得多。

在有些情况下我们需要用压缩的方式表示集合，但是仍然希望能够（近似）计算出集合之间的相似度，此时可用下面的Minhashing方法。

首先把问题抽象一下，用矩阵的每一列表示一个集合，矩阵的行表示集合中所有可能的元素。若集合c包含元素r，则矩阵中c列r行的元素为1，否则为0。这个矩阵叫做特征矩阵，往往是很稀疏的。以下设此矩阵有R行C列。

所谓minhash是指把一个集合（即特征矩阵的一列）映射为一个0..R-1之间的值。具体方法是，以等概率随机抽取一个0..R-1的排列，依此排列查找第一次出现1的行。

例如有集合S1={a,d}, S2={c}, S3 = {b,d,e}, S4 = {a,c,d}，特征矩阵即如下

S1S2S3S4

0a1001

1b0010

2c0101

3d1011

4e0010

设随机排列为43201(edcab)，按edcab的顺序查看S1列，发现第一次出现1的行是d(即第3行)，所以h(S1)= 3，同理有h(S2)=2, h(S3)=4, h(S4)=3。

此处有一重要而神奇的结论：对于等概率的随机排列，两个集合的minhash值相同的概率等于两个集合的Jaccard相似度。

证明：同一行的两个元素的情况有三种：X.两者都为1；Y.一个1一个0；Z.两者都为0。易知Jaccard相似度为|X|/(|X|+|Y|)。另一方面，若排列是等概率的，则第一个出现的X中元素出现在Y中元素之前的概率也为|X|/(|X|+|Y|)，而只有这种情况下两集合的minhash值相同。

于是方法就有了，我们多次抽取随机排列得到n个minhash函数h1,h2,…,hn，依此对每一列都计算n个minhash值。对于两个集合，看看n个值里面对应相等的比例，即可估计出两集合的Jaccard相似度。可以把

每个集合的n个minhash值列为一列，得到一个n行C列的签名矩阵。因为n可远小于R，这样我们就把集合压缩表示了，并且仍能近似计算出相似度。

在具体的计算中，可以不用真正生成随机排列，只要有一个hash函数从

[0..R-1]映射到[0..R-1]即可。因为R是很大的，即使偶尔存在多个值映射为同一值也没大的影响。

文章由超级p57官方网站http:// 整理发布

第二篇：基于属性重要度约简算法在数据挖掘中的应用研究论文

摘 要：属性约简是粗糙集理论研究的核心内容之一，本文通过对属性重要度的计算，以核为基础计算条件属性集中除核以外其他属性的重要性来确定最小的约简，最后通过实例分析验证了算法的有效性与可行性。

关键词：数据挖掘 属性约简 重要度

数据挖掘是从海量的且不断动态变化的数据中，借助有效的方法挖掘出潜在、有价值的知识过程。而粗糙集理论它是一种刻画不完整性和不确定性的数学工具，能在保持分类能力不变的前提下，通过知识约简从中发现隐含的知识，揭示潜在的规律，是由波兰科学家Pawlak在1982年提出的。而属性约简是粗糙集理论研究的核心内容之一，它能保证在分类能力不变的情况下，消除重复、冗余的属性和属性值，减少数据挖掘要处理的信息量，提高数据挖掘的效率。本文提出了通过计算单个属性的重要性，以重要性大于零的属性为核，来选取其它属性加入核中形成新的集合RED，直至剩下的所有属性的重要性为零，得到的集合REDn即为属性约简。粗糙集的基本理论[1-2]

定义1设 是一个信息系统，其中 是对象的非空有限集合，即;是属性的非空有限集合;，是属性 的值域;是一个信息函数，即每个对象在每个属性上对应的信息值。若，其中 为非空有限条件属性集合，为非空有限决策属性集合，且，则称信息系统为决策表。

定义2对决策表，，考虑单决策属性的情况，即，则的分辨矩阵是一个 矩阵，其中的元素定义如下：

定义3对分辨矩阵中每个，用布尔函数 来表示，若，则决策表的分辨函数 可定义为：。基于粗糙集的数据挖掘的属性约简算法[3-4]

2.1 算法分析

第一步：求核。通过求条件属性C中的每个属性a对在整个条件属性集C的重要性SigC(x)来确定属性核CORE(x)，重要性SigC(x)>0的属性为核属性。

第二步：通过向属性核CORE(x)中依次加入重要性大的属性来确定属性集x的最小约简，详细步骤如下：(1)把a加入到属性集R 中，计算重要性，选择重要性最大的属性;(2)如果两个属性有相同的重要性，取离散值小的属性。

2.2 算法复杂度

通过算法的分析，在对决策表进行划分的时间复杂度为O(n2)。而计算条件属性的重要性也是满足划分的线性关系，因此所求属性核的时间复杂度为O(n2)，依次添加次重要度的属性也没有增加额外的开销，因此整个时间复杂度还是O(n2)。

2.3 实例及分析

为了进一步验证算法的可行性，下面以表1中的决策表为例进行分析说明，其中对象集，条件属性集，决策属性。

以上对计算出的实验数据的重要性进行统计得出信息系统的两个约简为{c1,c4}和{c2,c4}。结语

本文针对属性约简算法中的属性重要度的计算来确定核，适合对海量数据的挖掘，不仅节省了存储空间，而且在时间复杂度开销少，通过实验分析验证了算法的可行性与有效性，为决策表的属性约简提供了一条高效的途径。

参考文献：

[1]张文修,吴伟志.粗糙集理论与方法[M].北京:科学出版社,2001:18-19

[2]周献中,黄兵，李华雄,等.不完备信息系统知识获取的粗糙集理论与方法[M].南京:南京大学出版社,2010:10-11

[3]饶泓,夏叶娟,李娒竹.基于分辨矩阵和属性重要度的规则提取算法[J].计算机工程与应用，2008,44(3):163-165

[4]黄国顺,刘云生.一种改进的决策表属性重要性及其快速约简算法[J].计算机工程与应用,2007,43(28):173-176