分類/聚類/文本分析算法介紹
分類算法
Decision tree, Random forest decision tree, linear regression, logistic regression, Naive bayesian, SVM
決策樹是用于分類和預測的主要技術(shù)之一，決策樹學習是以實例為基礎的歸納學習算法，它著眼于從一組無次序、無規(guī)則的實例中推理出以決策樹表示的分類規(guī)則。構(gòu)造決策樹的目的是找出屬性和類別間的關(guān)系，用它來預測將來未知類別的記錄的類別。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點進行屬性的比較，并根據(jù)不同屬性值判斷從該節(jié)點向下的分支，在決策樹的葉節(jié)點得到結(jié)論。
主要的決策樹算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它們在選擇測試屬性采用的技術(shù)、生成的決策樹的結(jié)構(gòu)、剪枝的方法以及時刻，能否處理大數(shù)據(jù)集等方面都有各自的不同之處。1決策樹（Decision Trees）的優(yōu)缺點
決策樹的優(yōu)點：
一、決策樹易于理解和解釋.人們在通過解釋后都有能力去理解決策樹所表達的意義。
二、對于決策樹，數(shù)據(jù)的準備往往是簡單或者是不必要的.其他的技術(shù)往往要求先把數(shù)據(jù)一般化，比如去掉多余的或者空白的屬性。
三、能夠同時處理數(shù)據(jù)型和常規(guī)型屬性。其他的技術(shù)往往要求數(shù)據(jù)屬性的單一。
四、決策樹是一個白盒模型。如果給定一個觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應的邏輯表達式。
五、易于通過靜態(tài)測試來對模型進行評測。表示有可能測量該模型的可信度。
六、 在相對短的時間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。
七、 可以對有許多屬性的數(shù)據(jù)集構(gòu)造決策樹。
八、 決策樹可很好地擴展到大型數(shù)據(jù)庫中，同時它的大小獨立于數(shù)據(jù)庫的大小
決策樹的缺點：
一、對于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹當中,信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征。
二、決策樹處理缺失數(shù)據(jù)時的困難。
三、 過度擬合問題的出現(xiàn)。
四、忽略數(shù)據(jù)集中屬性之間的相關(guān)性。
改進措施
1、對決策樹進行剪枝?？梢圆捎媒徊骝炞C法和加入正則化的方法。
2、使用基于決策樹的combination算法，如bagging算法，randomforest算法，可以解決過擬合的問題
應用領(lǐng)域
? 企業(yè)管理實踐，企業(yè)投資決策，由于決策樹很好的分析能力，在決策過程應用較多。
貝葉斯（Bayes）
貝葉斯（Bayes）算法是一類利用概率統(tǒng)計知識進行分類的算法，如樸素貝葉斯（Naive Bayes）算法。這些算法主要利用Bayes定理來預測一個未知類別的樣本屬于各個類別的可能性，選擇其中可能性最大的一個類別作為該樣本的最終類別。由于貝葉斯定理的成立本身需要一個很強的條件獨立性假設前提，而此假設在實際情況中經(jīng)常是不成立的，因而其分類準確性就會下降。為此就出現(xiàn)了許多降低獨立性假設的貝葉斯分類算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在貝葉斯網(wǎng)絡結(jié)構(gòu)的基礎上增加屬性對之間的關(guān)聯(lián)來實現(xiàn)的。
樸素貝葉斯的主要優(yōu)點有：
1）樸素貝葉斯模型發(fā)源于古典數(shù)學理論，有穩(wěn)定的分類效率。
2）對小規(guī)模的數(shù)據(jù)表現(xiàn)很好，能個處理多分類任務，適合增量式訓練，尤其是數(shù)據(jù)量超出內(nèi)存時，我們可以一批批的去增量訓練。
3）對缺失數(shù)據(jù)不太敏感，算法也比較簡單，常用于文本分類。
樸素貝葉斯的主要缺點有：
1） 理論上，樸素貝葉斯模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是因為樸素貝葉斯模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，在屬性個數(shù)比較多或者屬性之間相關(guān)性較大時，分類效果不好。而在屬性相關(guān)性較小時，樸素貝葉斯性能最為良好。對于這一點，有半樸素貝葉斯之類的算法通過考慮部分關(guān)聯(lián)性適度改進。
2）需要知道先驗概率，且先驗概率很多時候取決于假設，假設的模型可以有很多種，因此在某些時候會由于假設的先驗模型的原因?qū)е骂A測效果不佳。
3）由于我們是通過先驗和數(shù)據(jù)來決定后驗的概率從而決定分類，所以分類決策存在一定的錯誤率。
4）對輸入數(shù)據(jù)的表達形式很敏感。
現(xiàn)在貝葉斯已經(jīng)廣泛應用了，海難搜救、生物醫(yī)藥、疾病診斷、郵件過濾、文本分類、偵破案件、工業(yè)生產(chǎn)等很多方面。
支持向量機（SVM，Support Vector Machine）是Vapnik根據(jù)統(tǒng)計學習理論提出的一種新的學習方法[43] ，它的最大特點是根據(jù)結(jié)構(gòu)風險最小化準則，以最大化分類間隔構(gòu)造最優(yōu)分類超平面來提高學習機的泛化能力，較好地解決了非線性、高維數(shù)、局部極小點等問題。對于分類問題，支持向量機算法根據(jù)區(qū)域中的樣本計算該區(qū)域的決策曲面，由此確定該區(qū)域中未知樣本的類別。
支持向量機（SVM）的優(yōu)缺點
SVM的優(yōu)點：
一、可以解決小樣本情況下的機器學習問題。
二、可以提高泛化性能。
三、可以解決高維問題。
四、可以解決非線性問題。
五、可以避免神經(jīng)網(wǎng)絡結(jié)構(gòu)選擇和局部極小點問題。
SVM的缺點：
一、對缺失數(shù)據(jù)敏感。
二、對非線性問題沒有通用解決方案，必須謹慎選擇Kernelfunction來處理。
SVM應用領(lǐng)域
文本分類、圖像識別、主要二分類領(lǐng)域
聚類算法
K-means， Hierarchical clustering, Gaussian mixture model,
聚類就是按照某個特定標準(如距離準則)把一個數(shù)據(jù)集分割成不同的類或簇，使得同一個簇內(nèi)的數(shù)據(jù)對象的相似性盡可能大，同時不在同一個簇中的數(shù)據(jù)對象的差異性也盡可能地大。即聚類后同一類的數(shù)據(jù)盡可能聚集到一起，不同數(shù)據(jù)盡量分離。
何時使用？
當你事先知道你將找到多少個分組的時候。（這個就比較尷尬了，因為很多情況下，我們并不知道要聚多少個類）
工作方式
該算法可以隨機將每個觀察（observation）分配到 k 類中的一類，然后計算每個類的平均。接下來，它重新將每個觀察分配到與其最接近的均值的類別，然后再重新計算其均值。這一步不斷重復，直到不再需要新的分配為止。（機器學習里面最簡單的算法之一了，過程很簡單）
經(jīng)典K-means算法流程：
1. 隨機地選擇k個對象，每個對象初始地代表了一個簇的中心；
2. 對剩余的每個對象，根據(jù)其與各簇中心的距離，將它賦給最近的簇；
3. 重新計算每個簇的平均值，更新為新的簇中心；
4. 不斷重復2、3，直到準則函數(shù)收斂。
算法優(yōu)缺點
優(yōu)點：對于大型數(shù)據(jù)集也是簡單高效、時間復雜度、空間復雜度低。
缺點：最重要是數(shù)據(jù)集大時結(jié)果容易局部最優(yōu)；需要預先設定K值，對最先的K個點選取很敏感；對噪聲和離群值非常敏感；只用于numerical類型數(shù)據(jù)；不能解決非凸（non-convex）數(shù)據(jù)。
常見的算法及改進
k-means對初始值的設置很敏感，所以有了k-means++、intelligent k-means、genetic k-means。
k-means對噪聲和離群值非常敏感，所以有了k-medoids和k-medians。
k-means只用于numerical類型數(shù)據(jù)，不適用于categorical類型數(shù)據(jù)，所以k-modes。
k-means不能解決非凸（non-convex）數(shù)據(jù)，所以有了kernel k-means。
層次聚類（Hierarchical clustering）
何時使用？
當我們希望進一步挖掘觀測數(shù)據(jù)的潛在關(guān)系，可以使用層次聚類算法。
工作方式
首先我們會計算距離矩陣（distance matrix），其中矩陣的元素（i，j）代表觀測值 i 和 j 之間的距離度量。然后將最接近的兩個觀察值組為一對，并計算它們的平均值。通過將成對觀察值合并成一個對象，我們生成一個新的距離矩陣。具體合并的過程即計算每一對最近觀察值的均值，并填入新距離矩陣，直到所有觀測值都已合并。
有效案例：
以下是關(guān)于鯨魚或海豚物種分類的超簡單數(shù)據(jù)集。作為受過專業(yè)教育的生物學家，我可以保證通常我們會使用更加詳盡的數(shù)據(jù)集構(gòu)建系統(tǒng)?，F(xiàn)在我們可以看看這六個物種的典型體長。本案例中我們將使用 2 次重復步驟。
高斯混合 [Gaussian mixture model]
高斯混合模型 表達的是一種混合分布，所有點都來自于k個高斯子分布中的一個，每個點都對應一個相應的概率。在MLlib的實現(xiàn)中 ，對于給定的樣本集，使用最大期望算法(EM)來引導最大似然模型。
混合高斯模型的應用場景包括：
? 數(shù)據(jù)集分類，如會員分類；
? 圖像分割以及以及特征抽取，例如在視頻中跟蹤人物以及區(qū)分動作，識別汽車、建筑物等；
? 語音分割以及特征特征抽取，例如從一堆雜亂的聲音中提取某個人的聲音，從音樂中提取背景音樂，從大自然中提取地震的聲音等。
深度學習
FeedForward Classification, FeedForward Regression, LSTM RNN, CNN, Deep Belief,
RBM
文本分析
LDA，TFIDF，Word2vector, Word segmentation, Sentiment analysis
隱含狄利克雷分布(Latent Dirichlet Allocation，以下簡稱LDA)
LDA是基于貝葉斯模型的，涉及到貝葉斯模型離不開“先驗分布”，“數(shù)據(jù)（似然）”和"后驗分布"三塊。在樸素貝葉斯算法原理小結(jié)中我們也已經(jīng)講到了這套貝葉斯理論。在貝葉斯學派這里：
先驗分布 + 數(shù)據(jù)（似然）= 后驗分布
這點其實很好理解，因為這符合我們?nèi)说乃季S方式，比如你對好人和壞人的認知，先驗分布為：100個好人和100個的壞人，即你認為好人壞人各占一半，現(xiàn)在你被2個好人（數(shù)據(jù)）幫助了和1個壞人騙了，于是你得到了新的后驗分布為：102個好人和101個的壞人?，F(xiàn)在你的后驗分布里面認為好人比壞人多了。這個后驗分布接著又變成你的新的先驗分布，當你被1個好人（數(shù)據(jù)）幫助了和3個壞人（數(shù)據(jù)）騙了后，你又更新了你的后驗分布為：103個好人和104個的壞人。依次繼續(xù)更新下去。
LDA（Latent Dirichlet Allocation）是一種文檔主題生成模型，包含詞、主題和文檔三層結(jié)構(gòu)。通常認為一篇文章的每個詞都是通過一定概率選擇了某個主題，并從這個主題中以一定概率選擇某個詞語，從文檔—主題—詞語，
應用：針對給定輸入文本與文本庫，計算得出文本庫中與輸入文本最相似的文本
TFIDF
TF-IDF是Term Frequency - Inverse Document Frequency的縮寫，即“詞頻-逆文本頻率”。它由兩部分組成，TF和IDF。
TF-IDF是非常常用的文本挖掘預處理基本步驟，但是如果預處理中使用了Hash Trick，則一般就無法使用TF-IDF了，因為Hash Trick后我們已經(jīng)無法得到哈希后的各特征的IDF的值。使用了IF-IDF并標準化以后，我們就可以使用各個文本的詞特征向量作為文本的特征，進行分類或者聚類分析。Word2vector
word2vec 是Google在2013年年中開源的一款將詞表征為實數(shù)值向量的高效工具，采用的模型有 CBOW（Continuous Bag-Of-Words，即連續(xù)的詞袋模型）和Skip-Gram 兩種。word2vec 通過訓練， 可以把對文本內(nèi)容的處理簡化為 K 維向量空間中的向量運算， 而向量空間上的相似度可以用來表示文本語義上的相似度。 因此， word2vec輸出的詞向量可以被用來做很多 NLP 相關(guān)的工作，比如聚類、找同義詞、詞性分析等等。
情感分析(SentimentAnalysis)即分析發(fā)貼人對某個對象的態(tài)度是正面還是負面。這個過程當然不是僅僅查找"好"，"壞"這些關(guān)鍵字那 么簡單，有時候相似度很高的句子，卻反映了截然不同的態(tài)度，譬如下面這兩句話
"這瓶洗發(fā)水，適合頭發(fā)很干的人用"
"用了這瓶洗發(fā)水，頭發(fā)變得很干"
兩個句子中的主要成分都差不多，"洗發(fā)水"，"頭發(fā)"，"很干"，但是第一句是褒義，第二句則很可能是貶義。對于后一句的處理還算簡單，告訴計算機 程序頭發(fā)"很干"不好，因此讓頭發(fā)"變得""很干"的洗發(fā)水，也就不是好的洗發(fā)水。而前一句呢，我們能夠理解"適合頭發(fā)很干的人用"是指使用該洗發(fā)水后， 能讓頭發(fā)變得不那么干燥點。但是假設我們告訴計算機，"某某產(chǎn)品適合XXX的人用"就是指用了某某產(chǎn)品后，XXX的人就會變得不那么XXX，那么當計算機 處理"這件衣服，適合漂亮女生穿"，你猜它會怎么理解？(漂亮的女生穿了就會變得不那么漂亮)
還有一類問題是諷刺(反話)和幽默，國外的一個自然語言處理專家也在他的blog上感嘆道，"Humor is hard"。在國內(nèi)，很多褒義詞受到論壇文化的影響，往貶義詞發(fā)展的趨勢，例如"我太崇拜你了"，"你太有才了"。
說到底，這些都是自然語言處理面對的一個挑戰(zhàn)，即如何將生活經(jīng)驗、文化傳統(tǒng)等表達為一種可以被計算機
推薦算法
Factorization Based, Neighborhood based, popularity based, CF, slope one
Matrix Factorization即矩陣分解（MF），廣泛地應用于各種數(shù)據(jù)分析、機器學習的場景，推薦領(lǐng)域也不例外。MF矩陣分解算法用于推薦方法時，它的好處很明顯，易于編程實現(xiàn)，復雜度也比較低，預測效果也還不錯，同時具有較好的拓展性；當然，矩陣分解的解釋性會稍微弱些。
目前應用于推薦領(lǐng)域的矩陣分解模型，除了有基于SVD的各種矩陣分解算法如FunkSVD、BiasSVD、SVD++等，最基礎的矩陣分解模型（Basic MF）也可以應用于推薦系統(tǒng)，增加一些正則化項（Regularized MF）或偏置項后（Bias MF）的矩陣分解算法也都可以很好地作為推薦算法使用。
在實際應用中，矩陣分解也受到了推薦系統(tǒng)較多的青睞，尤其是小的推薦系統(tǒng)很多都會使用矩陣分解，而很大型的推薦系統(tǒng)，則會用深度學習的一些模型。
矩陣分解MF的主要思想是，1)通過分解得到用戶潛在因子矩陣U和商品潛在因子矩陣V，2）然后兩者通過外積便可得到一個用戶-商品評分矩陣的估計。
基于流行度的算法(popularity based)
基于流行度的算法非常簡單粗暴，類似于各大新聞、微博熱榜等，根據(jù)PV、UV、日均PV或分享率等數(shù)據(jù)來按某種熱度排序來推薦給用戶。
這種算法的優(yōu)點是簡單，適用于剛注冊的新用戶。缺點也很明顯，它無法針對用戶提供個性化的推薦?；谶@種算法也可做一些優(yōu)化，比如加入用戶分群的流行度排序，例如把熱榜上的體育內(nèi)容優(yōu)先推薦給體育迷，把政要熱文推給熱愛談論政治的用戶。
協(xié)同過濾算法(Collaborative Filtering, CF)
CF是很常用的一種算法，在很多電商網(wǎng)站上都有用到。CF算法包括基于用戶的CF(User-based CF)和基于物品的CF(Item-based CF)。
基于用戶的CF原理如下：
? 分析各個用戶對item的評價（通過瀏覽記錄、購買記錄等）；
? 依據(jù)用戶對item的評價計算得出所有用戶之間的相似度；
? 選出與當前用戶最相似的N個用戶；
? 將這N個用戶評價最高并且當前用戶又沒有瀏覽過的item推薦給當前用戶。
基于物品的CF原理大同小異，只是主體在于物品：
? 分析各個用戶對item的瀏覽記錄。
? 依據(jù)瀏覽記錄分析得出所有item之間的相似度；
? 對于當前用戶評價高的item，找出與之相似度最高的N個item；
? 將這N個item推薦給用戶。
?
? 我們可以看到，CF算法確實簡單，而且很多時候推薦也是很準確的。然而它也存在一些問題：
? 依賴于準確的用戶評分；
? 在計算的過程中，那些大熱的物品會有更大的幾率被推薦給用戶；
? 冷啟動問題。當有一名新用戶或者新物品進入系統(tǒng)時，推薦將無從依據(jù)；
? 在一些item生存周期短（如新聞、廣告）的系統(tǒng)中，由于更新速度快，大量item不會有用戶評分，造成評分矩陣稀疏，不利于這些內(nèi)容的推薦。
Slope One
算法是由 Daniel Lemire 教授在 2005 年提出的一個Item-Based 的協(xié)同過濾推薦算法。和其它類似算法相比, 它的最大優(yōu)點在于算法很簡單, 易于實現(xiàn), 執(zhí)行效率高, 同時推薦的準確性相對較高。
Slope One算法是基于不同物品之間的評分差的線性算法，預測用戶對物品評分的個性化算法。主要兩步：
Step1:計算物品之間的評分差的均值，記為物品間的評分偏差(兩物品同時被評分)；
Step2:根據(jù)物品間的評分偏差和用戶的歷史評分，預測用戶對未評分的物品的評分。
Step3:將預測評分排序，取topN對應的物品推薦給用戶。
slopeOne使用場景
該算法適用于物品更新不頻繁，數(shù)量相對較穩(wěn)定并且物品數(shù)目明顯小于用戶數(shù)的場景。依賴用戶的用戶行為日志和物品偏好的相關(guān)內(nèi)容。
優(yōu)點：
1.算法簡單，易于實現(xiàn)，執(zhí)行效率高；
2.可以發(fā)現(xiàn)用戶潛在的興趣愛好；
缺點：
依賴用戶行為，存在冷啟動問題和稀疏性問題。