智慧城市大數(shù)據(jù)方案關(guān)鍵技術(shù)課件

1、智慧城市大數(shù)據(jù)方案關(guān)鍵技術(shù)一、大數(shù)據(jù)、物聯(lián)網(wǎng)、智慧城市智慧城市大數(shù)據(jù)（云計(jì)算）物聯(lián)網(wǎng)智慧 交通智慧 醫(yī)療智能電網(wǎng)數(shù)據(jù)采集數(shù)據(jù)處理智慧 旅游智慧城市：運(yùn)用先進(jìn)的信 息技術(shù)，實(shí)現(xiàn)城市智慧管 理與運(yùn)行，為城市中的人 創(chuàng)造更美好的生活。物聯(lián)網(wǎng)：通過RFID、 GPS、傳感器等傳感 設(shè)備與互聯(lián)網(wǎng)連接起 來，進(jìn)行信息交換和 通訊，實(shí)現(xiàn)智能化識(shí) 別、定位、監(jiān)控與管 理。大數(shù)據(jù)：大小超 出傳統(tǒng)數(shù)據(jù)處理 工具存儲(chǔ)、處理 分析、能力的數(shù)據(jù)集。（麥肯錫）二、大數(shù)據(jù)數(shù)據(jù)質(zhì)量、處理框架及測評(píng)概述1數(shù)據(jù)質(zhì)量及評(píng)估2分布式數(shù)據(jù)處理框架及測評(píng)3大數(shù)據(jù)的基準(zhǔn)測試4概述 大數(shù)據(jù)環(huán)境下，傳統(tǒng)的數(shù)據(jù)處理技術(shù)無法滿足對(duì)大數(shù)據(jù)量 分析和

2、處理的要求，大數(shù)據(jù)治理、大數(shù)據(jù)處理技術(shù)應(yīng)運(yùn)而 生。 數(shù)據(jù)來源的不同、數(shù)據(jù)形式的多元化，使得數(shù)據(jù)質(zhì)量存在 較大的差異，不正確或者不一致的數(shù)據(jù)可能嚴(yán)重影響數(shù)據(jù) 分析效果。Hadoop、Spark為代表的各種大數(shù)據(jù)框架不斷涌現(xiàn)，這些數(shù) 據(jù)處理框架方便了大數(shù)據(jù)應(yīng)用的編寫，但是由于其分布性 和封裝性，給應(yīng)用程序的測試帶來巨大挑戰(zhàn)。大數(shù)據(jù)處理流程使用相關(guān)工具對(duì)分布廣泛的非結(jié)構(gòu)化的數(shù)據(jù)源進(jìn) 行抽取/采集，并進(jìn)行數(shù)據(jù)傳輸采用合適的模式/標(biāo)準(zhǔn)對(duì)數(shù)據(jù)進(jìn)行統(tǒng)一存儲(chǔ)利用智能算法，對(duì)數(shù)據(jù)進(jìn)行分析處理數(shù)據(jù)分析處理的結(jié)果，通過可視化的方法，提供 給大數(shù)據(jù)應(yīng)用（預(yù)測、分析報(bào)表、）數(shù)據(jù)源數(shù)據(jù)集成關(guān)系數(shù)據(jù)庫數(shù)據(jù)集成實(shí)體 數(shù)據(jù)質(zhì)量

3、聚類和關(guān)聯(lián)模式數(shù)據(jù)質(zhì)量應(yīng)用可視化目錄概述1數(shù)據(jù)質(zhì)量及評(píng)估2分布式數(shù)據(jù)處理模型及測試3大數(shù)據(jù)的基準(zhǔn)測試4數(shù)據(jù)質(zhì)量定義目前數(shù)據(jù)質(zhì)量還沒有統(tǒng)一的定義形式數(shù)據(jù)質(zhì)量為信息系統(tǒng)對(duì)模式和數(shù)據(jù)實(shí)例的一致性、正確性、完整性和最小性的滿足程度數(shù)據(jù)質(zhì)量是數(shù)據(jù)適合使用的程度數(shù)據(jù)質(zhì)量是數(shù)據(jù)滿足特定用戶期望的程度數(shù)據(jù)質(zhì)量的內(nèi)容 數(shù)據(jù)真實(shí)性：數(shù)據(jù)真實(shí)并且準(zhǔn)確地反映實(shí)際 的業(yè)務(wù)數(shù)據(jù)完備性：數(shù)據(jù)充分，沒有遺漏任何有關(guān)的操作數(shù)據(jù) 數(shù)據(jù)自治性：數(shù)據(jù)不是孤立存在而是通過不 同的約束互相關(guān)聯(lián)，在滿足數(shù)據(jù)之間關(guān)聯(lián)關(guān) 系的同時(shí)不違反相關(guān)約束數(shù)據(jù)質(zhì)量問題（臟數(shù)據(jù)來自哪里？） 數(shù)據(jù)源本身是臟數(shù)據(jù) 數(shù)據(jù)轉(zhuǎn)換/集成 數(shù)據(jù)本身價(jià)值的失效 數(shù)據(jù)質(zhì)量問

4、題分類10單數(shù)據(jù)源 數(shù)據(jù)質(zhì)量 問題模式層缺少完整性約束，糟糕的設(shè)計(jì)模式 1) 缺少唯一性約束2) 缺少引用約束實(shí)例層數(shù)據(jù)記錄錯(cuò)誤 1) 拼寫錯(cuò)誤2) 相似重復(fù)記錄3) 互相矛盾的字段多數(shù)據(jù)源 數(shù)據(jù)質(zhì)量 問題模式層異質(zhì)的數(shù)據(jù)模型和模式設(shè)計(jì) 1) 命名沖突2) 結(jié)構(gòu)沖突實(shí)例層冗余、互相矛盾或不一致的數(shù)據(jù) 1) 不一致的匯總2) 不一致的時(shí)間選擇數(shù)據(jù)質(zhì)量控制方法使用靜態(tài)的模式約束不允許空值、外鍵的約束等工作流中的動(dòng)態(tài)約束訂單額超過200美元的訂單交給ID為2的業(yè)務(wù)員操作約束遵循80-20原則少數(shù)幾個(gè)約束，能解決多數(shù)數(shù)據(jù)質(zhì)量問題數(shù)據(jù)預(yù)處理 數(shù)據(jù)預(yù)處理通常是指在數(shù)據(jù)存儲(chǔ)、分析之 前對(duì)數(shù)據(jù)的處理。使用數(shù)據(jù)

5、預(yù)處理技術(shù)能 夠提高數(shù)據(jù)質(zhì)量，提升數(shù)據(jù)分析的效果。數(shù)據(jù)預(yù)處理一般包含以下幾個(gè)步驟數(shù)據(jù)清洗（Data Cleaning）數(shù)據(jù)變換 (Data Transformation)數(shù)據(jù)集成 (Data Integration)數(shù)據(jù)規(guī)約 (Data Reduction)數(shù)據(jù)清洗數(shù)據(jù)清理主要是用如統(tǒng)計(jì)分析、預(yù)定義規(guī)則等相關(guān) 技術(shù)將“臟數(shù)據(jù)”轉(zhuǎn)換為滿足數(shù)據(jù)質(zhì)量要求的數(shù)據(jù)。數(shù)據(jù)清洗所處理的主要問題有：清理規(guī)則數(shù)據(jù)清理手工清理自動(dòng)清理滿足數(shù)據(jù)質(zhì)量 要求的數(shù)據(jù)臟數(shù)據(jù) 缺失的數(shù)據(jù)（Missing Data）-屬性缺失單位誤匹配（Unit mismatch）-$ vs. ￥實(shí)體解析（Entity Resolution）

6、-IBM vs. International Business Machines孤立點(diǎn)（Outlier）數(shù)據(jù)錯(cuò)誤（Data Error） 業(yè)務(wù)知識(shí)清理算法數(shù)據(jù)集成/數(shù)據(jù)變換 數(shù)據(jù)集成整合來自多個(gè)數(shù)據(jù)存儲(chǔ)的數(shù) 據(jù)，為數(shù)據(jù)分析、處理、挖掘提供完整的 數(shù)據(jù)源。數(shù)據(jù)變換將數(shù)據(jù)變換或統(tǒng)一成適合于數(shù)據(jù)分析挖掘的形式。數(shù)據(jù)集成中數(shù)據(jù)質(zhì)量問題分類問題類型問題描述數(shù)據(jù)表連接不 匹配來自多個(gè)數(shù)據(jù)源中的數(shù)據(jù)表需要通過相同的主鍵進(jìn)行 自然連接，當(dāng)表中的主鍵不匹配時(shí)，出現(xiàn)無法連接的 現(xiàn)象冗余在連接數(shù)據(jù)表的過程中，沒有對(duì)表中的字段嚴(yán)格選擇 后就連接，造成了大量的數(shù)據(jù)冗余數(shù)據(jù)值沖突不同數(shù)據(jù)源中不同的屬性值，導(dǎo)致數(shù)據(jù)表連接字

7、段的 類型的沖突。數(shù)據(jù)變換處理內(nèi)容數(shù)據(jù)分類描述屬性的數(shù)據(jù)類型轉(zhuǎn)換當(dāng)屬性之間的取值范圍可能相差很大時(shí)，要進(jìn)行 數(shù)據(jù)的映射處理，映射關(guān)系可以與平方根、標(biāo)準(zhǔn) 方差以及區(qū)域?qū)?yīng)屬性構(gòu)造根據(jù)已有的屬性集構(gòu)造新的屬性，以幫助數(shù)據(jù)挖 掘過程數(shù)據(jù)離散化將連續(xù)取值的屬性離散化成若干區(qū)間，來幫助消減一個(gè)連續(xù)屬性的取值個(gè)數(shù)數(shù)據(jù)標(biāo)準(zhǔn)化不同來源所得到的相同字段定義可能不一樣，比 如重量統(tǒng)一標(biāo)準(zhǔn)化為kg數(shù)據(jù)規(guī)約 數(shù)據(jù)規(guī)約獲得數(shù)據(jù)集的簡化表示（簡 稱近似子集），并且近似子集的信息表達(dá) 能力與原數(shù)據(jù)集非常接近。 屬性選擇是根據(jù)用戶的指標(biāo)選擇一個(gè)優(yōu)化屬性子 集的過程。優(yōu)化屬性子集可以是屬性數(shù)目最小的子 集，也可以是含有最佳預(yù)測

8、準(zhǔn)確率的子集。 實(shí)例選擇使用部分?jǐn)?shù)據(jù)記錄代替原來所有的數(shù)據(jù) 記錄進(jìn)行數(shù)據(jù)挖掘，減少了挖掘時(shí)間和降低了挖掘 資源的代價(jià)，獲得了更高效的挖掘性能。數(shù)據(jù)質(zhì)量測評(píng)數(shù)據(jù)質(zhì)量的評(píng)估指標(biāo)類別描述數(shù)據(jù)的可信性精確性描述數(shù)據(jù)是否與其對(duì)應(yīng)的客觀實(shí)體的特征相一致完整性描述數(shù)據(jù)是否存在缺失記錄或缺失字段一致性描述同一實(shí)體的同一屬性的值在不同的系統(tǒng)是否一致有效性描述數(shù)據(jù)是否滿足用戶定義的條件或在一定的域值范圍內(nèi)唯一性描述數(shù)據(jù)是否存在重復(fù)記錄數(shù)據(jù)的可用性時(shí)間性描述數(shù)據(jù)是當(dāng)前數(shù)據(jù)還是歷史數(shù)據(jù)穩(wěn)定性描述數(shù)據(jù)是否是穩(wěn)定的，是否在其有效期內(nèi)成本效益成本效益是數(shù)據(jù)清洗的代價(jià)案例分析 Entity Resolution（實(shí)體解析）實(shí)

9、體解析從結(jié)構(gòu)化或非結(jié)構(gòu)化數(shù)據(jù)中識(shí)別、鏈接/分組同 一真實(shí)世界對(duì)象的不同表現(xiàn)形式。Matched EntityAmazon 數(shù)據(jù)集包 含1363條記錄Google數(shù)據(jù)集包含3226條記錄 ER的目標(biāo)是找到兩 個(gè)不同來源數(shù)據(jù)集 中匹配的實(shí)體。案例分析 Entity Resolution（實(shí)體解析）20實(shí)體解析問題在大數(shù)據(jù)時(shí)代的挑戰(zhàn)首先，異構(gòu)的、非結(jié)構(gòu)化數(shù)據(jù)集，具有不同的數(shù)據(jù)模式與表示方法，甚至存在數(shù)據(jù)質(zhì)量問題其次，ER算法是可擴(kuò)展的，并在集群中并行計(jì)算第三，從大規(guī)模數(shù)據(jù)集中找到匹配的實(shí)體，需要設(shè)計(jì)時(shí)空代價(jià)與 通信開銷高效的算法案例分析 Entity Resolution（實(shí)體解析）實(shí)體解析問題的算

10、法流程Record similarity measureEvaluation and AnalysisPrecisionRecallF-measuresInverted indexCosineSimilarityEntityResolutionAmazon “b000hkgj8k” TF-IDF：autocad: 0.883, autodesk: 0.383, courseware: 0. (b00005lzly,http:/ load and preprocessloadData parseDataRDDTupleTF-IDF computingtokenizationdataUnion T

11、F-IDFBroadcast variable目錄概述1數(shù)據(jù)質(zhì)量及評(píng)估2分布式數(shù)據(jù)處理模型及測試3大數(shù)據(jù)的基準(zhǔn)測試4大數(shù)據(jù)處理框架Hadoop在大數(shù)據(jù)領(lǐng)域中，Hadoop是最著名的大數(shù) 據(jù)處理框架之一，它以可靠、高效、可伸 縮的方式進(jìn)行大數(shù)據(jù)的儲(chǔ)存、處理和分析。Hadoop由Apache基金會(huì)開發(fā)，在其實(shí)現(xiàn)的 過程中，借鑒了Google的三大核心組件即 GFS、MapReduce 和BigTable。Hadoop的生態(tài)圈Hadoop已發(fā)展成包含HDFS、MapReduce、YARN、Hbase、ZooKeeper等子項(xiàng)目的集合，用于處理和分析大規(guī)模數(shù)據(jù)MapReduce運(yùn)行流程應(yīng)用Master

12、workerworkerworkerworkerworkeroutput file 0Split 0Split 1Split 2Split 3Split 4輸入文件Map階段中間結(jié)果Reduce階段輸出文件(3) read(5) remote read(4) local write(6) write(1) fork(1) fork(1) fork(2)assign reduce(2)assign mapoutput file 1MapReduce示例WordCountMapReduce示例WordCount代碼（Mapper）MapReduce示例WordCount代碼（Reducer）Map

13、Reduce示例WordCount代碼（Main）大數(shù)據(jù)單元測試MRUnit工具30MRUnit-Cloudera公司開發(fā)的針對(duì)MapReduce的單元測試框 架，其基本原理是利用JUnit4與EasyMock。MRUnit結(jié)構(gòu)簡 單，依賴于JUnit的單元測試功能，同時(shí)已經(jīng)通過實(shí)現(xiàn)Mock 對(duì)象控制OutputCollector操作并且攔截OutputCollector的輸 出，對(duì)比期望結(jié)果以達(dá)到自動(dòng)斷言的目的。MRUnit的driverMapDriver：測試單獨(dú)的MapReduceDriver：測試單獨(dú)的ReduceMapReduceDriver：將Map與Reduce連貫起來測試Pip

14、elineMapReduceDriver：將多個(gè)MapReduce貫串起來測試MRUnit使用：下載MRUnit的jar包，添加到Hadoop的開 發(fā)環(huán)境的Classpath路徑中MRUnit示例以下為Map和Reduce測試的例子。模擬兩條記錄 的輸入：CDRID595877;462198;737283;CDRTypePhone1Phone2SMS Status Code1;747382938472839;0;342839402839482;1;232329483034893;.;898783728372812;238473920384932;384938271928374;.;532“.;

15、查找所有CDRType為1的記錄，并根據(jù)SMS Status Code進(jìn)行統(tǒng)計(jì)Mapper期望的輸出應(yīng)該是：5,13,1Mapper的單元測試Testpublic void testMapper() mapDriver.withInput(new LongWritable(), new Text( 595877;1; 747382938472839;898783728372812;5);/指定輸入mapDriver.withOutput(new Text(5), new IntWritable(1);/預(yù)期輸出mapDriver.runTest();/運(yùn)行測試Reducer的單元測試Testp

16、ublic void testReducer() List values = new ArrayList(); values.add(new IntWritable(1);values.add(new IntWritable(1); reduceDriver.withInput(new Text(“5”), values); /指定輸入reduceDriver.withOutput(new Text(5), new IntWritable(2);/預(yù)期輸出 reduceDriver.runTest(); /運(yùn)行測試MapReduce調(diào)試與測試的建議盡早采用MRUnit編寫對(duì)MapReduce中

17、的Map函數(shù)與Reduce 函數(shù)進(jìn)行測試通過Assert（斷言）來使得程序滿足正確性條件，并通過print語句輸出可能的錯(cuò)誤首先在本地運(yùn)行小規(guī)模測試數(shù)據(jù)，再到集群上運(yùn)行MapReduce程序通過Hadoop日志來分析MapReduce程序運(yùn)行狀況目錄概述1面向數(shù)據(jù)質(zhì)量的測評(píng)2分布式數(shù)據(jù)模型及測試3大數(shù)據(jù)的基準(zhǔn)測試4大數(shù)據(jù)的基準(zhǔn)測試 基準(zhǔn)測試（Benchmark Testing）一種測量和評(píng)估軟件 性能指標(biāo)的典型活動(dòng)?？梢栽谀硞€(gè)時(shí)候通過基準(zhǔn)測試建立 一個(gè)已知的性能水平（稱為基準(zhǔn)線），當(dāng)系統(tǒng)的軟硬件環(huán) 境發(fā)生變化之后再進(jìn)行一次基準(zhǔn)測試以確定那些變化對(duì)性 能的影響?；鶞?zhǔn)測試領(lǐng)域，最著名的組織是TPC

18、（Transaction Processing Performance Council），TPC主要職責(zé)是制定數(shù) 據(jù)庫（數(shù)據(jù)倉庫）領(lǐng)域基準(zhǔn)程序的標(biāo)準(zhǔn)規(guī)范、性能、性價(jià) 比度量的指標(biāo)。 OLTP基準(zhǔn)-TPC-A面向銀行事務(wù)管理、TPC-C面向倉庫訂單管理、TPC-E面向市場交易應(yīng)用 OLAP基準(zhǔn)-TPC-DS、TPC-H等OLAP的基準(zhǔn)，評(píng)測考察復(fù)雜查詢處理能力；SQL-On-Hadoop基準(zhǔn)測試案例分析星環(huán)科技SQL-on-Hadoop產(chǎn)品 Transwarp Inceptor 架構(gòu)圖SQL-On-Hadoop基準(zhǔn)測試案例分析基準(zhǔn)測試內(nèi)容 功能測試數(shù)據(jù)加載、數(shù)據(jù)壓縮、數(shù)據(jù)建表、數(shù)據(jù)分區(qū)、數(shù)據(jù) 查

19、詢 性能測試測試500GB數(shù)據(jù)（TPC-DS基準(zhǔn)數(shù)據(jù)）規(guī)模下SQL查 詢的時(shí)間效率 兼容性測試測試數(shù)據(jù)查詢的SQL語句是否符合SQL 99和SQL2003標(biāo)準(zhǔn)中的核心SQL及OLAP測試方法SQL-On-Hadoop基準(zhǔn)測試案例分析測試數(shù)據(jù)與SQL的生成 通過TPC-DS 基準(zhǔn)提供的DSTools v1.3.0生成測試數(shù)據(jù)，考慮到測 試環(huán)境磁盤的容量及HDFS的復(fù)制存儲(chǔ)機(jī)制，選擇500GB的數(shù)據(jù)總 量，并選用TPC-DS為MySQL生成的99個(gè)查詢SQL，目的是保留各 種復(fù)雜SQL查詢，客觀反映Transwarp Inceptor在SQL支持與兼容性 的情況。 TPC-DS的基準(zhǔn)測試有以下特點(diǎn)

20、：一共99個(gè)測試案例，遵循SQL99和SQL 2003的語法標(biāo)準(zhǔn)，SQL案例比較復(fù)雜分析的數(shù)據(jù)量大，并且測試案例是在回答真實(shí)的商業(yè)問題測試案例中包含各種業(yè)務(wù)模型（如分析報(bào)告性，迭代式的在線 分析性，數(shù)據(jù)挖掘性等）幾乎所有的測試案例都有很高的IO負(fù)載和CPU計(jì)算需求SQL-On-Hadoop基準(zhǔn)測試案例分析40建表與數(shù)據(jù)分區(qū)利用DSTools v1.3.0工具建測試數(shù)據(jù)倉庫與數(shù)據(jù)表數(shù)據(jù)壓縮與加載考慮到查詢優(yōu)化，測試將采用ORC （Optimized Row Columnar）文件 格式存儲(chǔ)原始數(shù)據(jù)，原始生成的text格式的數(shù)據(jù)總量大約為500G，轉(zhuǎn)成 ORC格式后將壓縮為大約150G。查詢執(zhí)行利

21、用DSTools v1.3.0工具生成的99個(gè)查詢SQL，并參考TPC-DS 基準(zhǔn)規(guī) 范并行執(zhí)行SQL，測試Transwarp Inceptor SQL查詢的可靠性、時(shí)間性能 及兼容性。SQL-On-Hadoop基準(zhǔn)測試案例分析Transwarp Inceptor性能報(bào)告在Transwarp Inceptor中執(zhí)行由DSTools v1.3.0工具生成的99個(gè)符合 SQL99與SQL 2003標(biāo)準(zhǔn)的SQL，記錄每條SQL三次執(zhí)行的平均執(zhí)行時(shí)間。 Transwarp Inceptor 在500GB數(shù)據(jù)，數(shù)據(jù)庫事實(shí)表規(guī)模1800萬-14.4億條記 錄的情況下，執(zhí)行99個(gè)SQL查詢，SQL執(zhí)行時(shí)間如

22、下：SQL數(shù)目（個(gè)）SQL分類總執(zhí)行時(shí)間（秒）平均執(zhí)行時(shí)間（秒）9交互式查詢19721.969統(tǒng)計(jì)分析7705111.710迭代計(jì)算4232423.211數(shù)據(jù)挖掘3502318.4三、大數(shù)據(jù)智能算法及測評(píng)概述1聚類算法及測評(píng)2分類算法及測評(píng)3推薦系統(tǒng)及測評(píng)4概述 如何從大規(guī)模、動(dòng)態(tài)的、異構(gòu)的數(shù)據(jù)中， 利用智能算法處理與挖掘有價(jià)值的信息， 已成為大數(shù)據(jù)研究與應(yīng)用的重要方向這部分主要從大數(shù)據(jù)的算法層面介紹大數(shù)據(jù)測評(píng)方法數(shù)據(jù)的聚類和分類是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域 的經(jīng)典算法，大數(shù)據(jù)時(shí)代仍有廣泛應(yīng)用個(gè)性化推薦系統(tǒng)是面向終端用戶的典型應(yīng)用，在電子商務(wù)、音樂視頻網(wǎng)站等有著廣泛的應(yīng)用概述大數(shù)據(jù)基礎(chǔ)算法大規(guī)模數(shù)

23、據(jù)集 聚類算法與評(píng)估層次聚類 流聚類大數(shù)據(jù)應(yīng)用算法推薦系統(tǒng)算法與評(píng)估大規(guī)模數(shù)據(jù)集 分類算法與評(píng)估支持向量機(jī) k近鄰K-均值樸素貝葉斯物品聚類用戶行為分類用戶聚類支撐應(yīng)用推薦算法目錄概述1聚類算法及測評(píng)2分類算法及測評(píng)3推薦系統(tǒng)及測評(píng)4聚類及其在大數(shù)據(jù)中的應(yīng)用聚類算法：將大量的具有相似特征的對(duì)象聚集到不同的簇中聚類的目的：在海量或難以理解的數(shù)據(jù)集里 發(fā)現(xiàn)層次與規(guī)律，讓數(shù)據(jù)集更容易被理解聚類算法的特征：不需要預(yù)先標(biāo)注數(shù)據(jù)集， 屬于無監(jiān)督機(jī)器學(xué)習(xí)算法聚類的應(yīng)用： 識(shí)別某個(gè)主題相關(guān)的問題，比如新聞聚類 根據(jù)用戶的職業(yè)、收入、購買習(xí)慣等屬性進(jìn)行用戶聚類聚類及其在大數(shù)據(jù)中的應(yīng)用圖百度新聞聚類實(shí)例圖上海商圈

24、聚類實(shí)例聚類及其在大數(shù)據(jù)中的應(yīng)用特征選擇 或抽取數(shù)據(jù)集聚類算法設(shè) 計(jì)或選擇 聚類算法測試 與評(píng)估結(jié)果的展示 與解釋聚類有價(jià)值的知識(shí)圖聚類分析的流程聚類的典型算法及分析-層次聚類 層次聚類的基本思想：一開始將每個(gè)點(diǎn)都 看成一個(gè)簇，算法通過合并兩個(gè)小簇而形 成一個(gè)大簇，直到簇聚類滿足某些條件從 而結(jié)束聚類過程。.1 (2,2)2 (3,4).3 (5,3).5 (5,9)4 (4,8).6 (7,7).8 (9,3) .9 (10,2).7 (10,4)聚類的典型算法及分析-層次聚類首先將每個(gè)點(diǎn)視為一個(gè)簇Ci, i = 1 m；找出所有簇中距離最近的兩個(gè)簇 Ci、Cj ；合并Ci、Cj為一個(gè)新簇；

25、若目前的簇?cái)?shù)多于預(yù)期的簇?cái)?shù)，則重復(fù)步驟2-步驟4，直到簇?cái)?shù) 滿足預(yù)期的簇?cái)?shù)。While number of nodes 1 Repeat for i = 1 to mfor j = i + 1 to mi, j merge node(i) and node(j)delete node(i) and node(j) update nodes list注：基本的層次聚類算法效率不高，其算法復(fù)雜度為O(n3)，可以通過將所有點(diǎn)對(duì)的距離 保存在一個(gè)優(yōu)先隊(duì)列中，將算法優(yōu)化為O(n2 log n)。層次聚類的思想非常，但一般應(yīng)用于 規(guī)模較小的數(shù)據(jù)集。50聚類的典型算法及分析-K-均值聚類K-均值聚類的基本

26、思想：即按照某一順序依 次遍歷所有點(diǎn)，將點(diǎn)分配到最合適的簇中K-均值假定在歐式空間下，聚類數(shù)K已知，算法接受一個(gè)未標(biāo)記的數(shù)據(jù)集，然后將數(shù)據(jù)聚類成K個(gè)不同的簇聚類的典型算法及分析-K-均值聚類 首先選擇K個(gè)點(diǎn)，稱為聚類質(zhì)心（通常隨機(jī)選擇）； 遍歷數(shù)據(jù)集中的每一個(gè)點(diǎn)，按照距離K個(gè)質(zhì)心的距離，將其與距離最 近的質(zhì)心關(guān)聯(lián)起來，與同一個(gè)質(zhì)心相關(guān)聯(lián)的所有點(diǎn)聚成一類； 計(jì)算每一類中所有點(diǎn)位置的均值（新的質(zhì)心），將該類的質(zhì)心移動(dòng)到新質(zhì)心位置； 重復(fù)步驟(2)-步驟(4)，直到滿足收斂要求（如質(zhì)心不再變化）。Repeat for i = 1 to m i : = from 1 to K ifor k = 1 t

27、o K 注：K-均值聚類的算法復(fù)雜度為O(mkt)，其中m為需要處理的點(diǎn)數(shù)、k為聚類質(zhì) 心數(shù)、t為迭代的次數(shù)。聚類的典型算法及分析-K-均值聚類圖 K-均值算法的動(dòng)態(tài)迭代聚類的并行化為什么需要并行化？ 大數(shù)據(jù)時(shí)代，聚類算法所面臨的數(shù)據(jù)規(guī)模越來越大 聚類算法的算法復(fù)雜度比較高，而且數(shù)據(jù)處理受限于內(nèi)存Ki數(shù)據(jù)集 0Mapper 1Ki 代表第i次迭代的 質(zhì)心的描述Mapper 2Mapper n數(shù)據(jù)集 1數(shù)據(jù)集 nReducer 1Reducer kKi - Ki-1 閾值i=i+1Ki-1聚類結(jié)束圖 基于MapReduce的K-均值算法聚類的并行化Mapper任務(wù)的偽代碼如下：Input：dat

28、aset and cluster centroids description fileOutput： for each point do beginkey:=cluster centroid listvalue:=index of point belongs to some cluster centroidoutput:Reducer任務(wù)的偽代碼如下：Input: the key and the value output by map function Output: for each centroid do beginkey:=cluster centroid listvalue:= new

29、 centroid position output:注：MapReduce編程模型并不直接支持迭代模型，因此需要額外編寫驅(qū)動(dòng)程序來判斷迭代是否終止， 若迭代沒有終止，則需要驅(qū)動(dòng)MapReduce程序重新執(zhí)行任務(wù)，直到滿足終止條件。Mapper任務(wù)：將數(shù)據(jù)集分成子集并與質(zhì)心描 述文件一起發(fā)送到各個(gè)Map節(jié)點(diǎn)，每個(gè)Map 節(jié)點(diǎn)分別執(zhí)行任務(wù)，即將子集中的數(shù)據(jù)分配 給最近點(diǎn)的質(zhì)心，并以所屬簇質(zhì)心為key，點(diǎn) 的索引為value，組成中間結(jié)果傳遞到Reducer 節(jié)點(diǎn)。Reducer任務(wù)：得到中間結(jié)果后將屬于同一簇的點(diǎn)計(jì)算新的質(zhì)心。 比較新的質(zhì)心與原有的質(zhì)心是否一致，如果 一致，代表算法已收斂，否則仍需

30、進(jìn)一步迭 代，即更新質(zhì)心描述文件，重新運(yùn)行整個(gè)作 業(yè)。大數(shù)據(jù)智能算法測試的方法論分析智能算法解決問題的領(lǐng)域 需要分析問題的領(lǐng)域與算法的類別 需要分析算法設(shè)計(jì)者可能沒考慮到的數(shù)據(jù)特征分析智能算法的定義及代碼 檢查算法的定義是否精確 分析算法的定義及代碼，可以推測缺陷可能出現(xiàn)的區(qū)域，從而創(chuàng)建測試集來發(fā)現(xiàn)潛在的算法缺陷分析智能算法運(yùn)行時(shí)的選項(xiàng) 檢查這些算法運(yùn)行時(shí)選項(xiàng)是如何處理或操作輸入數(shù)據(jù)，從而 設(shè)計(jì)數(shù)據(jù)集和測試方法，并在輸入數(shù)據(jù)的操作中可能發(fā)現(xiàn)缺 陷或不一致智能算法測試的測試方法-蛻變測試蛻變測試的基本觀察 測試成功的測試用例沒有被進(jìn)一步有效利用與挖掘，而這些測試用例很可能蘊(yùn)含著有價(jià)值的信息。 軟

31、件測試存在“測試準(zhǔn)則（Oracle）問題”。注：測試準(zhǔn)則，即是確認(rèn)程序輸出正確性的機(jī)制。所謂測試準(zhǔn)則問題就是不存在測試準(zhǔn)則， 或者沒有可靠的測試準(zhǔn)則，或者即使有測試準(zhǔn)則但應(yīng)用代價(jià)非常高。蛻變測試的基本思想 利用這些成功的測試用例，并根據(jù)蛻變關(guān)系創(chuàng)建衍生（follow-up） 測試用例，然后分析這兩類測試用例測試后的結(jié)果是否滿足蛻變 關(guān)系，從而判斷程序是否存在缺陷。蛻變測試是一種可有效解決智能算法測試的軟件測試方法，它能在一定程度上 解決由于這類軟件沒有可靠“測試準(zhǔn)則”問題帶來的挑戰(zhàn)。智能算法測試的測試方法-蛻變測試蛻變測試的形式化定義 定義1：假設(shè)程序P 用來計(jì)算函數(shù)f, x1, x2, ,

32、xn, n 1是f的n個(gè)變量, 且f(x1), f(x2) , f(xn)是它們所對(duì)應(yīng)的函數(shù)值。若x1, x2, , xn, 之間 滿足關(guān)系r 時(shí), f(x1), f(x2) , f(xn) 滿足關(guān)系rf 即r(x1, x2, , xn ) rf(f(x1), f(x2) , f(xn)，則稱 (r, rf) 是P 的蛻變關(guān)系(MetamorphicRelation, MR)。測試人員可以通過檢查分析上述推導(dǎo)式是否成立來判斷程序P的正確性。 定義2：使用蛻變關(guān)系(r, rf)測試程序P時(shí), 起初選擇的測試用例稱為原 始測試用例； 由原始測試用例根據(jù)關(guān)系r計(jì)算得出的測試用例是該原 始測試用例基于

33、蛻變關(guān)系(r, rf)的衍生測試用例。智能算法測試的測試方法-蛻變測試蛻變測試的原理 第一，結(jié)合其它測試用例選擇的策略（比如路徑覆蓋測試或等價(jià)類劃分等）為待 測程序P生成原始測試用例x0； 第二、利用這些原始測試用例來測試程序，若都通過測試，且計(jì)算結(jié)果P(x0)，然 后進(jìn)一步分析待測程序的特點(diǎn)，設(shè)計(jì)構(gòu)造一系列蛻變關(guān)系； 第三，根據(jù)這些蛻變關(guān)系生成衍生測試用例r1(x0)，r2(x0)，并計(jì)算衍生測試用例得到測試結(jié)果為P(r1(x0)和P(r2(x0)； 第四，分析原始測試用例的計(jì)算結(jié)果P(x0)與衍生用例的輸出P(r1(x0)、P(r2(x0) 是否滿足蛻變關(guān)系rf1與rf2，如果滿足蛻變關(guān)系

34、則測試通過，否則說明待測程序P 可能存在缺陷。1.sin 37.5 ，p(x) = 0.6078（正確嗎？）2.MR1: sin x= sin(180 x)3.x = 180 x = 142.54.P x= 0.60825.通過比較P(x)和P x 的值，可以發(fā)現(xiàn)它 們之間不滿足蛻變關(guān)系MR1，因此程序P 中存在缺陷基于蛻變測試的聚類算法測試構(gòu)造蛻變關(guān)系（以K-均值為例）MR 1.1： 屬性全局仿射變換的一致性。如果對(duì)原始測試用例中的每個(gè)屬性值(i)做仿射變換( i ) = (i) + ( 0)得到衍生測試用例，則聚類結(jié)果不變。60MR 1.2： 屬性局部仿射變換的一致性。 如果對(duì)原始測試用例

35、中的每個(gè)屬性列做仿射變換() = + ( 0)得到衍生測試用例，則聚類結(jié)果不變。()()()MR 2.1： 數(shù)據(jù)樣本行置換。如果對(duì)原始測試用例中的任意兩行數(shù)據(jù)樣本做行置換得到衍生測試用例, 則聚類結(jié)果不變。MR 2.2： 數(shù)據(jù)樣本列置換。 如果對(duì)原始測試用例中的任意兩列屬性做列置換得到衍生測試用例, 則 聚類結(jié)果不變。MR 3：增加不提供信息屬性。在原始測試用例的基礎(chǔ)上，增加一列屬性，增加的屬性值全部相同， 即這列屬性值與原始測試用例中屬性信息無關(guān)，得到衍生測試用例，則聚類結(jié)果不變。MR 4 ：復(fù)制單個(gè)數(shù)據(jù)樣本。在原始測試用例基礎(chǔ)上, 增加一個(gè)數(shù)據(jù)樣本，增加的樣本與原始測試用例中某一個(gè)樣本相同

36、，得到衍生測試用例，則聚類結(jié)果不變?；谕懽儨y試的聚類算法測試表基于蛻變測試的測試結(jié)果及K-均值算法的適用性分析MR預(yù)期結(jié)果K-均值算法的適用性分析MR 1.1Y屬性全局仿射變換的一致性MR 1.2Y屬性局部仿射變換的一致性MR 2.1N初始聚類質(zhì)心的改變將影響聚類結(jié)果MR 2.2Y對(duì)數(shù)據(jù)維的順序不影響聚類結(jié)果MR 3Y增加一列無關(guān)屬性（屬性值相同），不改變聚類結(jié)果MR 4N增加重復(fù)數(shù)據(jù)樣本將改變聚類結(jié)果關(guān)于蛻變測試應(yīng)用于大數(shù)據(jù)智能算法的思考 蛻變測試是一種非常有效、而且容易實(shí)現(xiàn)的自動(dòng)化測試方 法，除了以上的K-均值聚類算法、樸素貝葉斯分類算法測 試以外，還可以應(yīng)用于其它大數(shù)據(jù)智能算法，如支持

37、向量 機(jī)、K-近鄰等算法等。 應(yīng)用蛻變測試的關(guān)鍵是設(shè)計(jì)合理、高效的蛻變關(guān)系，這些 蛻變關(guān)系可以從不同路徑、不同方面來檢查程序的缺陷。 將蛻變測試應(yīng)用于大數(shù)據(jù)智能算法的測試時(shí)，還需要考慮 結(jié)合其它測試方法，比如隨機(jī)測試、變異測試等來生成大 規(guī)模、高效的測試用例聚類質(zhì)量的評(píng)估外部指標(biāo)-即計(jì)算聚類結(jié)果與已有的標(biāo)準(zhǔn)分類結(jié)果的吻合程度（1）F-Measure -利用信息檢索中的準(zhǔn)確率（Precision）與召回率（Recall）思想來進(jìn)行聚類質(zhì)量的評(píng)價(jià)。 , = , =其中，Nij代表類簇j中類別為i的樣本數(shù)，Nj代表類簇j樣本數(shù)，Ni代表類別i中的樣本數(shù)。F-Measure是對(duì)查準(zhǔn)率與查全率的加權(quán)調(diào)和

38、平均，其計(jì)算公式為： , =2 , (, ) , + (, )整個(gè)聚類結(jié)果的F-Measure由每個(gè)分類i的加權(quán)平均得到，其計(jì)算公式為： = , 其中，N代表聚類的總樣本數(shù)。 , = 3 4F-Measure的值越高，則聚類的效果越好。 , = 3 3類簇j的樣本類別i的樣本Precison與Recall計(jì)算實(shí)例聚類質(zhì)量的評(píng)估（2）信息熵指標(biāo)假設(shè)數(shù)據(jù)集C可以分K個(gè)簇，其樣本數(shù)為N，其中類簇Ci的樣本數(shù)為Ni,則該類簇的信息熵定 義為：Entropy = 1 =1其中q為數(shù)據(jù)集中類簇的數(shù)目，Ni表示類簇Ci與類簇Cj的交集，整個(gè)聚類結(jié)果的信息熵定 義為：jEntropy = Entropy =1

39、信息熵反映了同一類樣本在結(jié)果簇中的分散度，同一類樣本在結(jié)果簇中越分散，則信 息熵值越大，聚類效果越差。當(dāng)同一類樣本屬于一個(gè)類簇時(shí)，信息熵值為0。聚類質(zhì)量的評(píng)估（3）Rand指數(shù)和Jaccard指數(shù)設(shè)數(shù)據(jù)集X的聚類結(jié)果類簇為C = C1, C2, , Cm ，數(shù)據(jù)集的真實(shí)分類為P = P1, P2, , Ps ，C中的類數(shù) m和P中的類數(shù)s不一定相同，可以通過對(duì)C和P進(jìn)行比較來評(píng)估聚類結(jié)果的質(zhì)量。對(duì)數(shù)據(jù)集中任一對(duì)點(diǎn) xi, xj 計(jì)算下列項(xiàng)：a兩點(diǎn)屬于中同一簇，并且屬于中同一類； b兩點(diǎn)屬于中同一簇，并且屬于中不同類； c兩點(diǎn)屬于中不同簇，并且屬于中同一類； d兩點(diǎn)屬于中不同簇，并且屬于中同一類

40、；a和d用來描述兩個(gè)分類的一致性，b和c用來描述聚類對(duì)于真實(shí)分類的偏差。C和P的相似程度可以用Rand指數(shù)和Jaccard指數(shù)來定義：Rand指數(shù)： R = a +b a+b+c+dJaccard指數(shù)： J = a a+b+cRand指數(shù)和Jaccard指數(shù)用于度量聚類算法的聚類結(jié)果與真實(shí)分類的相似度，顯然Rand指數(shù) R值越大， 相似程度越好，聚類效果就越好；同理，Jaccard指數(shù)J越小，聚類效果越差。聚類質(zhì)量的評(píng)估內(nèi)部指標(biāo)-不依賴于外部信息，如分類的先驗(yàn)知識(shí)。內(nèi)部指標(biāo)的評(píng)估是直接從原始數(shù)據(jù)集中檢查聚類的效果。（1）簇內(nèi)誤差 -即任意點(diǎn)與其質(zhì)心的距離的平方和。V = (, )2 其中，C為

41、所有的簇，k 是Ck 的質(zhì)心，(,)是距離度量函數(shù)，即數(shù)據(jù)點(diǎn)xi 與其對(duì)應(yīng)的簇的質(zhì)心的距離。 因此簇內(nèi)誤差越小，聚類效果越好。（2）Cophenetic相關(guān)系數(shù)層次聚類得到的樹形圖可用Cophenetic矩陣表示，的元素 是數(shù)據(jù) 和首次在同一個(gè)簇中的距離 值，是數(shù)據(jù)點(diǎn)的相似性矩陣，的元素為。Cophenetic相關(guān)系數(shù)可度量層次聚類的質(zhì)量，公式定義如 下： =( 1 1) =1=+1 ( 1 ) 1 2 2 1 =1=+1=1=+1 2 2其中， = ( 1)/2，是數(shù)據(jù)的個(gè)數(shù)；和分別是矩陣和的均值； 的取值范圍是 1,1， 的值越接近1，說明兩個(gè)矩陣相關(guān)性越好，層次聚類的效果越好。目錄概述1

42、聚類算法及測評(píng)2分類算法及測評(píng)3推薦系統(tǒng)及測評(píng)4分類及其在大數(shù)據(jù)中的應(yīng)用 分類算法：根據(jù)數(shù)據(jù)集的特點(diǎn)構(gòu)造一個(gè)分類模型（也 稱為分類器），該模型能把未知類別的樣本，自動(dòng)映 射到某一指定類別。分類的目的：計(jì)算機(jī)判斷一個(gè)對(duì)象是不是屬于某種類型，或者該對(duì)象是不是含有某些屬性 分類算法的特征：需要事先定義好類別，并對(duì)訓(xùn)練樣 本進(jìn)行人工標(biāo)記，屬于有監(jiān)督機(jī)器學(xué)習(xí)算法分類的應(yīng)用： 判斷預(yù)測某一次交易是否為行用卡詐騙 判斷某一張圖片的內(nèi)容是否屬于某一種類型分類及其在大數(shù)據(jù)中的應(yīng)用分類算法已標(biāo)記類別的 訓(xùn)練樣本分類算法測試與驗(yàn)證分類器預(yù)測類別新的樣本圖分類的流程分類的典型算法及分析-樸素貝葉斯分類算法樸素貝葉斯算

43、法的基本思想： 假設(shè)x = (x1, x2, , xm)為數(shù)據(jù)集中的某一樣本，其中xi是該樣本的第i個(gè)特征， 并有類別集合 C = y1, y2, , yk ；可以計(jì)算概率 p y1 x , p y2 x , , p yk x ； 若p yi x = maxp y1 x , p y2 x , , p yk x ，則x yi，即x屬于yi類。 樸素貝葉斯分類算法基于樸素貝葉斯假設(shè)，即在給定類別信息yi的條件下， x的特征xi之間互相獨(dú)立，這也是為什么這個(gè)分類算法稱為樸素貝葉斯分類 算法。 根據(jù)概率論中的貝葉斯定理：p yi x=p x yi p(yi)p(x)考慮到分母對(duì)于所有類別為常數(shù)，因此只

44、需要考慮分子部分，根據(jù)樸素貝葉斯的假設(shè)，x的特征xi之間互相條件獨(dú)立，因此有：m70p x yi p yi= p x1 yip x2 yi p xm yip yi= p yi p xj yij=1分類的典型算法及分析-樸素貝葉斯分類算法樸素貝葉斯算法： 遍歷整個(gè)數(shù)據(jù)集，可以統(tǒng)計(jì)得到在k個(gè)類別下各個(gè)特征的條件概率估計(jì)，即x1 y1 , p x2 y1 , , p xm y1 p x1 y2 , p x2 y2 , , p xm y2p x1 yk , p x2 yk , , p xm yk .根據(jù)以上的貝葉斯公式，可以計(jì)算得出p yi x ，i = 1, , k，從而預(yù)測樣本x屬于哪一類。 樸素

45、貝葉斯分類算法的偽代碼如下：Computep x yi= mp xj yi, j = 1, , m, i = 1, , kj=1p yi ,i = 1, , karg max p(yi|x) = argyi p x yi p(yi)yi注：盡管樸素貝葉斯分類算法對(duì)于樣本數(shù)據(jù)稀疏時(shí)非常敏感（需要“拉普拉斯平滑”），但仍然是應(yīng) 用最廣的分類算法之一，被廣泛應(yīng)用于文本分類領(lǐng)域、用戶行為分析等大數(shù)據(jù)分析挖掘領(lǐng)域。分類的典型算法及分析-支持向量機(jī)算法支持向量機(jī)算法的基本思想： 尋找一個(gè)滿足分類要求的最優(yōu)分類超平面，使得該超平面在保證分類精度的 同時(shí)，能夠使超平面兩側(cè)的間隔最大化。圖 線性的支持向量機(jī)原理

46、圖分類的典型算法及分析-支持向量機(jī)算法支持向量機(jī)算法的數(shù)學(xué)原理： 支持向量機(jī)本質(zhì)上是約束最小化問題 1 min 22+ C =1+ 1 ，is. t. w = 1,2, , m 0，i = 1,2, , m其中，C是正則化因子，可以通過C來控制樣本的過擬合問題；i是松弛變量分類的典型算法及分析-支持向量機(jī)算法支持向量機(jī)算法的分類實(shí)例：圖 總體線性可分的例子正則化因子C=1時(shí)計(jì)算得到的分類決策邊界圖 線性不可分的例子采用了高斯核計(jì)算得到的分類決策邊界分類算法（分類器）性能的評(píng)估分類器性能評(píng)估的方法留置法（Hold-Out）留置法的思想是把數(shù)據(jù)分為互不相交的兩部分，分別稱為訓(xùn)練集與測試集。 其中訓(xùn)

47、練集用于構(gòu)造分類器，而測試集用于評(píng)估分類器的性能。訓(xùn)練集與測試 集的比例通常是2:1，即2/3的樣本用于訓(xùn)練集，1/3樣本用于測試集。分類器的性能根據(jù)模型在測試集上的準(zhǔn)確率估計(jì)，可以定義分類性能為：/380 =1/3 ( , )=1其中，N是樣本數(shù)，F(xiàn)(,)是分類性能的評(píng)估指標(biāo)。分類算法（分類器）性能的評(píng)估分類器性能評(píng)估的方法隨機(jī)子抽樣（Random Subsampling）隨機(jī)子抽樣是留置法的改進(jìn)，其通過留置法的多次迭代，每次隨機(jī)形成訓(xùn)練集與測試集。隨機(jī)子抽樣的分類器性能為： = =1其中，K代表迭代的次數(shù)，Pj是第j迭代時(shí)分類器的性能。分類算法（分類器）性能的評(píng)估分類器性能評(píng)估的方法交叉驗(yàn)

48、證（Cross-validation） 二折交叉驗(yàn)證假設(shè)把數(shù)據(jù)分為相同大小的兩個(gè)子集，首先選擇其中一個(gè)子集作為訓(xùn)練集，另一個(gè) 作為測試集，然后交換兩個(gè)子集的角色，這種方法稱為二折交叉驗(yàn)證。分類總誤差通過 對(duì)兩次運(yùn)行的誤差求和得到。 K折交叉驗(yàn)證K折交叉驗(yàn)證方法是二折交叉驗(yàn)證的推廣，即把數(shù)據(jù)集分成獨(dú)立并數(shù)量相同的K份。 每次驗(yàn)證時(shí)選擇其中的一份作為測試集，其余的 K 1 份都作為訓(xùn)練集，該過程重復(fù) K 次， 使得每份數(shù)據(jù)都用于測試恰好一次。同樣，分類的總誤差是說有K次誤差之和。分類算法（分類器）性能的評(píng)估準(zhǔn)確性和F-Measure準(zhǔn)確性（Accuracy）TP + TNAccuracy = TP

49、 + TN + FP + FNF-MeasurePrecision = + Recall = + F Measure =2 Precision RecallPrecision + Recall準(zhǔn)確性值與F-Measure值越大，分類器的性能越好預(yù)測類別+-實(shí)際 類別+正確的正例（TP）錯(cuò)誤的負(fù)例（FN）-錯(cuò)誤的正例（FP）正確的負(fù)例（TN）分類算法（分類器）性能的評(píng)估ROC曲線與AUC的一些說明ROC曲線與AUC(FPR=0,TPR=0)意味著分類器將每個(gè)樣本都預(yù)測為負(fù)例(FPR=1,TPR=1)意味著分類器將每個(gè) 樣本都預(yù)測為正例(FPR=0,TPR=1)意味著最優(yōu)的分類器在ROC曲線中，如

50、果曲線A始終位于 曲線B的左上方，則曲線A優(yōu)于曲線BAUC，即ROC曲線下方面積（the Area Under the ROC curve，AUC）。如果 ROC曲線B的AUC值大于曲線A的值， 則B對(duì)應(yīng)的分類器性能優(yōu)于A。求AUC 值的最通用方法是通過積分法求ROC 曲線下方的面積。X軸是錯(cuò)誤的正例率（False Positive Rate，F(xiàn)PR），F(xiàn)PFPR =FP + TNY軸是正確的正例率（True Positive Rate，TPR），TPTPR =TP + FNROC曲線與AUC目錄概述1聚類算法及測評(píng)2分類算法及測評(píng)3推薦系統(tǒng)及測評(píng)4推薦系統(tǒng)概述 個(gè)性化推薦系統(tǒng)：是一種利用用戶

51、歷史行為數(shù)據(jù)，建 立用戶行為模型，幫助用戶過濾無關(guān)信息、提供最能 滿足用戶個(gè)性化需求信息的智能系統(tǒng)。推薦系統(tǒng)的核心流程用戶特征收集模塊：該模塊負(fù)責(zé)收集用戶的歷史行為，比如評(píng)分、購買、瀏覽、評(píng)論等行為，這些行 為可以用來描述用戶的偏好。用戶行為建模與分析模塊：該模塊根據(jù)收集得到的用戶歷史行為，構(gòu)建合適的數(shù)學(xué)模型來分析用戶的 偏好或找出相似偏好的用戶。物品的排序與推薦模塊：該模塊將用戶的行為信息作為特征，通過推薦算法快速獲得用戶感興趣的物 品，并將物品排序后推薦給用戶。推薦系統(tǒng)的評(píng)估模塊：該模塊負(fù)責(zé)評(píng)估推薦系統(tǒng)是否滿足應(yīng)用的需求，常見的評(píng)估指標(biāo)包括準(zhǔn)確度、 多樣性、新穎性、覆蓋率等。推薦系統(tǒng)的應(yīng)用

52、亞馬遜的商品推薦Netflix的電影推薦推薦系統(tǒng)算法-基于內(nèi)容的推薦基于內(nèi)容的推薦基本思想：根據(jù)用戶已經(jīng)選擇的物品的內(nèi)容信息，為用戶推薦內(nèi)容上相似的其它物品。令UserProfile u 為用戶u的物品偏好向量，該向量可以定義如下：UserProfile =1(u) ()(u)其中，N(u)是用戶u之前偏好的物品集合，Content(s)是物品的內(nèi)容向量，其可以從物品的 特征信息中獲得。那么，對(duì)于任意一個(gè)用戶u和一個(gè)他不知道的物品c，用戶物品偏好向量 UserProfile u 與Content(c)的相似度可定義如下：s u, c= sim(UserProfile , )接下來，就可以通過比

53、如向量余弦定理度量上述兩個(gè)向量的相似度，兩個(gè)向量的夾角越小， 則這兩個(gè)向量的距離越近，也就是這兩個(gè)向量相似度越高；反之，兩個(gè)向量的夾角越大，則這 兩個(gè)向量的距離越遠(yuǎn)，兩個(gè)向量相似度越低。優(yōu)點(diǎn)：無需使用其它用戶數(shù)據(jù)；能為愛好比較獨(dú)特的用戶進(jìn)行推薦；能推薦新的或比較冷門的 物品；通過列出推薦物品的內(nèi)容特征來解釋推薦的原因缺點(diǎn)：僅適用于物品特征容易抽取的領(lǐng)域，難以挖掘出用戶潛在的興趣推薦系統(tǒng)算法-基于用戶的協(xié)同過濾推薦基于用戶的協(xié)同過濾算法基本思想：一個(gè)用戶會(huì)喜歡和他有相似偏好的用戶喜歡的物品用戶A用戶B用戶C電影AA電影BB電影CC電影DD 喜歡 推薦90相似用戶/電影電影A電影B電影C電影D用戶

54、A推薦用戶B用戶C推薦系統(tǒng)算法-基于物品的協(xié)同過濾推薦基于物品的協(xié)同過濾算法基本思想：一個(gè)用戶會(huì)喜歡和他之前喜歡的物品類似的物品92用戶/物品物品A物品B物品C用戶甲用戶乙用戶丙推薦推薦系統(tǒng)的測評(píng)實(shí)驗(yàn)推薦系統(tǒng)的測評(píng)仍然是推薦系統(tǒng)設(shè)計(jì)與應(yīng)用中的一大挑戰(zhàn) 不同的推薦算法在不同的數(shù)據(jù)集上的表現(xiàn)不同；某些算法可能對(duì)于小數(shù)據(jù)集 表現(xiàn)不錯(cuò)，但當(dāng)數(shù)據(jù)集不斷增大，算法的性能和運(yùn)行速度都可能明顯下降。 推薦系統(tǒng)的評(píng)估指標(biāo)繁多，而且指標(biāo)之間并不一致。評(píng)估指標(biāo)包括基本的準(zhǔn) 確度、多樣性、覆蓋率、驚喜度、可擴(kuò)展性等。而且，準(zhǔn)確度指標(biāo)和多樣性 指標(biāo)本身是一對(duì)矛盾。 推薦系統(tǒng)的不同指標(biāo)需要通過不同的測試方法來計(jì)算度量。比

55、如，準(zhǔn)確度可 以通過離線計(jì)算，但驚喜度就需要通過用戶調(diào)查才能得出，而有些指標(biāo)的評(píng) 估需要在線實(shí)驗(yàn)獲得。推薦系統(tǒng)的測評(píng)實(shí)驗(yàn)離線實(shí)驗(yàn) 離線實(shí)驗(yàn)使用現(xiàn)有的數(shù)據(jù)集，利用數(shù)據(jù)集對(duì)用戶的行為進(jìn)行建模，進(jìn)而來評(píng)估 推薦系統(tǒng)的性能，如預(yù)測的準(zhǔn)確度。離線實(shí)驗(yàn)的實(shí)施在三類實(shí)驗(yàn)中的代價(jià)是最 低的，也是最容易實(shí)施的。 在進(jìn)行離線實(shí)驗(yàn)時(shí)，首先需要預(yù)先收集用戶的行為數(shù)據(jù)，比如用戶的選擇或商 品評(píng)分的數(shù)據(jù)集，這些數(shù)據(jù)集可以模擬用戶與推薦系統(tǒng)交互的行為。 假定收集的用戶行為數(shù)據(jù)，與用戶在實(shí)際的推薦系統(tǒng)上的行為足夠的相似，基于這種假設(shè)，可以通過離線實(shí)驗(yàn)作出可靠的評(píng)估。 用于離線實(shí)驗(yàn)的數(shù)據(jù)集應(yīng)該盡可能與未來部署后的系統(tǒng)產(chǎn)生的數(shù)據(jù)

56、一致。換句 話說，用于離線評(píng)估的用戶行為數(shù)據(jù)（用戶的評(píng)分、用戶的選擇等）盡可能是 無偏的。優(yōu)點(diǎn)：不需要真實(shí)用戶的交互，因此可以以較低的代價(jià)快速的測試評(píng)估各種不同的算法。 缺點(diǎn)：這類實(shí)驗(yàn)通常只能計(jì)算某一個(gè)算法的預(yù)測能力，無法評(píng)估驚喜度、滿意度等其它指標(biāo)。推薦系統(tǒng)的測評(píng)實(shí)驗(yàn)用戶調(diào)查 要求一小部分測試用戶使用推薦系統(tǒng)，并執(zhí)行一組任務(wù)，然后回答一些關(guān)于他 們使用體驗(yàn)的問題。 當(dāng)測試人員執(zhí)行任務(wù)時(shí)，觀察并記錄他們的行為，收集任務(wù)完成的情況，比如 哪些任務(wù)已經(jīng)完成、執(zhí)行任務(wù)花費(fèi)的時(shí)間、任務(wù)結(jié)果的準(zhǔn)確性等。 可以通過用戶調(diào)查讓測試人員回答一些定性的問題，比如是否喜歡用戶界面、或者用戶對(duì)完成任務(wù)難易程度的感受

57、，這些結(jié)果一般無法直接觀察得到。 需要考慮測試人員的分布問題，比如興趣愛好、男女比例、年齡、活躍程度的 分布都應(yīng)和真實(shí)系統(tǒng)中的用戶分布盡量相同。優(yōu)點(diǎn)：可以測試用戶與推薦系統(tǒng)交互的行為，以及推薦系統(tǒng)對(duì)用戶行為的影響。用戶調(diào)查還 可以收集定性的數(shù)據(jù)，這些數(shù)據(jù)往往對(duì)解釋定量的結(jié)果至關(guān)重要。缺點(diǎn)：用戶調(diào)查的成本很高，一方面需要招募大量的測試人員，另一方面需要測試人員完成 大量的與推薦系統(tǒng)交互的任務(wù)。推薦系統(tǒng)的測評(píng)實(shí)驗(yàn)在線評(píng)估 在一個(gè)部署好的推薦系統(tǒng)上運(yùn)行大規(guī)模測試，在線評(píng)估中通過真實(shí)的用戶執(zhí)行 真實(shí)的任務(wù)來測評(píng)或比較不同的推薦系統(tǒng)。 需要對(duì)用戶進(jìn)行隨機(jī)采樣，保證不同推薦系統(tǒng)的測試用戶分布盡量相同，這樣

58、 不同推薦系統(tǒng)的比較才相對(duì)公平。 如果關(guān)注推薦系統(tǒng)的某一項(xiàng)指標(biāo)，那么盡量保持其它影響因素的一致性。優(yōu)點(diǎn)：可以獲得推薦系統(tǒng)整體性能評(píng)估，比如長期的商業(yè)利潤和用戶保持度，而不僅僅是某 些單一的指標(biāo)。缺點(diǎn)：在線評(píng)估測試是有一定風(fēng)險(xiǎn)的。推薦系統(tǒng)的評(píng)估基于機(jī)器學(xué)習(xí)視角推薦算法的預(yù)測準(zhǔn)確度度量Mean absolute error（平均絕對(duì)誤差）： =1 (,) Mean Square Error（均方誤差）： =1 ( )2(,)Root Mean Square Error（均方根誤差）： =1 ( )2(,)推薦系統(tǒng)的評(píng)估基于信息檢索視角基本的決策支持度量與基于排名的度量準(zhǔn)確率、召回率、F-Measu

59、re準(zhǔn)確率 = 或 = 用戶喜歡的物品的比例召回率 = 2 不遺漏用戶喜歡物品的比率 = + 其中，Nrs是推薦物品中用戶喜歡的個(gè)數(shù)、Ns是推薦的物品數(shù)，n代表前n個(gè)推薦項(xiàng)Nr是用戶喜歡的物品數(shù)。推薦系統(tǒng)的評(píng)估基于信息檢索視角基本的決策支持度量與基于排名的度量平均準(zhǔn)確率（Mean Average Precision，MAP）：多個(gè)推薦準(zhǔn)確率的平均值，推薦的相關(guān)物品 越靠前，平均準(zhǔn)確率越高 = ()=1，其中 =1# relevant itemQ為物品推薦的次數(shù)，k是排名，rel k 代表給定排名的相關(guān)性函數(shù)，p k 代表給定排名的 精度。ROC曲線ROC曲線也適用于推薦系統(tǒng)的評(píng)估，可以通過RO

60、C曲線來調(diào)整推薦系統(tǒng)的參數(shù)，比如可以 找到推薦系統(tǒng)錯(cuò)誤的正例率與正確的正例率之間的折中。此外，通過AUC還可以比較不同推薦 系統(tǒng)的性能。100推薦系統(tǒng)的評(píng)估101基于信息檢索視角基本的決策支持度量與基于排名的度量平均倒數(shù)排名（Mean Reciprocal Rank，MRR）：其概念來自信息檢索系統(tǒng)，希望越相關(guān)的 檢索結(jié)果應(yīng)該排在越前面。平均倒數(shù)排名應(yīng)用于推薦系統(tǒng)時(shí)，可以度量推薦系統(tǒng)是否將用戶 最喜歡的物品排在最前面，其定義如下： = 1/ = 1 其中，Q為物品推薦的次數(shù)，ranki為用戶最喜歡的物品的在推薦列表中的排名。 顯然MRR的值越大，推薦系統(tǒng)的性能越好。推薦系統(tǒng)的評(píng)估基于信息檢索視