http://www.cnblogs.com/seasamsun/p/samsun.html2013/07/22-26 于合肥科大
這幾天在合肥參加了由熊輝老師主講的DM（Data Mining），收獲不少。老師講的方式正如他所說的是獨一無二的，通過案例的方式介紹算法，深入淺出，通俗易懂。5天的時間，天氣很熱，課上大家基本上沒有睡覺的。老師認為DM主要分為4大塊：Classification, Association Rule Discovery, Clustering和Anomaly Detection。中間還介紹了對人生，社會，教育等的獨特見解。
1.幾個問題和概念
1）為什么要有DM
硬件的發展。硬件越來越強大也越來越便宜，為我們利用計算機解決大規模計算問題提供了物質基礎。
商業競爭的需要。現在有大量數據需要收集和存貯，如何利用這些數據在同行競爭中占據優勢很關鍵。
人性化需要。高質量，更方便，更舒適，更安全，更宜居的生活是人的本能需求，利用計算機對每個人的歷史數據進行分析和挖掘可以更好地滿足人的需要。
城市的發展。隨著社會信息化的進行，交通、醫療、教育、服務等各行各業都需要合理監督和優化配置。
科學發展的需要。未來科學的發展離不開計算機的支持，科學家需要更好的理解和分析數據。
2）DM的定義（定義很多，選取一種）
從 數據中獲取之前不知道，但有用的信息。挖掘之前是一堆數據，挖掘之后還是一堆數據，只是挖掘之后的數據是經過提煉的，人們所能理解的信息。數據挖掘必須要 有數據，沒有數據做不好數據挖掘。數據是信息的載體，現實生活中的信息不一定可以被計算機直接處理，所以需要分析和抽象并預處理為計算機能處理的數據。挖 掘到的信息準不準，有不有用還需要驗證和檢驗。
3）DM && ML
數據挖掘重在挖掘的流程，機器學習重在算法的調優。兩者的共同點離不開數據，算法和驗證。
4）數據的來源
做DM是從數據開始的，如果數據一開始就是壞的，不要指望能挖掘到好的、有用的信息。
5）數據預處理
原 始數據通常是含有噪聲的，這些噪聲數據對結果影響很大，需要找到并移除。數據的預處理內容還包括：整合，取樣，降維，特征提取。整合就是把多個數據源的原 始數據合并在一起，取樣是選取部分樣本作學習樣本，降維簡單的理解就是選擇哪些屬性，特征提取提取麻煩點涉及到構造特征空間，它主要是進一步提煉原始數 據。
6）數據可視化
做DM需要有較好的圖像展示能力。一堆數據和一個圖像在一起一定是圖像更直觀，更有說服力。通過圖像可以幫助我們分析和理解數據。
7）什么是大數據
大數據不是數據體積大，數量多。它應該用單位時間內能處理的能力來衡量。如果在能接受的時間和代價內，數據非常多但能被處理完畢，那么可以認為該數據還不夠大。
2. 挖掘技術
2.1. 分類
分類就是通過訓練出的模型判斷一個未知樣本屬于哪個類。最常見的就是2分類問題，2分類問題在金融欺詐，疾病診斷用的比較多。分類比聚類容易，分類有參考系，聚類沒有。分類一般是監督性學習。
常見的分類算法有：Decision Tree，K-Nearest-Neighbor，Neural Network，SVM，Naive Bayesian等。 判斷一個算法的好壞要從速度，準確性，可理解性，性能幾個方面綜合考慮。沒有一個算法是萬能的，具體選擇哪一個算法需要視情況而定。另外學習算法應該先從 該算法的復雜度，優缺點，使用范圍入手。學習一個算法最快的就是看簡單的案例，如果將來需要對某一個算法深入研究才要看其實現的過程。
分類的流程一般是訓練--->評估--->調整--->訓練。評估會用到混合矩陣，一般會使用ROC曲線去描述。
1）Decision Tree
決策樹就是找出滿足什么條件得到什么結果一系列的最大可能性的規則。
決策樹需要解決的難點：該用哪一個屬性，什么時候停止分叉，如何分叉。如何分叉通用的3種方法：增益（Gini），信息商（Entropy），分類錯誤（Misclassification error）。它們的共性就是減少問題的不確定大小。
有時候樹越大，越容易過擬合。過擬合（overfitting）和欠擬合（underfitting）是相對的兩個概念。過擬合拿到做人上就是太較真了，欠擬合就是做什么都無所謂。
決策樹的優點：計算復雜度底，可解釋性強，使用方便。
缺點：不是全局最優，屬性需要是離散的。
關于可解釋性想要再說一點就是政府和公司決策者喜歡DT，因為它清楚，滿足什么條件就有什么結果，而且還告訴你準確率是多少。SVM和Neural Network是一個黑箱，雖然大多數情況下這兩個比DT的準確率高幾個百分點，但決策者更加傾向于DT。
2）KNN
k最近鄰點算法原理就是看這個人是什么樣，就找他身邊最近幾個人看是什么樣，然后求一個平均值。
KNN需要解決的問題：如何衡量最近的人，是經常在一起的男（女）朋友，同事，哥們還是其他人；找幾個人，3,5個還是10個。
KNN的優點：思想簡單，訓練時間短。
缺點：k會影響準確度，分類時間長（lazy）。
3）SVM
SVM就是找到一個超平面把兩個類分開，越開越好。
關于SVM理解幾個概念。hyperplane（超平面），margin（度量分開的程度），quadratic programing（二次規劃），slack variables（松弛變量，消除噪音用），kernel function（轉化為對偶問題時需要用），support vectors（部分樣本，分類結果由這幾個向量決定）。
優點：小樣本性能都較好，準確度高，穩定性好。
缺點：調參數難，訓練時間較長，可理解性較差，維數災難（核函數引起）。
關于分類就介紹這3種算法。補充2個問題。
噪音和異常
噪聲（noise）是錯誤，異常（outlier）不是。通過情況下異常對問題的發現具有重要意義。如金融異常發現等。
訓練樣本&&驗證樣本&&測試樣本
驗證樣本是訓練樣本的一部分，測試樣本和訓練樣本嚴格分開，測試樣本只用一次。驗證的方法一般采用5-flod-validation 或 10-flod-validation。5-flod-validation的意思就是將訓練樣本平均分為5份，標記1,2,3,4,5。先拿2,3,4,5份訓練，第1份測試；然后1,3,4,5份訓練，第2份測試；... ，求5次的評價錯誤即為錯誤率。
2.2. 關聯分析
關聯規則又稱頻繁項挖掘。主要用來找出兩個同時出現的項（item），這些項之間沒有直接的因果關系。與聚類的比較相似，聚類針對對象，關聯針對對象中的某些屬性值。
關聯的幾個概念：項集（itemset），支持數（support count），支持度（support），頻繁項集（frequency itemset），關聯規則（association rule），規則評估量（rule evaluation metric）。
抽取規則的過程需要借助一些過濾條件，這些過濾條件的閾值與規則評估量有關，例如support與confidence。現在confidence被證明有問題，但為了描述經典算法apriori還繼續使用它。
關聯規則難點在于計算，如果一條記錄有n個屬性，那么它的項集是一個組合，2n個。在指數級空間被進行頻繁項搜索是一個NP難問題，更加費時間的是每一次需要掃描數據庫做統計運算。所以可以從2個方面改進，減小搜索項空間和加快數據庫查詢速度。前者的思想是apriori算法的基礎，后者是FP-tree算法的基礎。
由于關聯規則特點，用計算機去發現頻繁項是非常耗時的，這一點與人的思維恰恰相反，人的思維可以跳躍式思考，而計算機不行。
借助關聯分析的特點可以幫助我們做人做事，情報機構大部分就是在做關聯分析。我們和人打交道也有關聯分析的影響，通常有經驗的人會在幾秒鐘之內知道你的身份，工作，地位，年齡及收入等，不是說這個人有什么特異功能，而是他有經驗，這個經驗用DM的術語講就是關聯規則。關聯規則強調細節，細節決定成敗，有些人從細節上會看到別人看不到，看不懂的東西。
人的大腦具備很強的學習能力，只是我們沒有給它數據進行學習，這個數據很多都是失敗的經歷還有自我的不滿足，所以說人的經歷多了，見識多了就變得更加老練和聰明。
2.3. 聚類
聚類是一個非常有挑戰性的問題，原因在于沒有一個統一的標準去衡量聚類結果的好壞。聚類就是將相似的個體放在一起，它可以幫助我們更好的總結和理解事物。分類主要有分割式（partitional）和分層式（hierarchical）兩大類算法。前者是全局的（global），后者是貪婪的（greedy）。前者可描述社會主義社會，后者可以描述資本主義社會，社會主義輕個人重國家，資本主義重個人輕國家。好社會應該利用兩種社會制度的優點，它應該是國富民強，少異常少噪聲，每個人都有機會，中間大兩頭小，幸福指數均值大、方差小滿足正態（正常狀態）分布的社會。
聚類算法的難點在于聚類衡量標準和分類數目。分割式聚類代表性算法是k-means，分層式有group average，dbscan，min，max等。
1）k-means
k-means的思想很簡單。先隨機選擇k的點做初始點；然后每一個點與這k個點作比較，這個點與這k個點哪一個最近就屬于哪個點（類）； 求出每一個類的中心點，總共k個，以新的k的點作為類標記按照同樣的方式劃分所有的點；滿足結束條件結束。
算法的優點：簡單容易理解，復雜度低，速度快。
缺點：對k值和初始值敏感，數據分布的稀疏程度有影響，樣本是球形結果才好，抗噪音能力低。
在運用k-means進行聚類分析時，為了減小k值的影響可以先將k值取很大（譬如100），然后再分層聚類，或者先將所有樣本分層1個類再分成2，3... ，多個（Bisecting k-means）。在減小初始值隨機性的影響時，可以采取多次選取求大概率的方法。
2）group average
該方法是分層聚類方法，一般在多元統計課程里會講到。它是分層聚類常用的方法，基本思想是類與類的距離由該類中所有點加權決定，有效的消除了噪聲的干擾。一般來說，group average整體性能比min和max要好，但是其計算量較大。min也有自己的優勢，在密度大的聚類時抗噪能力較好。
3）dbscan
該分層聚類方法canopy方法類似，都是為了提高算法的抗噪能力。它有3個概念：core point，border poing和noise point。難點是確定core point中點的個數。
算法的優點：2,3維聚類效果很好。
缺點：高維效果不好。
2.4. 異常檢測
異常檢測一般是非監督性學習，異常檢測得到的異常可以看成是聚類結果的一種特殊形式。異常和噪聲有區別，異常通常是有用的，從它入手很可能發現新問題，而噪聲通常是錯誤。異常檢測主要用在發現不尋常的事物，在網絡欺詐和疾病檢測中用的比較多。
異常的來源主要是因為它們出現的概率比較低，或者被非正常的篡改。由于是小概率事件，發現它們是非常困難的。
處理這類問題的方法有：分類，統計分布，回歸，幾何和圖論。以聚類的方法為例，由于異常樣本較小，一般聚類方法不適用。因為聚類方法對大類的預測較好，異常檢測是要大概率識別出異常，即使正常數據預測的再高，但異常檢測不到也是沒有效果的。
用分類做檢測常用的做法是加大異常樣本的權重。這樣一來會將一部分正常的數據預測為異常的數據，但是可以接受，在欺詐檢測方面：誤判比漏判好。
2.5. 小結
在介紹DM中4大問題時，沒有給出算法的計算公式。不是說公式不重要，要想深入研究公式是必要的，在解決實際問題時，從宏觀上（思想，優缺點，使用范圍）對每一個算法進行把握就夠了。
3. 好話
在上課的過程中，老師不時穿插他對社會，國家和人生的見解。一方面講算法容易使人睡覺，講這些我們不犯困；另一方面，讓我們增加見識，學會做事做人。
1) 贊美人的話多說，損害人的話少說，謊話不能說，真話不全說
人都是喜歡聽贊美的話；因一時氣憤說話攻擊別人，到頭來即使贏了，也會受傷；表里不一就會失掉做人的根本---誠信；有些話自己說出來本意是好，但是會傷害其他人。
2）如果自己不會做事情，找到會做的人，跟著他們做
不是所有的事自己都會做，遇到必須做自己又不會做的事情時，選擇擅長做這件事的人很重要。
3）方向比能力重要
最可悲的是一個人能力非常強，但是選錯了方向，結果他越努力，錯的越遠。
4）vip不好做
當你成為vip后，你享受利益和尊貴時，也許你已經被盯上了，社會知道你太多的信息，隨著信息化加速發展，你所有的信息都會被記錄。普通人機器掃描不過來，vip數量有限是可以掃描的。用顯微鏡去發現一個人的問題，誰都逃不過。所以vip不好做，普通人也有普通人的好處。
5）不要入即將被標準化的行業
入錯行對每一個人都是比較大的打擊，入錯行意味著你的收入，發展都會受到不良影響。這個行指的是標準化的行業。一旦某一個行業被標準化，絕大部分事都用機器來做時，就沒人什么事了。
6）讓自己無法被人替代
擁有自己的核心競爭力很重要。如果你能做的事別人都能做，對公司來講你就是其他人的一個子集，那你就沒有任何乘數效應可言了。
7）個人的發展由個人知識集，家庭知識集，人際關系知識集決定
年輕的時候對我們影響最大的就是家庭，其次是自己。家庭教育和決策在一個人發展之初是非常重要的，所以做父母的不容易。但隨著年齡增加，最重要的變成個人和人際關系。
8）自己會做蛋糕比切蛋糕更加了不起
一塊蛋糕（利益）在你手上，如何分讓大家皆大歡喜是一件困難的事，因為你要考慮到以后還有沒有人愿意和你分蛋糕。但如果你自己就會做蛋糕，到時候就不缺求你分蛋糕給他的人。
9）放下身段，做長遠打算
如果你目前什么都沒有，無技術，無money，無權利，拼不過爹，也拼不過爺。似乎是一無所有，怎么辦，還好你還有時間，還有目標，還有機會。你可以放下自己的身段，選定正確方向后給老板低價打工。在這個平臺下，你要積蓄力量，沉淀自己，堅持下去總有一天你會證明自己，聰明的老板會設法留下你。這是一個苦b的過程，但卻值得。