概念描述：特征化與比較(武漢大學(xué)-李春葆)

1、第第5章章 概念描述：特征化與比較概念描述：特征化與比較 n從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描述性挖掘和預(yù)從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描述性挖掘和預(yù) 測(cè)性挖掘。測(cè)性挖掘。 q描述性挖掘：描述性挖掘：以簡(jiǎn)潔概要的方式描述數(shù)據(jù)，并提供數(shù)據(jù)以簡(jiǎn)潔概要的方式描述數(shù)據(jù)，并提供數(shù)據(jù) 的有趣的一般性質(zhì)。的有趣的一般性質(zhì)。 q預(yù)測(cè)性數(shù)據(jù)挖掘：預(yù)測(cè)性數(shù)據(jù)挖掘：通過(guò)分析數(shù)據(jù)建立一個(gè)或一組模型，通過(guò)分析數(shù)據(jù)建立一個(gè)或一組模型， 并試圖預(yù)測(cè)新數(shù)據(jù)集的行為。并試圖預(yù)測(cè)新數(shù)據(jù)集的行為。 5.1 什么是概念描述？什么是概念描述？ n概念描述是以簡(jiǎn)潔的形式在更一般的（而不是在較低層的）概念描述是以簡(jiǎn)潔的形式在更一

2、般的（而不是在較低層的） 抽象層描述數(shù)據(jù)。抽象層描述數(shù)據(jù)。 q當(dāng)所描述的概念所指的是一類對(duì)象時(shí)，也稱為類描述。當(dāng)所描述的概念所指的是一類對(duì)象時(shí)，也稱為類描述。 n概念指的是一類數(shù)據(jù)的集合。概念指的是一類數(shù)據(jù)的集合。 qe.g. e.g. 研究生，大客戶。研究生，大客戶。 n概念描述產(chǎn)生特征化和比較描述。概念描述產(chǎn)生特征化和比較描述。 q特征化：提供給定數(shù)據(jù)集的簡(jiǎn)潔匯總。特征化：提供給定數(shù)據(jù)集的簡(jiǎn)潔匯總。 q區(qū)分：提供兩個(gè)或多個(gè)數(shù)據(jù)集的比較描述。區(qū)分：提供兩個(gè)或多個(gè)數(shù)據(jù)集的比較描述。 概念描述與概念描述與OLAP的區(qū)別的區(qū)別 n概念描述和數(shù)據(jù)倉(cāng)庫(kù)的聯(lián)機(jī)分析處理（概念描述和數(shù)據(jù)倉(cāng)庫(kù)的聯(lián)機(jī)分析處理（

3、OLAP）都跟數(shù)據(jù)）都跟數(shù)據(jù) 概化密切相關(guān)，即以簡(jiǎn)潔的形式在更一般的抽象層描述數(shù)概化密切相關(guān)，即以簡(jiǎn)潔的形式在更一般的抽象層描述數(shù) 據(jù)，允許數(shù)據(jù)在抽象層概化，便于考察數(shù)據(jù)的一般行為。據(jù)，允許數(shù)據(jù)在抽象層概化，便于考察數(shù)據(jù)的一般行為。 n兩者的主要區(qū)別：兩者的主要區(qū)別： q概念描述概念描述 n可以處理復(fù)雜數(shù)據(jù)類型的屬性及其聚集?？梢蕴幚韽?fù)雜數(shù)據(jù)類型的屬性及其聚集。 n一個(gè)更加自動(dòng)化的過(guò)程。一個(gè)更加自動(dòng)化的過(guò)程。 qOLAP n實(shí)際使用的實(shí)際使用的OLAP系統(tǒng)中，維和度量的數(shù)據(jù)類型都非系統(tǒng)中，維和度量的數(shù)據(jù)類型都非 常有限（非數(shù)值型的維和數(shù)值型的數(shù)據(jù)），表現(xiàn)為常有限（非數(shù)值型的維和數(shù)值型的數(shù)據(jù)），

4、表現(xiàn)為 一種簡(jiǎn)單的數(shù)據(jù)分析模型。一種簡(jiǎn)單的數(shù)據(jù)分析模型。 n一個(gè)由用戶控制的過(guò)程。一個(gè)由用戶控制的過(guò)程。 5.2 數(shù)據(jù)概化數(shù)據(jù)概化 n數(shù)據(jù)概化數(shù)據(jù)概化 q數(shù)據(jù)庫(kù)中的數(shù)據(jù)和對(duì)象通常包含原始概念層的細(xì)節(jié)信息，數(shù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)和對(duì)象通常包含原始概念層的細(xì)節(jié)信息，數(shù) 據(jù)概化就是將數(shù)據(jù)庫(kù)中的跟任務(wù)相關(guān)的數(shù)據(jù)集從較低的概念據(jù)概化就是將數(shù)據(jù)庫(kù)中的跟任務(wù)相關(guān)的數(shù)據(jù)集從較低的概念 層抽象到較高的概念層的過(guò)程。層抽象到較高的概念層的過(guò)程。 n主要方法：主要方法： q數(shù)據(jù)立方體（數(shù)據(jù)立方體（OLAP使用的方法）使用的方法） q面向?qū)傩缘臍w納方法面向?qū)傩缘臍w納方法 1 2 3 4 5 概念層概念層 5.2.1 數(shù)據(jù)概

5、化：數(shù)據(jù)立方體方法數(shù)據(jù)概化：數(shù)據(jù)立方體方法 n執(zhí)行計(jì)算并將結(jié)果存儲(chǔ)在數(shù)據(jù)立方體中。執(zhí)行計(jì)算并將結(jié)果存儲(chǔ)在數(shù)據(jù)立方體中。 n優(yōu)點(diǎn)：優(yōu)點(diǎn)： q數(shù)據(jù)概化的一種有效實(shí)現(xiàn)。數(shù)據(jù)概化的一種有效實(shí)現(xiàn)。 q可以計(jì)算各種不同的度量值。可以計(jì)算各種不同的度量值。 n比如：比如：count(), sum(), average(), max() q概化和特征分析通過(guò)一系列的數(shù)據(jù)立方體操作完成，比如上概化和特征分析通過(guò)一系列的數(shù)據(jù)立方體操作完成，比如上 卷、下鉆等。卷、下鉆等。 n缺點(diǎn)：缺點(diǎn)： q只能處理非數(shù)值類型的維和簡(jiǎn)單聚集數(shù)值類型的度量值（大只能處理非數(shù)值類型的維和簡(jiǎn)單聚集數(shù)值類型的度量值（大 部分現(xiàn)有商業(yè)系統(tǒng)中

6、，只能為非數(shù)值類型的維產(chǎn)生概念分部分現(xiàn)有商業(yè)系統(tǒng)中，只能為非數(shù)值類型的維產(chǎn)生概念分 層）。層）。 q缺乏智能分析，不能自動(dòng)確定分析中該使用哪些維，應(yīng)該概缺乏智能分析，不能自動(dòng)確定分析中該使用哪些維，應(yīng)該概 化到哪個(gè)層次?；侥膫€(gè)層次。 5.2.2 面向?qū)傩缘臍w納面向?qū)傩缘臍w納 特點(diǎn)：特點(diǎn)： n一種面向關(guān)系數(shù)據(jù)查詢的、基于匯總的在線數(shù)據(jù)分析技術(shù)。一種面向關(guān)系數(shù)據(jù)查詢的、基于匯總的在線數(shù)據(jù)分析技術(shù)。 n受數(shù)據(jù)類型和度量類型的約束比較少。受數(shù)據(jù)類型和度量類型的約束比較少。 1. 面向?qū)傩缘臍w納的基本步驟面向?qū)傩缘臍w納的基本步驟 n數(shù)據(jù)收集。獲得初始工作關(guān)系。數(shù)據(jù)收集。獲得初始工作關(guān)系。 n進(jìn)行面向?qū)?/p>

7、性的歸納。進(jìn)行面向?qū)傩缘臍w納。 q基本操作是數(shù)據(jù)概化，對(duì)有大量不同值的屬性，進(jìn)行進(jìn)基本操作是數(shù)據(jù)概化，對(duì)有大量不同值的屬性，進(jìn)行進(jìn) 一步概化。一步概化。 n屬性刪除屬性刪除 n屬性概化屬性概化 q屬性概化控制：控制概化過(guò)程，確定有多少不同的值才屬性概化控制：控制概化過(guò)程，確定有多少不同的值才 算是有大量不同值的屬性。算是有大量不同值的屬性。 n屬性概化臨界值控制屬性概化臨界值控制 n概化關(guān)系臨界值控制概化關(guān)系臨界值控制 （1） 數(shù)據(jù)收集數(shù)據(jù)收集 n目的：獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，在目的：獲得跟任務(wù)相關(guān)的數(shù)據(jù)集，包括屬性或維，在DMQL中中 他們由他們由in relevance to

8、子句表示。子句表示。 n示例：示例： qDMQL: 描述描述Big-University數(shù)據(jù)庫(kù)中研究生的一般特征數(shù)據(jù)庫(kù)中研究生的一般特征: use Big_University_DB mine characteristics as “Science_Students” in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpa from student where status in “graduate” q將數(shù)據(jù)挖掘查詢轉(zhuǎn)換為關(guān)系查詢：將數(shù)據(jù)挖掘查詢轉(zhuǎn)換為關(guān)系查詢： Select n

9、ame, gender, major, birth_place, birth_date, residence, phone#, gpa from student where status in “Msc”, “MBA”, “PhD” 產(chǎn)生的結(jié)果表：產(chǎn)生的結(jié)果表： n數(shù)據(jù)收集時(shí)的困難數(shù)據(jù)收集時(shí)的困難 q用戶在指定相關(guān)的數(shù)據(jù)集方面存在困難，遺漏在描用戶在指定相關(guān)的數(shù)據(jù)集方面存在困難，遺漏在描 述中可能起作用的屬性。述中可能起作用的屬性。 q用戶可能引進(jìn)太多的屬性。用戶可能引進(jìn)太多的屬性。 （2）數(shù)據(jù)概化）數(shù)據(jù)概化 n數(shù)據(jù)概化的兩種常用方法：屬性刪除和屬性概化數(shù)據(jù)概化的兩種常用方法：屬性刪除和屬性概

10、化 q屬性刪除的適用規(guī)則：對(duì)初始工作關(guān)系中具有大量不同屬性刪除的適用規(guī)則：對(duì)初始工作關(guān)系中具有大量不同 值的屬性，符合以下情況，應(yīng)使用屬性刪除：值的屬性，符合以下情況，應(yīng)使用屬性刪除： n在此屬性上沒(méi)有概化操作符（比如該屬性沒(méi)有定義在此屬性上沒(méi)有概化操作符（比如該屬性沒(méi)有定義 相關(guān)的概念分層）。相關(guān)的概念分層）。 n該屬性的較高層概念用其他屬性表示。該屬性的較高層概念用其他屬性表示。 q屬性概化的使用規(guī)則：如果初始工作關(guān)系中的某個(gè)屬性屬性概化的使用規(guī)則：如果初始工作關(guān)系中的某個(gè)屬性 具有大量不同值，且該屬性上存在概化操作符，則使用具有大量不同值，且該屬性上存在概化操作符，則使用 該概化操作符對(duì)

11、該屬性進(jìn)行數(shù)據(jù)概化操作。該概化操作符對(duì)該屬性進(jìn)行數(shù)據(jù)概化操作。 屬性概化控制屬性概化控制 n確定什么是確定什么是“具有大量的不同值具有大量的不同值”，控制將屬性概化到多，控制將屬性概化到多 高的抽象層。高的抽象層。 n屬性概化控制的兩種常用方法：屬性概化控制的兩種常用方法： q屬性概化臨界值控制屬性概化臨界值控制 n對(duì)所有屬性設(shè)置一個(gè)概化臨界值或者是對(duì)每個(gè)屬性都對(duì)所有屬性設(shè)置一個(gè)概化臨界值或者是對(duì)每個(gè)屬性都 設(shè)置一個(gè)臨界值（一般為設(shè)置一個(gè)臨界值（一般為2到到8）。）。 q概化關(guān)系臨界值控制概化關(guān)系臨界值控制 n為概化關(guān)系設(shè)置一個(gè)臨界值，確定概化關(guān)系中，不同為概化關(guān)系設(shè)置一個(gè)臨界值，確定概化關(guān)系

12、中，不同 元組的個(gè)數(shù)的最大值。（通常為元組的個(gè)數(shù)的最大值。（通常為10到到30，應(yīng)該允許在，應(yīng)該允許在 實(shí)際應(yīng)用中進(jìn)行調(diào)整）。實(shí)際應(yīng)用中進(jìn)行調(diào)整）。 q兩種技術(shù)的順序使用：使用屬性概化臨界值控制來(lái)概化兩種技術(shù)的順序使用：使用屬性概化臨界值控制來(lái)概化 每個(gè)屬性，然后使用關(guān)系臨界值控制進(jìn)一步壓縮概化的每個(gè)屬性，然后使用關(guān)系臨界值控制進(jìn)一步壓縮概化的 關(guān)系。關(guān)系。 n相等元組的合并、累計(jì)計(jì)數(shù)和其他聚集值。相等元組的合并、累計(jì)計(jì)數(shù)和其他聚集值。 當(dāng)屬性不同值個(gè)數(shù)大于某閾值，刪除或概化。當(dāng)屬性不同值個(gè)數(shù)大于某閾值，刪除或概化。 當(dāng)概化關(guān)系中不同元組個(gè)數(shù)超過(guò)閾值，當(dāng)概化關(guān)系中不同元組個(gè)數(shù)超過(guò)閾值， 進(jìn)一步

13、概化；否則不再概化。進(jìn)一步概化；否則不再概化。 面向?qū)傩缘臍w納面向?qū)傩缘臍w納示例示例 n挖掘挖掘Big-University數(shù)據(jù)庫(kù)中研究生的一般特征：數(shù)據(jù)庫(kù)中研究生的一般特征： qname（姓名）：刪除屬性。（姓名）：刪除屬性。 qgender（性別）：只有兩值，保留該屬性，不概化。（性別）：只有兩值，保留該屬性，不概化。 qmajor（專業(yè)）：根據(jù)概念分層向上攀升（專業(yè)）：根據(jù)概念分層向上攀升文，理，工文，理，工。 qbirth_place（出生地）：根據(jù)概念分層（出生地）：根據(jù)概念分層location向上攀升。向上攀升。 qbirth_date（出生日期）：概化為（出生日期）：概化為age

14、，再概化為，再概化為age_range。 qresidence（住址）：根據(jù)概念分層（住址）：根據(jù)概念分層location向上攀升。向上攀升。 qphone#（電話）：刪除屬性。（電話）：刪除屬性。 qgpa（成績(jī)）：根據(jù)（成績(jī)）：根據(jù)GPA的分級(jí)作為概念分層。的分級(jí)作為概念分層。 通過(guò)面向?qū)傩詺w納得到的主概化關(guān)系：通過(guò)面向?qū)傩詺w納得到的主概化關(guān)系： gendermajorbirth_country age_range residence_city gpa count M Science Canada 20.25 Richmond very_good 16 F Science Foreign

15、25.30 Burnaby excellent 22 . 5.2.2 面向?qū)傩缘臍w納算法面向?qū)傩缘臍w納算法 n輸入輸入 q1. DB; 2. 數(shù)據(jù)挖掘查詢數(shù)據(jù)挖掘查詢DMQuery; 3. 屬性列表屬性列表; 4. 屬性的概念分層屬性的概念分層; 屬性的概化臨界值；屬性的概化臨界值； n輸出輸出 q主概化關(guān)系主概化關(guān)系P n算法描述：算法描述： 1.W get_task_relevant_data(DMQuery, DB) 2.prepare_for_generalization(W)/預(yù)處理預(yù)處理 1.掃描掃描W，收集每個(gè)屬性，收集每個(gè)屬性a的不同值。的不同值。 2.對(duì)每個(gè)屬性對(duì)每個(gè)屬性a，

16、根據(jù)臨界值確定是否刪除，如果不刪除，則計(jì)算其最小，根據(jù)臨界值確定是否刪除，如果不刪除，則計(jì)算其最小 期望層次期望層次L，并確定映射對(duì)，并確定映射對(duì)(v,v)。 3.P generalization(W) q通過(guò)使用通過(guò)使用v代替代替W中每個(gè)中每個(gè)v，累計(jì)計(jì)數(shù)并計(jì)算所有聚集值，導(dǎo)出，累計(jì)計(jì)數(shù)并計(jì)算所有聚集值，導(dǎo)出P。 1.每個(gè)概化元組的插入或累積計(jì)數(shù)。每個(gè)概化元組的插入或累積計(jì)數(shù)。 2.用數(shù)組表示用數(shù)組表示P。 主概化關(guān)系主概化關(guān)系 相關(guān)數(shù)據(jù)集合相關(guān)數(shù)據(jù)集合 學(xué)號(hào)學(xué)號(hào)性別性別分?jǐn)?shù)分?jǐn)?shù) 1男男85 2女女90 3男男76 4男男96 5男男62 6女女88 7女女93 all A 90 B 808

17、9 C 7079 D 6069 E 60 分?jǐn)?shù)：概念分層分?jǐn)?shù)：概念分層 性別性別分?jǐn)?shù)分?jǐn)?shù)個(gè)數(shù)個(gè)數(shù) 男男A1 男男B1 男男C1 女女A2 女女B1 5.2.3 導(dǎo)出概化的表示導(dǎo)出概化的表示 n概化關(guān)系概化關(guān)系 q一部分或者所有屬性得到概化的關(guān)系，包含計(jì)數(shù)或其他一部分或者所有屬性得到概化的關(guān)系，包含計(jì)數(shù)或其他 度量值的聚集。度量值的聚集。 locationitemsalescount 亞洲亞洲 TV 15 300 歐洲歐洲 TV 12 250 北美北美 TV 28 450 亞洲亞洲 計(jì)算機(jī)計(jì)算機(jī)15 300 歐洲歐洲 計(jì)算機(jī)計(jì)算機(jī) 12 250 北美北美 計(jì)算機(jī)計(jì)算機(jī)28 450 某年銷售某年銷

18、售 概化關(guān)系概化關(guān)系 n交叉表交叉表 q二維交叉表使用每行顯示一個(gè)屬性，使用每列顯示二維交叉表使用每行顯示一個(gè)屬性，使用每列顯示 另外一個(gè)屬性將結(jié)果集映射到表中。另外一個(gè)屬性將結(jié)果集映射到表中。 q可視化技巧：可視化技巧： n條形圖、餅圖、曲線和數(shù)據(jù)立方體瀏覽工具（用單元的大條形圖、餅圖、曲線和數(shù)據(jù)立方體瀏覽工具（用單元的大 小代表計(jì)數(shù)，用單元亮度代表另外的度量）。小代表計(jì)數(shù)，用單元亮度代表另外的度量）。 locationitemTV計(jì)算機(jī)兩項(xiàng)和計(jì)算機(jī)兩項(xiàng)和 salescountsalescountsalescount 亞洲亞洲15300 120 10001351300 歐洲歐洲 . 北美北美

19、 . 所有地區(qū)所有地區(qū) . n量化規(guī)則量化規(guī)則 q使用使用t_weight表示主概化關(guān)系中每個(gè)元組的典型性表示主概化關(guān)系中每個(gè)元組的典型性 n量化特征規(guī)則量化特征規(guī)則 q將概化的結(jié)果映射到相應(yīng)的量化特征規(guī)則中，比如：將概化的結(jié)果映射到相應(yīng)的量化特征規(guī)則中，比如： n i ia qcountqcountweightt 1 )(/ )(_ : )(.: )()(_arg , mmll wtXconditionwtXconditionXclassettX %45: ) )( .%25: ) )( )( , tAmericanNorth XlocationtAsiaXlocationcomputerX

20、itemX 量化特征規(guī)則中每個(gè)條件的析取成為目標(biāo)類的一個(gè)必要條件；亦即，量化特征規(guī)則中每個(gè)條件的析取成為目標(biāo)類的一個(gè)必要條件；亦即， 如果如果X在目標(biāo)類中，則在目標(biāo)類中，則X滿足滿足conditioni的概率是的概率是wi： 興趣度度量興趣度度量 一個(gè)關(guān)于維一個(gè)關(guān)于維item、location和和cost的數(shù)據(jù)立方體，的數(shù)據(jù)立方體， 單元的單元的size表示對(duì)應(yīng)單元的計(jì)數(shù)，單元的亮度表示另一表示對(duì)應(yīng)單元的計(jì)數(shù)，單元的亮度表示另一 個(gè)度量，如個(gè)度量，如sum(sales)?？梢赃M(jìn)行旋轉(zhuǎn)、上卷、下鉆、?？梢赃M(jìn)行旋轉(zhuǎn)、上卷、下鉆、 切片和切塊操作，在數(shù)據(jù)立方體瀏覽器中顯示。切片和切塊操作，在數(shù)據(jù)立方

21、體瀏覽器中顯示。 5.3 解析特征化：屬性相關(guān)分析解析特征化：屬性相關(guān)分析 n特征化過(guò)程中的兩大困難特征化過(guò)程中的兩大困難 q復(fù)雜數(shù)據(jù)類型的處理。復(fù)雜數(shù)據(jù)類型的處理。 q缺乏一種自動(dòng)概化的過(guò)程，用戶必須告訴系統(tǒng)。缺乏一種自動(dòng)概化的過(guò)程，用戶必須告訴系統(tǒng)。 n哪些屬性或維應(yīng)該包括在類特征化中。哪些屬性或維應(yīng)該包括在類特征化中。 n每個(gè)維應(yīng)該概化到多高的程度。每個(gè)維應(yīng)該概化到多高的程度。 確定哪些維或?qū)傩允歉叨认嚓P(guān)的確定哪些維或?qū)傩允歉叨认嚓P(guān)的保留這樣的屬性或保留這樣的屬性或 維：其值可以用于區(qū)分該類與其他類。維：其值可以用于區(qū)分該類與其他類。 5.3.1 為什么進(jìn)行屬性相關(guān)分析？為什么進(jìn)行屬性相

22、關(guān)分析？ n數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)和OLAP系統(tǒng)中的多維數(shù)據(jù)分析缺乏一個(gè)自動(dòng)概系統(tǒng)中的多維數(shù)據(jù)分析缺乏一個(gè)自動(dòng)概 化過(guò)程，這使得這個(gè)過(guò)程中需要有很多用戶干預(yù)?；^(guò)程，這使得這個(gè)過(guò)程中需要有很多用戶干預(yù)。 q用戶必須告訴系統(tǒng)哪些維或?qū)傩詰?yīng)當(dāng)包含在類分析中用戶必須告訴系統(tǒng)哪些維或?qū)傩詰?yīng)當(dāng)包含在類分析中 （難）。（難）。 n屬性太少，則造成挖掘的描述結(jié)果不正確屬性太少，則造成挖掘的描述結(jié)果不正確 n屬性太多，浪費(fèi)計(jì)算、淹沒(méi)知識(shí)屬性太多，浪費(fèi)計(jì)算、淹沒(méi)知識(shí) q告訴系統(tǒng)每個(gè)維應(yīng)當(dāng)概化到多高的層次告訴系統(tǒng)每個(gè)維應(yīng)當(dāng)概化到多高的層次 （易）。（易）。 n直接通過(guò)概化的臨界值，說(shuō)明給定維應(yīng)當(dāng)達(dá)到的概化程度直接通過(guò)

23、概化的臨界值，說(shuō)明給定維應(yīng)當(dāng)達(dá)到的概化程度 n對(duì)概化層次不滿意，則可以指定需要上卷或下鉆的維對(duì)概化層次不滿意，則可以指定需要上卷或下鉆的維 5.3.2屬性相關(guān)分析的方法屬性相關(guān)分析的方法 n屬性相關(guān)分析的基本思想是計(jì)算某種度量，用于屬性相關(guān)分析的基本思想是計(jì)算某種度量，用于量化屬性量化屬性 與給定類或概念的相關(guān)性與給定類或概念的相關(guān)性。 q可采用的度量包括：信息增益、可采用的度量包括：信息增益、Gini索引、不確定性和索引、不確定性和 相關(guān)系數(shù)。（涉及機(jī)器學(xué)習(xí)、統(tǒng)計(jì)、模糊和粗糙集理論相關(guān)系數(shù)。（涉及機(jī)器學(xué)習(xí)、統(tǒng)計(jì)、模糊和粗糙集理論 等方面的相關(guān)知識(shí)）等方面的相關(guān)知識(shí)） q比如：比如：信息增益信

24、息增益通過(guò)計(jì)算一個(gè)樣本分類的期望信息和屬通過(guò)計(jì)算一個(gè)樣本分類的期望信息和屬 性的熵來(lái)獲得一個(gè)屬性的信息增益，判定該屬性與當(dāng)前性的熵來(lái)獲得一個(gè)屬性的信息增益，判定該屬性與當(dāng)前 的特征化任務(wù)的相關(guān)性。的特征化任務(wù)的相關(guān)性。 信息增益方法信息增益方法 nS是一個(gè)訓(xùn)練樣本的集合，該樣本中已知每個(gè)集合的類編號(hào)。是一個(gè)訓(xùn)練樣本的集合，該樣本中已知每個(gè)集合的類編號(hào)。 每個(gè)樣本為一個(gè)元組。有個(gè)屬性用來(lái)判定某個(gè)訓(xùn)練樣本的類每個(gè)樣本為一個(gè)元組。有個(gè)屬性用來(lái)判定某個(gè)訓(xùn)練樣本的類 編號(hào)（類似于學(xué)生記錄中的編號(hào)（類似于學(xué)生記錄中的status屬性）。屬性）。 n假設(shè)假設(shè)S中有中有m個(gè)類，總共個(gè)類，總共s個(gè)訓(xùn)練樣本，每個(gè)

25、類個(gè)訓(xùn)練樣本，每個(gè)類ci有有Si個(gè)樣本（個(gè)樣本（i 1,2,3.m），那么任意一個(gè)樣本屬于類），那么任意一個(gè)樣本屬于類Ci的概率是的概率是si / s，那，那 么用來(lái)分類一個(gè)給定樣本的么用來(lái)分類一個(gè)給定樣本的期望信息期望信息是：是： s s s s sssI i m i i m2 1 21 log),.,( c1 c2 c3 cm s個(gè)樣本分為個(gè)樣本分為m個(gè)類個(gè)類 s1 s2 s3 sm n對(duì)于屬性對(duì)于屬性A，有，有v個(gè)值的個(gè)值的a1,a2,.,av，可以將，可以將S分成分成v個(gè)子集個(gè)子集 S1,S2,.,Sv，其中，其中Sj包含包含S中屬性中屬性A上的值為上的值為aj的樣本。假的樣本。假 設(shè)

26、設(shè)Sj包含類包含類Ci的的sij個(gè)樣本。根據(jù)個(gè)樣本。根據(jù)A的這種劃分的期望信息的這種劃分的期望信息 稱為稱為A的熵：的熵： ),.,( . )( 1 1 1 mjj v j mjj ssI s ss AE a1a2a3av S1S2S3 Sv 屬性屬性A： 類類Ci 1im si1si2si3 siv nA上該劃分的獲得的信息增益定義為：上該劃分的獲得的信息增益定義為： n具有高信息增益的屬性，是給定集合中具有高區(qū)分度的屬具有高信息增益的屬性，是給定集合中具有高區(qū)分度的屬 性。所以可以通過(guò)計(jì)算性。所以可以通過(guò)計(jì)算S中樣本的每個(gè)屬性的信息增益，中樣本的每個(gè)屬性的信息增益， 來(lái)得到一個(gè)屬性的相關(guān)性

27、的排序。來(lái)得到一個(gè)屬性的相關(guān)性的排序。 )(),.,()( 21 AEsssIAGain m 示例示例 n任務(wù)任務(wù):使用解析特征化挖掘使用解析特征化挖掘BigUniversity的研究生的一的研究生的一 般特征描述。般特征描述。 n給定：給定： q屬性屬性name, gender, major, birth_place, birth_date, phone#和和gpa。 qUi = 屬性分析閥值。屬性分析閥值。 qTi = 屬性概化閥值。屬性概化閥值。 qR = 屬性相關(guān)閥值。屬性相關(guān)閥值。 n1. 數(shù)據(jù)收集數(shù)據(jù)收集 q目標(biāo)類：研究生目標(biāo)類：研究生 q對(duì)比類：本科生對(duì)比類：本科生 n2. 使用

28、保守的閥值使用保守的閥值Ui和和Ti進(jìn)行進(jìn)行AOI（面向?qū)傩缘臍w納）（面向?qū)傩缘臍w納） q屬性刪除屬性刪除 nname和和phone# q屬性概化屬性概化 n概化概化major, birth_place, birth_date 和和 gpa q進(jìn)行累積計(jì)數(shù)進(jìn)行累積計(jì)數(shù) q候選關(guān)系：候選關(guān)系：gender, major, birth_country, age_range 和和gpa gendermajorbirth_countryage_rangegpacount MScienceCanada20-25Very_good16 FScienceForeign25-30Excellent22 MEn

29、gineeringForeign25-30Excellent18 FScienceForeign25-30Excellent25 MScienceCanada20-25Excellent21 FEngineeringCanada20-25Excellent18 目標(biāo)類候選關(guān)系：目標(biāo)類候選關(guān)系：研究生研究生( =120) gendermajorbirth_countryage_rangegpacount MScienceForeign20Very_good18 FBusinessCanada20Fair20 MBusinessCanada20Fair22 FScienceCanada20-25Fair24 MEngineering Foreign20-25Very_good22 FEngineering Canada20Excellent24 對(duì)比類候選關(guān)系：對(duì)比類候選關(guān)系：本科生本科生 ( =130) (可以在類比較時(shí)使用）可以在類比較時(shí)使用） n3. 相關(guān)性分析相關(guān)性分析 q計(jì)算給定的樣本分類所需要的期望信息計(jì)算給定的樣本分類所需要的期望信息 q計(jì)算每個(gè)屬性的熵計(jì)算每個(gè)屬性的熵: e.g. major（屬性）（屬性） 99880 250 130 250 130 250