數(shù)據(jù)分析基礎(chǔ)算法大觀

數(shù)據(jù)中心就是數(shù)據(jù)處理的中心，數(shù)據(jù)是數(shù)據(jù)中心里最寶貴的資產(chǎn)。沒有數(shù)據(jù)需要處理，數(shù)據(jù)中心也就失去了存在的意義。僅僅有數(shù)據(jù)，沒有分析與處理，對(duì)于社會(huì)來說，這些數(shù)據(jù)沒有體現(xiàn)出其應(yīng)該有的價(jià)值，通過數(shù)據(jù)中心對(duì)數(shù)據(jù)進(jìn)行二次加工處理，則可能產(chǎn)生出巨大的財(cái)富。21世紀(jì)社會(huì)發(fā)展開啟了大數(shù)據(jù)時(shí)代，與此同時(shí)，大數(shù)據(jù)也將反作用于社會(huì)，將給社會(huì)帶來巨大的變革。而只有數(shù)據(jù)中心才能夠擔(dān)負(fù)起大數(shù)據(jù)分析的重任，然而面對(duì)這些海量的數(shù)據(jù)，如何進(jìn)行高效分析，并得到預(yù)期效果，那就是數(shù)據(jù)中心要認(rèn)真去考慮的事情了。除了通過耗費(fèi)大量資金去購買各種服務(wù)器，提升網(wǎng)絡(luò)和存儲(chǔ)能力這些硬件參數(shù)之外，關(guān)鍵是要采用高效的軟件數(shù)據(jù)處理算法，在單位時(shí)間內(nèi)，相同的硬件資源條件下，可以計(jì)算更多的數(shù)據(jù)。下面就來說一說那些常用的數(shù)據(jù)處理算法。

數(shù)據(jù)分析的方法有很多，比如聚類分析、因子分析、相關(guān)分析、對(duì)應(yīng)分析、回歸分析等等，而這些數(shù)據(jù)分析的方法往往忽略了一個(gè)非常關(guān)鍵的因素：計(jì)算性能，數(shù)據(jù)中心需要的就是這些計(jì)算性能高的數(shù)據(jù)分析方法，比如HASH算法，二叉樹算法。

HASH算法一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。，HASH算法是根據(jù)特定的索引在海量的數(shù)據(jù)當(dāng)中以最快的速度查找，這種方法在任何的數(shù)據(jù)分析中都有應(yīng)用。比如：我們數(shù)據(jù)中心有這樣一個(gè)應(yīng)用系統(tǒng)，就是記錄進(jìn)入數(shù)據(jù)中心人員，那么當(dāng)我們需要知道某個(gè)人是否以前也曾進(jìn)入數(shù)據(jù)中心的時(shí)候，就需要在以往的登記數(shù)據(jù)中查找，比如我們系統(tǒng)記錄的是身份證號(hào)碼，那么怎么樣才能以最快的速度匹配呢。當(dāng)然我們可以從頭到尾一條一條的查找，這時(shí)找到花費(fèi)的時(shí)間是不定的，可能一次就找到，也可能幾千次都找不到。若采用HASH算法，基本通過一次查找就可以找到。我們可以通過HASH算法，將每個(gè)進(jìn)入數(shù)據(jù)中心的人身份證都進(jìn)行HASH計(jì)算（一般是選取不同位的數(shù)值進(jìn)行異或運(yùn)算），算出來的索引記錄保存到HASH 表中，隨著進(jìn)入的人越來越多，HASH表也會(huì)越來越大。當(dāng)我們需要得到現(xiàn)在進(jìn)入數(shù)據(jù)中心的人是否曾經(jīng)來過，那么根據(jù)這個(gè)人的身份證數(shù)據(jù)算出索引值，根據(jù)這個(gè)索引值直接去HASH表的這個(gè)位置去看是否為空，如果非空，就表明此人曾經(jīng)來過，如果是空，就表明此人以前從來沒有進(jìn)入過。這只是一個(gè)HASH算法的舉例，實(shí)際的應(yīng)用系統(tǒng)算法要比這個(gè)復(fù)雜得多，但數(shù)據(jù)處理的根本還是要靠HASH算法來提升計(jì)算性能，有時(shí)甚至要做多次HASH計(jì)算。

我們?cè)诖髮W(xué)學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)課程的都知道，有個(gè)二叉樹算法，這是樹形算法的一種。其計(jì)算的理念就是將數(shù)據(jù)一分為二，然后判斷要查找的數(shù)據(jù)屬于哪一部分，這樣一次計(jì)算就排除掉了一半的數(shù)據(jù)量，以此類推，每計(jì)算一次就可以排除一半的數(shù)據(jù)，這種算法雖然沒有HASH 算法效率高，但使用簡單，編程設(shè)計(jì)容易實(shí)現(xiàn)，在一些要求不太高的軟件計(jì)算系統(tǒng)中也應(yīng)用很普遍。這兩種算法都為在海量數(shù)據(jù)中查找到需要的數(shù)據(jù)提供了快速的計(jì)算方法，其實(shí)我們?cè)诎俣壬蠜]搜索一次，就是在海量的網(wǎng)頁里面查找想要搜索的數(shù)據(jù)，那么在搜索的算法中，就廣泛地使用了HASH和二叉樹算法，除了這些算法，還有一種就是集群算法。

在海量的網(wǎng)頁里查找到關(guān)鍵字，僅僅靠一臺(tái)服務(wù)器計(jì)算是不可能在短時(shí)間完成的，而我們?cè)谒阉鞯臅r(shí)候幾乎在一秒之內(nèi)就會(huì)得到數(shù)萬條搜索記錄，其實(shí)后臺(tái)是靠數(shù)百臺(tái)服務(wù)器同時(shí)計(jì)算完成的，這些服務(wù)器我們定義為一個(gè)集群系統(tǒng)。集群技術(shù)就是使用多個(gè)服務(wù)器的計(jì)算資源來共同完成一件事，和我們經(jīng)常談及的云計(jì)算類似，可以將集群技術(shù)歸結(jié)為云計(jì)算的前身，在云計(jì)算概念沒有出來之前，基本都是集群技術(shù)的天下。比如在奇虎360，采用200臺(tái)服務(wù)器完成搜索的工作，當(dāng)然百度的搜索集群的服務(wù)器數(shù)量要更多一些，當(dāng)一個(gè)搜索詞語進(jìn)來，通過集群技術(shù)就將需求同時(shí)發(fā)向200臺(tái)服務(wù)器，每臺(tái)服務(wù)器將計(jì)算的結(jié)果發(fā)給發(fā)出請(qǐng)求的服務(wù)器，這200臺(tái)服務(wù)器哪個(gè)都可以作為發(fā)起請(qǐng)求的服務(wù)器，當(dāng)?shù)玫狡溆?99臺(tái)設(shè)備返回的結(jié)果，然后就將計(jì)算的結(jié)果返回給用戶。通過增加集群里服務(wù)器的數(shù)量，就可以達(dá)到提升計(jì)算性能的目的。另外集群技術(shù)還有一個(gè)好處，就是假如這200臺(tái)設(shè)備有一臺(tái)是故障的，并不會(huì)大大影響計(jì)算的性能，有其余的199臺(tái)承擔(dān)全部的搜索需求，避免出現(xiàn)由于單臺(tái)硬件故障導(dǎo)致搜索功能無法使用。在我們實(shí)際的使用中可以回憶一下幾乎從來沒有遇到過百度搜索不好用的情況，就是因?yàn)椴捎昧思杭夹g(shù)，不僅計(jì)算速度快，還能避免單點(diǎn)故障導(dǎo)致整個(gè)搜索無法進(jìn)行。一般搜索系統(tǒng)至少多做好兩到三個(gè)集群系統(tǒng)，當(dāng)其中一個(gè)集群無法工作時(shí)，可以將搜索需求調(diào)整到其它的集群系統(tǒng)中來計(jì)算完成，避免了整個(gè)搜索業(yè)務(wù)癱瘓掉。

除了這些算法，其實(shí)還有不少的提升計(jì)算性能的好方法，比如哈夫曼編碼，數(shù)據(jù)挖掘的K-means，isodata等，這些算法都不是太常用，但是在算法領(lǐng)域都是比較知名的，在數(shù)據(jù)中心的各種軟件應(yīng)用系統(tǒng)中也很常見。

本文簡單介紹了數(shù)據(jù)中心最常用的一些數(shù)據(jù)分析算法，本意就是希望對(duì)數(shù)據(jù)中心里軟件對(duì)提升數(shù)據(jù)處理效率的作用和硬件一樣不能小視，高性能的數(shù)據(jù)中心并不意味著一定不斷地引進(jìn)先進(jìn)的計(jì)算設(shè)備，優(yōu)化軟件處理算法往往可以讓數(shù)據(jù)中心的計(jì)算效率有質(zhì)的提升。