记忆基础推理精选文档.ppt

《记忆基础推理精选文档.ppt》由会员分享，可在线阅读，更多相关《记忆基础推理精选文档.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、记忆基础推理本讲稿第一页，共六十九页報告大綱一、前言二、CaseStudy：到底誰才是鄰居？三、記憶基礎推理如何運作?四、如何增進MBR作業效能?五、CaseStudy：新聞報導分類六、反查與準度的範例七、距離的測量八、結論本讲稿第二页，共六十九页一、前言本讲稿第三页，共六十九页前言人們總是藉著過去的經驗做判斷，例如:1.當你聽到說話不捲舌,你會覺得她是台灣人，為什麼？2.當醫生要診斷一個病人時，會依據過去的經驗與眼前的症狀來做判斷及比對，為什麼？本讲稿第四页，共六十九页MBR(Memory-Basedreasoning)以上的敘述都是MBR的原理，只不過是換成了由人工智慧進行比對。根據現有的

2、資料庫，“記憶基礎推理”先找出新資料的“鄰近資料”（Neighbor），然後根據鄰近資料，對新資料進行分析和預測。本讲稿第五页，共六十九页關鍵運用(一)MBR不在乎資料的格式必備要項(1).距離函數(DistanceFunction)負責判斷兩筆資料差異到底有多大(2).組合函數(CombinationFunction)將若干相似資料的結果結合，以產生答案。本讲稿第六页，共六十九页關鍵運用(二)MBR的相關應用例子(1).詐欺案件的判斷(2).顧客回應預測(3).最佳醫療措施選擇(4).顧客反應分類(顧客抱怨單)本讲稿第七页，共六十九页MBR優點相較於其他DataMining技術時，MBR的簡

3、易使用常讓人低估了他的強大能力.只要定義出距離函數與組合函數，MBR的可以分析任何形式的資料-例如:地理區位、影像、純文字等。它能同時將新資料和舊資料結合，同時能從舊資料中分析出新的分類項和定義。本讲稿第八页，共六十九页二、到底誰才是鄰居？本讲稿第九页，共六十九页到底誰是鄰居？Tuxedo與New York的租金 一般人的概念，地理上鄰近的城市，也就是其鄰居，租金應該都差不了多少。但是妥善運用MBR後，我們將會重新認識並且定義什麼是“鄰居”。MBR考慮的觀點較為客觀，而非單純是 地理上的相關，而是包含人口數、房屋價值中位數等。本讲稿第十页，共六十九页圖8.1本讲稿第十一页，共六十九页到底誰才是

4、真正的鄰居？作法：(1).從散佈圖中找出最鄰近於目標的點(2).整合目標資訊答案:Shelter Island&North Salem 是Tuxedo的鄰居TownPopulationMedian RentRent$1500(%)NORent(%)ShelterIsland2228$8043.134.631.410.73.117North Salem5173$1150310.221.630.924.210.2本讲稿第十二页，共六十九页所以，租金是所以，租金是1.Average the most common rents of the two neighbors(use midpoint of

5、the range)(625+1250)/2,租金約是$9382.Or,pick the point midway between the two median rents:(804+1150)/2,租金約是$977本讲稿第十三页，共六十九页三、如何操作MBR？本讲稿第十四页，共六十九页MBR操作MBR有兩個明顯的分析階段:(1)學習階段-產生歷史資料庫 (2)預測階段-將MBR運用在新資料上運用MBR的三項前置準備工作:(1)選擇適當的訓練資料集。(2)找出最具效率的方式表達歷史記錄 (3)設定距離函數、組合函數和鄰近資料集的數目 本讲稿第十五页，共六十九页選擇一個歷史記錄的平衡資料集定義:

6、現有資料的子群組或是訓練資料集(TrainingSet)限制:訓練資料集必須能涵蓋大部分可能情況涵蓋大部分可能情況，如此新記錄的鄰近資料才能作為良好的預測基礎作法:建立訓練資料集時，不同類的資料記錄的數目應該要平衡。Tip:選擇資料組時，除確保約略相等的樣本數之外，每類最好有數十筆。本讲稿第十六页，共六十九页訓練資料的表示方法(一)MBR在預測效率取決於訓練資料組如何表示。現今最常用的是關聯式資料庫。需要比對每一筆資料和此筆紀錄的距離，然後才能產生出最接近的鄰近資料集。當訓練集資料集累積越多筆資料時，比對時間將急速上升。在關聯式資料庫為一筆新紀錄找尋鄰近資料集，雖需要掃描整個資料庫，但還算不會

7、耗時太久；可是如果同時為多筆新紀錄找尋他們的鄰近資料集時，需多次完整掃描整個資料庫，將會嚴重耗用電腦資源解決之道1:縮減訓練資料集，不使用整個資料庫，見圖8.2本讲稿第十七页，共六十九页訓練資料的表示方法(二)Distance()運算是可以帶進任何特定的距離機制，這個運算需要掃描整個資料庫。此步驟非常耗時，因此，同時保存最相似的最相似的表格表格(解決之道解決之道2 2)，視情況加入或刪除記錄，但是這些必須透過其他的程式語言，在SQL環境下無法執行。SELECT distance(),rec.categoryFROM historical_records recORDER BY 1 ASCEND

8、ING;本讲稿第十八页，共六十九页四、如何增進MBR作業效率?本讲稿第十九页，共六十九页增進MBR作業效率減少歷史資料庫的紀錄數量，“前提”：訓練資料組的大小可以大幅的影響記憶基礎裡作業效率。作法：找出含有不同分類項的群集，則各級群的中心可當成縮減的訓練資料集。條件：不同的分類項要離的夠遠不同的分類項要離的夠遠，若有重疊或界線不明時，將使MBR產生誤差。找出“Support Records”。本讲稿第二十页，共六十九页本讲稿第二十一页，共六十九页五、CaseStudy：新聞報導分類本讲稿第二十二页，共六十九页新聞報導分類採用哪些關鍵字作為分類編碼?政府機關、工業、商業、產品、地區、主題“幾乎所

9、有的新聞稿件都有地區和主題編碼，有時甚至有三個編碼”本讲稿第二十三页，共六十九页MBR運用依照以下四個步驟改善新聞的分類編碼作業1.選擇訓練資料集2.設定距離函數3.設定鄰近資料集數量4.設定組合函數本讲稿第二十四页，共六十九页選擇測試資料組測試資料組包含了49,652件新聞。這些資料是三個月的新聞稿與100個消息來源。每一則平均有2700字(words)和八個編碼。1.沒有經過篩選，為反映真實散佈2.若能採用具有更多罕見編碼的訓練資料組會更好本讲稿第二十五页，共六十九页設定距離函數利用“相關回饋”(Relevance Feedback)的測試標準，由任何兩則新聞稿的文字內容比對他們的相似度。

10、採用最相似的新聞稿當成MBR所需要的鄰近資料本讲稿第二十六页，共六十九页利用相關回饋建立距離函數(一)相關回饋是一種能夠讓使用者在比對相似資料庫，用以進行精細分析的強大技術。作法：1.去除沒有附載有價值意義的單字 ex:it、of 2.將前20%最常出現的詞彙去除 3.剩下的字最轉存到一個可搜尋術語 的字庫中，每個字給予加權值(-log2fi)4.複合語詞的納入 ex:United States、New York 5.計算兩篇報導之間的相關回饋分數 score(A,B)為A與B各自的字的權值的加總本讲稿第二十七页，共六十九页利用相關回饋建立距離函數(二)相關回饋是利用現有函數的修正用來取代真正

11、的距離函數。公式：利用上面的公式將相關回饋分析轉換成一般的距離公式。本讲稿第二十八页，共六十九页設定組合函數(一)組合函數採用加權總值技術(WeightedSummationTechnique)：每一筆鄰近資料都有一個距離倒數成正比的權值，所以越相近的資料組就有越高的加權值。表8.3為未分類新聞找出相似者相似者相似者距離距離權重權重編碼編碼10.0760.924R/FE,R/CA,R/CO20.3460.654R/FE,R/JA,R/CA30.3690.631R/FE,R/JA,R/MI40.3930.607R/FE,R/JA,R/CA本讲稿第二十九页，共六十九页設定組合函數(二)表8.4為未

12、分類新聞評分CODE1234SCORER/CA0.9240.65400.6072.185R/CO0.9240000.924R/FE0.9240.6540.6310.6072.816R/JA00.6540.6310.6071.892R/MI000.63100.631若將門檻值設為1，則此篇文章可以指派的code為 R/CA,R/FE,and R/JA本讲稿第三十页，共六十九页設定鄰近資料集數量此案例嘗試使用111個鄰近資料集數目，發現使用越多鄰近資料集數目，結果越好此例,因每則新聞會得到的分類項不只一個。較典型的問題是配置在單一編碼或分類單一編碼或分類項，此情況則較少的鄰近資料集數目，反而較好。

13、本讲稿第三十一页，共六十九页結果(一)為了測試MBR在編碼上的有效程度，我們將200則由人工(專家)及MBR編碼的新聞稿混合結果，交由一群編輯進行複審，只有過半數同意才能被當成“合格”。結果：人工編碼正確的數目比上“合格”編碼數目為88%(recall,回想)；然而，人工編碼正確的數目比上人工編碼全部為83%(precision,精確)，即不正確比例為17%。本讲稿第三十二页，共六十九页圖8.4利用人工作業及MBR將新聞進行分類的比較本讲稿第三十三页，共六十九页結果(二)MBR表現並不好:由MBR分配編碼的recall為80%；而precision僅為72%。問題與原因：Q:為什麼MBR表現不

14、好?A:因為資料數不足，無法讓MBR使用全由資深編輯分類的訓練組資料可能是因為原資料處理者的專業程度不足結論：MBR比其他技術能夠處理困難的問題。本讲稿第三十四页，共六十九页六、回想與準度本讲稿第三十五页，共六十九页回想與準度回想(RECALL)記憶基礎推理究竟提供了多少個正確碼。假如所提供的編碼包含了每個正確的編碼，其反查值就是100%，假如提供的編碼中沒有一個正確的，回想值就是0%準度準度(PRECISION)在記憶基礎推理所提供的編碼中，有多少是正確的？準度100代表著預測的編碼百發百中，若是提供的沒一個正確，那準度就是0本讲稿第三十六页，共六十九页回想與準度的範例-表8.5CODES

15、BY MBRCORRECT CODESRECALLPRECISIONA,B,C,DA,B,C,D100%100%A,BA,B,C,D50%100%A,B,C,D,E,F,G,H,A,B,C,D100%50%E,FA,B,C,D0%0%A,B,E,FA,B,C,D50%50%本讲稿第三十七页，共六十九页利用編碼類別測量回想與準度個人編輯對新聞編碼，回想83%準度88%記憶基礎推理，回想80%準度72%CATEGORYRECALLPRECISIONGovernment85%87%Industry91%85%Market Sector93%91%Product69%89%Region86%64%Su

16、bject72%53%本讲稿第三十八页，共六十九页七、測量距離本讲稿第三十九页，共六十九页測量距離假設你要到一個小鎮旅行，而你想知道那裡的天氣狀況如何，但是卻沒有管道獲得資訊，因為天氣預報都只報導大城市。如果你在當地沒有朋友，則通常的作法就是查詢附近大城市的天氣狀況，就以那個城市的天氣當成判斷標準，或者綜合附近三個大城市的天氣狀況。以上所描繪的正是利用記憶基礎推理找出天氣狀況的例子，而這裡的距離函數是兩個地點的距離。本讲稿第四十页，共六十九页距離函數的特性（一）妥適定義(Well-defined)：兩點之間的距離永遠是可以找出來的，且大於零同位(Identity)：從一點到它本身的距離一定是交

17、換性(Commutatively)：距離沒有方向性，所以到的距離就是到的距離三角不等式(Triangle Inequality)A與C的距離小於或等於A與B的距離加B與C的距離本讲稿第四十一页，共六十九页距離函數的特性（二）妥適定義妥適定義確保每筆資料都一定有鄰近資料的存在，記憶基礎推理便是需要這些鄰近資料才能進行分析同位同位確保每筆資料最相似的資料就是它本身交換性交換性和三角不等式三角不等式則將鄰近資料限定在特定區域中，增加一筆新的資料進資料庫，不會改變現有資料間的距離本讲稿第四十二页，共六十九页資料差異性圖8.5的最鄰近資料是，但卻有與多筆比還近的鄰近資料本讲稿第四十三页，共六十九页一次建

18、立一個單變數的距離函數以幾何學的角度，距離很容易推理，但問題是，我們如何為多變數且不同資料型態的資料建立距離函數？答案是：次建立單一變數的距離函數，再組合起來。本讲稿第四十四页，共六十九页表8.7行銷資料庫中的五個顧客資料RECNUMGENDERAGESALARY1Female27$19,0002male51$64,0003male52$105,0004Female33$55,0005male45$45,000本讲稿第四十五页，共六十九页圖8.6三維分佈圖中展示五筆紀錄的分佈本讲稿第四十六页，共六十九页距離矩陣表8.8顧客年齡變數的距離矩陣2751523345270.000.961.000.2

19、40.72510.960.000.040.720.24521.000.040.000.760.28330.240.720.760.000.48450.720.240.280.480.00本讲稿第四十七页，共六十九页常見的距離加總方式加總：dsum(A,B)=dgender(A,B)+dage(A,B)+dsalary(A,B)標準化加總(Normalized Summation)：dnorm(A,B)=dsum(A,B)max(dsum)歐幾里得距離：dEuclid(A,B)=sqrt（dgender(A,B)2+dage(A,B)2+dsalary(A,B)2）本讲稿第四十八页，共六十九页表

20、8.9三種距離函數的最近似者組合此案例中，三種方式的結果完全樣是個巧合D sumD normD euclid11,4,5,2,31,4,5,2,31,4,5,2,322,5,3,4,12,5,3,4,12,5,3,4,133,2,5,4,13,2,5,4,13,2,5,4,144,1,5,2,34,1,5,2,34,1,5,2,355,2,3,4,15,2,3,4,15,2,3,4,1本讲稿第四十九页，共六十九页加入新的資料表8.10新顧客RECNUMGENDERAGESALARYnewfemale45$100,000本讲稿第五十页，共六十九页表8.11新顧客最近似者組合12345NEIGHB

21、ORSD sum1.6621.6591.3381.0031.6404,3,5,2,1D norm0.5540.5530.4460.3340.5474,3,5,2,1D euclid0.7811.0521.2510.4941.0004,1,5,2,3本讲稿第五十一页，共六十九页其他資料形式的距離函數郵遞區號電話號碼產品編號本讲稿第五十二页，共六十九页常見的組合函數民主方式(democracy)加權投票本讲稿第五十三页，共六十九页民主方式(democracy)記憶基礎推理可使用的組合函數就是讓最近似的個鄰近資料鄰近資料投票選出答案為了避免同票的情況，必須是奇數，當類別數為時，鄰近資料應該要有c+1

22、個本讲稿第五十四页，共六十九页民主方式案例表8.12顧客流失紀錄RECNUMGENDERAGESALARYINACTIVE1Female27$19,000No2male51$64,000Yes3male52$105,000Yes4Female33$55,000Yes5male45$45,000Nonewfemale45$100,000?本讲稿第五十五页，共六十九页民主方式案例表8.13 使用MBR判斷新顧客是否會流失 NEIGHBORSNEIGHBORATTRITIONK=1K=2K=3K=4K=5d sum4,3,5,2,1Y,Y,N,Y,Nyesyesyesyesyesd euclid4,

23、1,5,2,3Y,N,N,Y,Yyes?No?yesK=1K=2K=3K=4K=5d sumYes,100%Yes,100%Yes,67%Yes,75%Yes,60%d euclidYes,1005yes,50%No,67%Yes,50%Yes,60%表8.14 流失預測的信心水準本讲稿第五十六页，共六十九页加權投票加權投票(類似股東民主)和民主方式類似，不同之處在於每一票的加權值和他與新資料的距離成反比(距離加距離加1 1的倒數的倒數)加權對於結果和信心水準會有影響，主要的作用還是在消除鄰近資料為複數的情況下，無法判斷的結果(得票數相同)。至於使用或不使用加權，可透過使用測試資測試資料集料集

24、比較何者有較好的表現，再來決定例，見表8.15與8.16本讲稿第五十七页，共六十九页Collaborative Filtering:A Nearest Neighbor Approach to Making Recommendations本讲稿第五十八页，共六十九页合作篩選合作篩選共有三個步驟(為一個新顧客提供建議)：建立新顧客的Profile，即令新顧客對某些品項(例如電影、音樂、餐廳等)的偏好進行評分。使用相似性或距離的測量，比較新顧客與其它就顧客的profiles，找出偏好最接近的幾個顧客(鄰近資料集)利用某種combination function計算新顧客對某項尚未評分的品項的評分預

25、測值本讲稿第五十九页，共六十九页合作篩選案例圖8.7（1/2(-1)+1/4(-4)）（1/2+1/4）=-1.5/0.75=-2本讲稿第六十页，共六十九页A good collaborative filtering system gives its users a chance to comment on the predictions and adjust the profile accordingly.If it turns that the customer really like the item and gives it a rating of 4,his new profile

26、will be in slightly different neighborhood and original neighbors opinions will count less for this new customers next recommendation.本讲稿第六十一页，共六十九页八、結論本讲稿第六十二页，共六十九页獲得最佳結果MBR是一個很有效的Data Mining技術，它可以應用在許多的直接Data Mining問題上。1.選擇正確訓練資料集 (1)足夠的資料數量 (2)增加某些罕見分類項的資料數量 (3)約略相等的資料數量2.距離函數 (1)加總法：較具有緩衝效果 (2)

27、歐幾里得：注重每一個變數都必須維持在較小的差值本讲稿第六十三页，共六十九页獲得最佳結果(二).鄰近資料數量 (1).需要由“分布狀況”和“面對的問 題”決定 (2).鄰近資料的數量必須比分類項至少 多”.基本函數組合 加權投票對於類別變數有效，但在連續數值時，建議可以結合迴歸分析和最似鄰近資料模式，計算出最適線後，進行推測。本讲稿第六十四页，共六十九页MBR優點結論容易推測 MBR能列出最似鄰近資料的特性，方便我們看出結果是如何產生運用在任何資料型態、甚至是非關聯式資料上 只依靠兩種機制：距離函數與組合函數任何數量的變數下都能運作良好 MBR的效能主要是受訓練組資料的數量多寡決定，將較之下原始

28、 資料變數多寡，並不會有太大影響訓練資料集容易建立 當有新分類項產生時，可直接加入訓練資料組中本讲稿第六十五页，共六十九页MBR缺點在分類和預測上運算作業繁複需要一一運用距離含數計算出每一筆新資料和每一筆訓練資料組紀錄之間的差異訓練資料組需要大量紀錄MBR的訓練資料組就是模式，而資料數量越大越好，且必須要有 一定的樣本數目高度依賴距離函數和組合函數結果取決於距離函數和組合函數及鄰近資料數。本讲稿第六十六页，共六十九页何時應用MBR？MBR是一種對分類和預測都有效的直接式資料採礦技術，和其他技術比較起來，更能針對特定情形進行分析。1.整體規律性不能提供良好解釋時2.資料非常複雜時本讲稿第六十七页

29、，共六十九页SAS EM An assumption for the Memory-Based Reasoning node is that the variables that have status of use are numeric,orthogonal to each other,and standardized.You can use the Princomp/Dmneural or the Singular Value Decomposition nodes to generate numeric,orthogonal,and standardized variables tha

30、t can be used as inputs for the Memory-Based Reasoning node.本讲稿第六十八页，共六十九页In Enterprise Miner,the k-nearest neighbors are determined by the Euclidean distance between an observation and the probe.Based on the target values of the k-nearest neighbors,each of the k-nearest neighbors votes on the targe

31、t value for a probe.The votes are the posterior probabilities for the binary or nominal target variable.The following display shows the voting approach of these neighbors for a binary target variable when different values of k are specified.In this example,observations 7,12,35,108,and 334 are the fi

32、ve closest observations to the probe,where observations 108 and 35 have the shortest and the longest distances to the probe,respectively.The k-nearest neighbors are first k observations that have the closest distances to the probe.If the value of k is set to 3,then the target values of the first three nearest neighbors(108,12,and 7)are used.The target values for these three neighbors are Y,N,and Y.Therefore,the posterior probability for the probe to have the target value Y is 2/3(67%).本讲稿第六十九页，共六十九页