第一篇：我的讀書(shū)筆記(一)：數(shù)據(jù)信息中的相似度計(jì)算算法

我的讀書(shū)筆記

（一）：數(shù)據(jù)信息中的相似度計(jì)算算法

無(wú)意中發(fā)現(xiàn)這本貌似不錯(cuò)的書(shū) Mining of Massive Datasets，隨便記一下學(xué)到的東西。因?yàn)閷?duì)數(shù)據(jù)挖掘沒(méi)什么研究，理解肯定很膚淺，請(qǐng)過(guò)往大牛指教。下面內(nèi)容來(lái)自此書(shū)第三章的前面部分。

在數(shù)據(jù)挖掘中經(jīng)常需要用到比較兩個(gè)東西的相似度。比如搜索引擎要避免非常相似的文檔出現(xiàn)在結(jié)果的前幾頁(yè)，再比如很多網(wǎng)站上都有的“查找與你口味相似的用戶”、“你可能喜歡什么什么”之類(lèi)的功能。后者其實(shí)是很大的一塊叫做“協(xié)同過(guò)濾”的研究領(lǐng)域，留待以后詳談。

首先我們定義兩個(gè)集合S,T的Jaccard相似度: Sim(S,T)= |S,T的交集| / |S,T的并集|。直觀上就容易感覺(jué)出這是一個(gè)很簡(jiǎn)單而且比較合理的度量，我不清楚有沒(méi)有什么理論上的分析，在此省略。下面先主要說(shuō)一下文檔的相似度。

如果是判斷兩個(gè)文檔是否完全相同，問(wèn)題就變得很簡(jiǎn)單，只要簡(jiǎn)單地逐字符比較即可。但是在很多情況下并不是這樣，比如網(wǎng)站文章的轉(zhuǎn)載，主體內(nèi)容部分是相同的，但是不同網(wǎng)頁(yè)本身有自己的Logo、導(dǎo)航欄、版權(quán)聲明等等，不能簡(jiǎn)單地直接逐字符比較。這里有一個(gè)叫做Shingling的方法，其實(shí)說(shuō)起來(lái)很圡，就是把每相鄰的k個(gè)字符作為一個(gè)元素，這樣整篇文檔就變成了一個(gè)集合。比如文檔是“banana”，若k=2，轉(zhuǎn)化以后得到集合為

{“ba”,“an”,“na”}，于是又變成了前述集合相似度的問(wèn)題。關(guān)于k值的設(shè)置，顯然過(guò)小或過(guò)大都不合適，據(jù)說(shuō)比較短的比如email之類(lèi)可以設(shè)k=5，比如長(zhǎng)的文章如論文之類(lèi)可以設(shè)k=9。

當(dāng)然，這是一個(gè)看上去就很粗糙的算法，這里的相似度比較只是字符意義上的，如果想進(jìn)行語(yǔ)義上的比較就不能這么簡(jiǎn)單了（我覺(jué)得肯定有一摞摞的paper在研究這個(gè)）。不過(guò)同樣可以想見(jiàn)的是，在實(shí)際中這個(gè)粗糙算法肯定表現(xiàn)得不壞，速度上更是遠(yuǎn)優(yōu)于復(fù)雜的NLP方法。在實(shí)際工程中，必然糙快猛才是王道。

有一點(diǎn)值得注意的是，Shingling方法里的k值比較大時(shí)，可以對(duì)每個(gè)片段進(jìn)行一次hash。比如k=9，我們可以把每個(gè)9字節(jié)的片段hash成一個(gè)32bit的整數(shù)。這樣既節(jié)省了空間又簡(jiǎn)化了相等的判斷。這樣兩步的方法和4-shingling占用空間相同，但是會(huì)有更好的效果。因?yàn)樽址姆植疾皇蔷鶆虻?，?-shingling中實(shí)際上大量的4字母組合沒(méi)有出現(xiàn)過(guò)，而如果是9-shingling再hash成4個(gè)字節(jié)就會(huì)均勻得多。

在有些情況下我們需要用壓縮的方式表示集合，但是仍然希望能夠（近似）計(jì)算出集合之間的相似度，此時(shí)可用下面的Minhashing方法。

首先把問(wèn)題抽象一下，用矩陣的每一列表示一個(gè)集合，矩陣的行表示集合中所有可能的元素。若集合c包含元素r，則矩陣中c列r行的元素為1，否則為0。這個(gè)矩陣叫做特征矩陣，往往是很稀疏的。以下設(shè)此矩陣有R行C列。

所謂minhash是指把一個(gè)集合（即特征矩陣的一列）映射為一個(gè)0..R-1之間的值。具體方法是，以等概率隨機(jī)抽取一個(gè)0..R-1的排列，依此排列查找第一次出現(xiàn)1的行。

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

S1S2S3S4

0a1001

1b0010

2c0101

3d1011

4e0010

設(shè)隨機(jī)排列為43201(edcab)，按edcab的順序查看S1列，發(fā)現(xiàn)第一次出現(xiàn)1的行是d(即第3行)，所以h(S1)= 3，同理有h(S2)=2, h(S3)=4, h(S4)=3。

此處有一重要而神奇的結(jié)論：對(duì)于等概率的隨機(jī)排列，兩個(gè)集合的minhash值相同的概率等于兩個(gè)集合的Jaccard相似度。

證明：同一行的兩個(gè)元素的情況有三種：X.兩者都為1；Y.一個(gè)1一個(gè)0；Z.兩者都為0。易知Jaccard相似度為|X|/(|X|+|Y|)。另一方面，若排列是等概率的，則第一個(gè)出現(xiàn)的X中元素出現(xiàn)在Y中元素之前的概率也為|X|/(|X|+|Y|)，而只有這種情況下兩集合的minhash值相同。

于是方法就有了，我們多次抽取隨機(jī)排列得到n個(gè)minhash函數(shù)h1,h2,…,hn，依此對(duì)每一列都計(jì)算n個(gè)minhash值。對(duì)于兩個(gè)集合，看看n個(gè)值里面對(duì)應(yīng)相等的比例，即可估計(jì)出兩集合的Jaccard相似度?？梢园?/p>

每個(gè)集合的n個(gè)minhash值列為一列，得到一個(gè)n行C列的簽名矩陣。因?yàn)閚可遠(yuǎn)小于R，這樣我們就把集合壓縮表示了，并且仍能近似計(jì)算出相似度。

在具體的計(jì)算中，可以不用真正生成隨機(jī)排列，只要有一個(gè)hash函數(shù)從

[0..R-1]映射到[0..R-1]即可。因?yàn)镽是很大的，即使偶爾存在多個(gè)值映射為同一值也沒(méi)大的影響。

文章由超級(jí)p57官方網(wǎng)站http:// 整理發(fā)布

第二篇：基于屬性重要度約簡(jiǎn)算法在數(shù)據(jù)挖掘中的應(yīng)用研究論文

摘 要：屬性約簡(jiǎn)是粗糙集理論研究的核心內(nèi)容之一，本文通過(guò)對(duì)屬性重要度的計(jì)算，以核為基礎(chǔ)計(jì)算條件屬性集中除核以外其他屬性的重要性來(lái)確定最小的約簡(jiǎn)，最后通過(guò)實(shí)例分析驗(yàn)證了算法的有效性與可行性。

關(guān)鍵詞：數(shù)據(jù)挖掘 屬性約簡(jiǎn) 重要度

數(shù)據(jù)挖掘是從海量的且不斷動(dòng)態(tài)變化的數(shù)據(jù)中，借助有效的方法挖掘出潛在、有價(jià)值的知識(shí)過(guò)程。而粗糙集理論它是一種刻畫(huà)不完整性和不確定性的數(shù)學(xué)工具，能在保持分類(lèi)能力不變的前提下，通過(guò)知識(shí)約簡(jiǎn)從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律，是由波蘭科學(xué)家Pawlak在1982年提出的。而屬性約簡(jiǎn)是粗糙集理論研究的核心內(nèi)容之一，它能保證在分類(lèi)能力不變的情況下，消除重復(fù)、冗余的屬性和屬性值，減少數(shù)據(jù)挖掘要處理的信息量，提高數(shù)據(jù)挖掘的效率。本文提出了通過(guò)計(jì)算單個(gè)屬性的重要性，以重要性大于零的屬性為核，來(lái)選取其它屬性加入核中形成新的集合RED，直至剩下的所有屬性的重要性為零，得到的集合REDn即為屬性約簡(jiǎn)。粗糙集的基本理論[1-2]

定義1設(shè) 是一個(gè)信息系統(tǒng)，其中 是對(duì)象的非空有限集合，即;是屬性的非空有限集合;，是屬性 的值域;是一個(gè)信息函數(shù)，即每個(gè)對(duì)象在每個(gè)屬性上對(duì)應(yīng)的信息值。若，其中 為非空有限條件屬性集合，為非空有限決策屬性集合，且，則稱信息系統(tǒng)為決策表。

定義2對(duì)決策表，，考慮單決策屬性的情況，即，則的分辨矩陣是一個(gè) 矩陣，其中的元素定義如下：

定義3對(duì)分辨矩陣中每個(gè)，用布爾函數(shù) 來(lái)表示，若，則決策表的分辨函數(shù) 可定義為：?；诖植诩臄?shù)據(jù)挖掘的屬性約簡(jiǎn)算法[3-4]

2.1 算法分析

第一步：求核。通過(guò)求條件屬性C中的每個(gè)屬性a對(duì)在整個(gè)條件屬性集C的重要性SigC(x)來(lái)確定屬性核CORE(x)，重要性SigC(x)>0的屬性為核屬性。

第二步：通過(guò)向?qū)傩院薈ORE(x)中依次加入重要性大的屬性來(lái)確定屬性集x的最小約簡(jiǎn)，詳細(xì)步驟如下：(1)把a(bǔ)加入到屬性集R 中，計(jì)算重要性，選擇重要性最大的屬性;(2)如果兩個(gè)屬性有相同的重要性，取離散值小的屬性。

2.2 算法復(fù)雜度

通過(guò)算法的分析，在對(duì)決策表進(jìn)行劃分的時(shí)間復(fù)雜度為O(n2)。而計(jì)算條件屬性的重要性也是滿足劃分的線性關(guān)系，因此所求屬性核的時(shí)間復(fù)雜度為O(n2)，依次添加次重要度的屬性也沒(méi)有增加額外的開(kāi)銷(xiāo)，因此整個(gè)時(shí)間復(fù)雜度還是O(n2)。

2.3 實(shí)例及分析

為了進(jìn)一步驗(yàn)證算法的可行性，下面以表1中的決策表為例進(jìn)行分析說(shuō)明，其中對(duì)象集，條件屬性集，決策屬性。

以上對(duì)計(jì)算出的實(shí)驗(yàn)數(shù)據(jù)的重要性進(jìn)行統(tǒng)計(jì)得出信息系統(tǒng)的兩個(gè)約簡(jiǎn)為{c1,c4}和{c2,c4}。結(jié)語(yǔ)

本文針對(duì)屬性約簡(jiǎn)算法中的屬性重要度的計(jì)算來(lái)確定核，適合對(duì)海量數(shù)據(jù)的挖掘，不僅節(jié)省了存儲(chǔ)空間，而且在時(shí)間復(fù)雜度開(kāi)銷(xiāo)少，通過(guò)實(shí)驗(yàn)分析驗(yàn)證了算法的可行性與有效性，為決策表的屬性約簡(jiǎn)提供了一條高效的途徑。

參考文獻(xiàn)：

[1]張文修,吳偉志.粗糙集理論與方法[M].北京:科學(xué)出版社,2001:18-19

[2]周獻(xiàn)中,黃兵，李華雄,等.不完備信息系統(tǒng)知識(shí)獲取的粗糙集理論與方法[M].南京:南京大學(xué)出版社,2010:10-11

[3]饒泓,夏葉娟,李?yuàn)弥?基于分辨矩陣和屬性重要度的規(guī)則提取算法[J].計(jì)算機(jī)工程與應(yīng)用，2008,44(3):163-165

[4]黃國(guó)順,劉云生.一種改進(jìn)的決策表屬性重要性及其快速約簡(jiǎn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(28):173-176