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

1、1本講內(nèi)容 k-NN分類(lèi) 預(yù)測(cè) 分類(lèi)的準(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分類(lèi) 每個(gè)訓(xùn)練樣本都看

2、作n維空間中的一個(gè)點(diǎn)。 給定一個(gè)未知樣本（類(lèi)似于查詢(xún)點(diǎn)q）， 首先找到該樣本的k個(gè)近鄰，將這k個(gè)近鄰按照類(lèi)標(biāo)號(hào)進(jìn)行分組，未知樣本最終被分到組員最多的那個(gè)組。4本講內(nèi)容 k-NN分類(lèi) 預(yù)測(cè) 分類(lèi)的準(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 有一些軟件包解決回歸問(wèn)題。例如:lSAS(http:/)lSPSS(http:/)lS-Plus(http:/)。7Linear regression 在線(xiàn)性回歸線(xiàn)性回歸中，數(shù)據(jù)用直線(xiàn)建模。是最簡(jiǎn)單的回歸形式。 雙變量回歸將一個(gè)隨機(jī)變量Y（稱(chēng)作響應(yīng)響應(yīng)變量變量

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

5、 與其它復(fù)雜的回歸方法相比，線(xiàn)性回歸常常給出很好的近似。siisiiixxyyxx121)()(xyxy10用最小二乘法求回歸系數(shù):例子11 用方程Y = + X表示年薪和工作年數(shù)之間的關(guān)系。 給定左圖數(shù)據(jù)，計(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進(jìn)行線(xiàn)性回歸 給定樣本x, 根據(jù)訓(xùn)練集求出它的k個(gè)近鄰，則：)(1xNxykY

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

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

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