分類-數(shù)據(jù)挖掘-韓家煒_5剖析

1、1本講內(nèi)容 k-NN分類 預(yù)測 分類的準(zhǔn)確性2k-Nearest Neighbors Definition: Given a query point p, and a distance function dist(), let qk be a point in the database such that count( q| dist(p,q) =dist(p,qk), q D ) = k-1 The k-nearest neighbors of p are all points q such that dist(p,q) = dist(p,qk)pqkk=103k-NN分類 每個訓(xùn)練樣本都看

2、作n維空間中的一個點。 給定一個未知樣本（類似于查詢點q）， 首先找到該樣本的k個近鄰，將這k個近鄰按照類標(biāo)號進行分組，未知樣本最終被分到組員最多的那個組。4本講內(nèi)容 k-NN分類 預(yù)測 分類的準(zhǔn)確性5What Is Prediction? Prediction is similar to classificationlFirst, construct a modellSecond, use model to predict unknown value Major method for prediction: regressionlLinear and multiple regressionl

3、Non-linear regression Prediction is different from classificationlClassification refers to predict categorical class labellPrediction models continuous-valued functions6 有一些軟件包解決回歸問題。例如:lSAS(http:/)lSPSS(http:/)lS-Plus(http:/)。7Linear regression 在線性回歸線性回歸中，數(shù)據(jù)用直線建模。是最簡單的回歸形式。 雙變量回歸將一個隨機變量Y（稱作響應(yīng)響應(yīng)變量變量

4、）視為另一個隨機變量X（稱為預(yù)測預(yù)測變量變量）的線性函數(shù)。即：Y = + X 8Linear regression 在線性回歸線性回歸中，數(shù)據(jù)用直線建模。是最簡單的回歸形式。 雙變量回歸將一個隨機變量Y（稱作響應(yīng)變量響應(yīng)變量）視為另一個隨機變量X（稱為預(yù)測變量預(yù)測變量）的線性函數(shù)。即：Y = + X 其中，和是回歸系數(shù)回歸系數(shù) 建模的過程主要是求回歸系數(shù)，常用的方法：l最小二乘法9用最小二乘法求回歸系數(shù) 給定s個樣本或形如(x1,y1), (x2,y2), (xs,ys)的數(shù)據(jù)點，回歸系數(shù)和可以用下式計算： 其中，是x1, x2 ,., xs的平均值，而 是y1, y2 ,., ys的平均值。

5、 與其它復(fù)雜的回歸方法相比，線性回歸常常給出很好的近似。siisiiixxyyxx121)()(xyxy10用最小二乘法求回歸系數(shù):例子11 用方程Y = + X表示年薪和工作年數(shù)之間的關(guān)系。 給定左圖數(shù)據(jù)，計算出 = 9.1， = 55.4。 用最小二乘法求回歸系數(shù):例子xy6 .23) 1 . 9)(7 . 3(4 .555 . 3) 1 . 916(.) 1 . 98() 1 . 93()4 .5583)(1 . 916(.)4 .5557)(1 . 98()4 .5530)(1 . 93(22212用k-NN進行線性回歸 給定樣本x, 根據(jù)訓(xùn)練集求出它的k個近鄰，則：)(1xNxykY

6、kii13multiple regression 多元回歸多元回歸是線性回歸的擴展，涉及多個預(yù)測變量。 響應(yīng)變量Y可以是一個多維特征向量的線性函數(shù)。 基于兩個預(yù)測屬性或變量X1和X2的多元回歸模型的例子是 最小二乘法同樣可以用在這里求解，1和2 2211XXY14Non-linear regression 通過在基本線性模型上添加多項式項，多項式回歸多項式回歸可以用于建模。 通過對變量進行變換，可以將非線性模型轉(zhuǎn)換成線性的，然后用最小二乘法求解。15Non-linear regression 例 下面的三次多項式 通過定義如下新變量： X1 = X X 2 = X 2 X 3 =X 3 可以轉(zhuǎn)

7、換成線性形式，結(jié)果為： 33221XXXY332211XXXY16本講內(nèi)容 k-NN分類 預(yù)測 分類的準(zhǔn)確性17評估分類法的準(zhǔn)確率 保持和k-交叉確認是兩種常用的評估分類法準(zhǔn)確率的技術(shù) 18保持法 給定數(shù)據(jù)隨機地劃分成兩個獨立的集合：訓(xùn)練集和測試集。通常，三分之二的數(shù)據(jù)分配到訓(xùn)練集，其余三分之一分配到測試集。 隨機選樣：隨機選樣：是保持方法的一種變形，它將保持方法重復(fù)k次。總體準(zhǔn)確率估計取k次迭代的平均值。19k-交叉確認 初試數(shù)據(jù)被劃分成k個互不相交的子集S 1 ， S 2 ，. ， S k，每個子集的大小大致相等。 訓(xùn)練和測試進行k次。在第i次迭代，S i用作測試集，其余的子集都用于訓(xùn)練集

8、。即，第一次迭代在子集S 2,.,S k上訓(xùn)練，而在S1上測試；第二次迭代的分類法在子集S 1, S 3,.,S k上訓(xùn)練，而在S2上測試；如此下去。 準(zhǔn)確率是k次迭代過程中分類結(jié)果正確的樣本數(shù)除以樣本總數(shù)。 20提高準(zhǔn)確率的方法 裝袋（Bagging）和 推進 (Boosting) 假定你是一個病人，希望根據(jù)你的癥狀進行診斷。你可能選擇看多個醫(yī)生，而不是一個。如果某種診斷比其它診斷出現(xiàn)的次數(shù)多，你可能將它作為最終或最好的診斷。現(xiàn)在，將醫(yī)生換成分類法，你就可以直觀地理解裝袋。 假定你根據(jù)醫(yī)生以前診斷的準(zhǔn)確率，對每個醫(yī)生的診斷“值”或價值賦予一個權(quán)值，則最終的診斷是加權(quán)的診斷的組合。這就是推進的

9、基本思想。 21總結(jié) Classification is an extensively studied problem (mainly in statistics, machine learning & neural networks) Classification is probably one of the most widely used data mining techniques with a lot of extensions Scalability is still an important issue for database applications: thus combining classification with database techniques should be a promising topic Research directions: classification of non-relational data, e.g., text, spatial, multimedia, etc.22作業(yè)1：1.Explain why RainForest is a scalable method for decision-tree inductio