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

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

2、處理的要求，大數(shù)據(jù)治理、大數(shù)據(jù)處理技術(shù)應(yīng)運而 生。 數(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)工具對分布廣泛的非結(jié)構(gòu)化的數(shù)據(jù)源進 行抽取/采集，并進行數(shù)據(jù)傳輸采用合適的模式/標(biāo)準(zhǔn)對數(shù)據(jù)進行統(tǒng)一存儲利用智能算法，對數(shù)據(jù)進行分析處理數(shù)據(jù)分析處理的結(jié)果，通過可視化的方法，提供 給大數(shù)據(jù)應(yīng)用（預(yù)測、分析報表、）數(shù)據(jù)源數(shù)據(jù)集成關(guān)系數(shù)據(jù)庫數(shù)據(jù)集成實體 數(shù)據(jù)質(zhì)量

3、聚類和關(guān)聯(lián)模式數(shù)據(jù)質(zhì)量應(yīng)用可視化目錄概述1數(shù)據(jù)質(zhì)量及評估2分布式數(shù)據(jù)處理模型及測試3大數(shù)據(jù)的基準(zhǔn)測試4數(shù)據(jù)質(zhì)量定義目前數(shù)據(jù)質(zhì)量還沒有統(tǒng)一的定義形式數(shù)據(jù)質(zhì)量為信息系統(tǒng)對模式和數(shù)據(jù)實例的一致性、正確性、完整性和最小性的滿足程度數(shù)據(jù)質(zhì)量是數(shù)據(jù)適合使用的程度數(shù)據(jù)質(zhì)量是數(shù)據(jù)滿足特定用戶期望的程度數(shù)據(jù)質(zhì)量的內(nèi)容 數(shù)據(jù)真實性：數(shù)據(jù)真實并且準(zhǔn)確地反映實際 的業(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) 系的同時不違反相關(guān)約束數(shù)據(jù)質(zhì)量問題（臟數(shù)據(jù)來自哪里？） 數(shù)據(jù)源本身是臟數(shù)據(jù) 數(shù)據(jù)轉(zhuǎn)換/集成 數(shù)據(jù)本身價值的失效 數(shù)據(jù)質(zhì)量問

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

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

6、-IBM vs. International Business Machines孤立點（Outlier）數(shù)據(jù)錯誤（Data Error） 業(yè)務(wù)知識清理算法數(shù)據(jù)集成/數(shù)據(jù)變換 數(shù)據(jù)集成整合來自多個數(shù)據(jù)存儲的數(shù) 據(jù)，為數(shù)據(jù)分析、處理、挖掘提供完整的 數(shù)據(jù)源。數(shù)據(jù)變換將數(shù)據(jù)變換或統(tǒng)一成適合于數(shù)據(jù)分析挖掘的形式。數(shù)據(jù)集成中數(shù)據(jù)質(zhì)量問題分類問題類型問題描述數(shù)據(jù)表連接不 匹配來自多個數(shù)據(jù)源中的數(shù)據(jù)表需要通過相同的主鍵進行 自然連接，當(dāng)表中的主鍵不匹配時，出現(xiàn)無法連接的 現(xiàn)象冗余在連接數(shù)據(jù)表的過程中，沒有對表中的字段嚴(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ù)的映射處理，映射關(guān)系可以與平方根、標(biāo)準(zhǔn) 方差以及區(qū)域?qū)?yīng)屬性構(gòu)造根據(jù)已有的屬性集構(gòu)造新的屬性，以幫助數(shù)據(jù)挖 掘過程數(shù)據(jù)離散化將連續(xù)取值的屬性離散化成若干區(qū)間，來幫助消減一個連續(xù)屬性的取值個數(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)選擇一個優(yōu)化屬性子 集的過程。優(yōu)化屬性子集可以是屬性數(shù)目最小的子 集，也可以是含有最佳預(yù)測

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

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

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ì)量及評估2分布式數(shù)據(jù)處理模型及測試3大數(shù)據(jù)的基準(zhǔn)測試4大數(shù)據(jù)處理框架Hadoop在大數(shù)據(jù)領(lǐng)域中，Hadoop是最著名的大數(shù) 據(jù)處理框架之一，它以可靠、高效、可伸 縮的方式進行大數(shù)據(jù)的儲存、處理和分析。Hadoop由Apache基金會開發(fā)，在其實現(xiàn)的 過程中，借鑒了Google的三大核心組件即 GFS、MapReduce 和BigTable。Hadoop的生態(tài)圈Hadoop已發(fā)展成包含HDFS、MapReduce、YARN、Hbase、ZooKeeper等子項目的集合，用于處理和分析大規(guī)模數(shù)據(jù)MapReduce運行流程應(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ā)的針對MapReduce的單元測試框 架，其基本原理是利用JUnit4與EasyMock。MRUnit結(jié)構(gòu)簡 單，依賴于JUnit的單元測試功能，同時已經(jīng)通過實現(xiàn)Mock 對象控制OutputCollector操作并且攔截OutputCollector的輸 出，對比期望結(jié)果以達(dá)到自動斷言的目的。MRUnit的driverMapDriver：測試單獨的MapReduceDriver：測試單獨的ReduceMapReduceDriver：將Map與Reduce連貫起來測試Pip

14、elineMapReduceDriver：將多個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進行統(tǒng)計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();/運行測試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(); /運行測試MapReduce調(diào)試與測試的建議盡早采用MRUnit編寫對MapReduce中

17、的Map函數(shù)與Reduce 函數(shù)進行測試通過Assert（斷言）來使得程序滿足正確性條件，并通過print語句輸出可能的錯誤首先在本地運行小規(guī)模測試數(shù)據(jù)，再到集群上運行MapReduce程序通過Hadoop日志來分析MapReduce程序運行狀況目錄概述1面向數(shù)據(jù)質(zhì)量的測評2分布式數(shù)據(jù)模型及測試3大數(shù)據(jù)的基準(zhǔn)測試4大數(shù)據(jù)的基準(zhǔn)測試 基準(zhǔn)測試（Benchmark Testing）一種測量和評估軟件 性能指標(biāo)的典型活動。可以在某個時候通過基準(zhǔn)測試建立 一個已知的性能水平（稱為基準(zhǔn)線），當(dāng)系統(tǒng)的軟硬件環(huán) 境發(fā)生變化之后再進行一次基準(zhǔn)測試以確定那些變化對性 能的影響。基準(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ī)范、性能、性價 比度量的指標(biāo)。 OLTP基準(zhǔn)-TPC-A面向銀行事務(wù)管理、TPC-C面向倉庫訂單管理、TPC-E面向市場交易應(yīng)用 OLAP基準(zhǔn)-TPC-DS、TPC-H等OLAP的基準(zhǔn)，評測考察復(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ù)據(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ù)制存儲機制，選擇500GB的數(shù)據(jù)總 量，并選用TPC-DS為MySQL生成的99個查詢SQL，目的是保留各 種復(fù)雜SQL查詢，客觀反映Transwarp Inceptor在SQL支持與兼容性 的情況。 TPC-DS的基準(zhǔn)測試有以下特點

20、：一共99個測試案例，遵循SQL99和SQL 2003的語法標(biāo)準(zhǔn)，SQL案例比較復(fù)雜分析的數(shù)據(jù)量大，并且測試案例是在回答真實的商業(yè)問題測試案例中包含各種業(yè)務(wù)模型（如分析報告性，迭代式的在線 分析性，數(shù)據(jù)挖掘性等）幾乎所有的測試案例都有很高的IO負(fù)載和CPU計算需求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）文件 格式存儲原始數(shù)據(jù)，原始生成的text格式的數(shù)據(jù)總量大約為500G，轉(zhuǎn)成 ORC格式后將壓縮為大約150G。查詢執(zhí)行利

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

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

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

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

25、若目前的簇數(shù)多于預(yù)期的簇數(shù)，則重復(fù)步驟2-步驟4，直到簇數(shù) 滿足預(yù)期的簇數(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)，可以通過將所有點對的距離 保存在一個優(yōu)先隊列中，將算法優(yōu)化為O(n2 log n)。層次聚類的思想非常，但一般應(yīng)用于 規(guī)模較小的數(shù)據(jù)集。50聚類的典型算法及分析-K-均值聚類K-均值聚類的基本

26、思想：即按照某一順序依 次遍歷所有點，將點分配到最合適的簇中K-均值假定在歐式空間下，聚類數(shù)K已知，算法接受一個未標(biāo)記的數(shù)據(jù)集，然后將數(shù)據(jù)聚類成K個不同的簇聚類的典型算法及分析-K-均值聚類 首先選擇K個點，稱為聚類質(zhì)心（通常隨機選擇）； 遍歷數(shù)據(jù)集中的每一個點，按照距離K個質(zhì)心的距離，將其與距離最 近的質(zhì)心關(guān)聯(lián)起來，與同一個質(zhì)心相關(guān)聯(lián)的所有點聚成一類； 計算每一類中所有點位置的均值（新的質(zhì)心），將該類的質(zhì)心移動到新質(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為需要處理的點數(shù)、k為聚類質(zhì) 心數(shù)、t為迭代的次數(shù)。聚類的典型算法及分析-K-均值聚類圖 K-均值算法的動態(tài)迭代聚類的并行化為什么需要并行化？ 大數(shù)據(jù)時代，聚類算法所面臨的數(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ū)動程序來判斷迭代是否終止， 若迭代沒有終止，則需要驅(qū)動MapReduce程序重新執(zhí)行任務(wù)，直到滿足終止條件。Mapper任務(wù)：將數(shù)據(jù)集分成子集并與質(zhì)心描 述文件一起發(fā)送到各個Map節(jié)點，每個Map 節(jié)點分別執(zhí)行任務(wù)，即將子集中的數(shù)據(jù)分配 給最近點的質(zhì)心，并以所屬簇質(zhì)心為key，點 的索引為value，組成中間結(jié)果傳遞到Reducer 節(jié)點。Reducer任務(wù)：得到中間結(jié)果后將屬于同一簇的點計算新的質(zhì)心。 比較新的質(zhì)心與原有的質(zhì)心是否一致，如果 一致，代表算法已收斂，否則仍需

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

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

32、xn, n 1是f的n個變量, 且f(x1), f(x2) , f(xn)是它們所對應(yīng)的函數(shù)值。若x1, x2, , xn, 之間 滿足關(guān)系r 時, 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時, 起初選擇的測試用例稱為原 始測試用例； 由原始測試用例根據(jù)關(guān)系r計算得出的測試用例是該原 始測試用例基于

33、蛻變關(guān)系(r, rf)的衍生測試用例。智能算法測試的測試方法-蛻變測試蛻變測試的原理 第一，結(jié)合其它測試用例選擇的策略（比如路徑覆蓋測試或等價類劃分等）為待 測程序P生成原始測試用例x0； 第二、利用這些原始測試用例來測試程序，若都通過測試，且計算結(jié)果P(x0)，然 后進一步分析待測程序的特點，設(shè)計構(gòu)造一系列蛻變關(guān)系； 第三，根據(jù)這些蛻變關(guān)系生成衍生測試用例r1(x0)，r2(x0)，并計算衍生測試用例得到測試結(jié)果為P(r1(x0)和P(r2(x0)； 第四，分析原始測試用例的計算結(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： 屬性全局仿射變換的一致性。如果對原始測試用例中的每個屬性值(i)做仿射變換( i ) = (i) + ( 0)得到衍生測試用例，則聚類結(jié)果不變。60MR 1.2： 屬性局部仿射變換的一致性。 如果對原始測試用例

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

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

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

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

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

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

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

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

43、法的基本思想： 假設(shè)x = (x1, x2, , xm)為數(shù)據(jù)集中的某一樣本，其中xi是該樣本的第i個特征， 并有類別集合 C = y1, y2, , yk ；可以計算概率 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之間互相獨立，這也是為什么這個分類算法稱為樸素貝葉斯分類 算法。 根據(jù)概率論中的貝葉斯定理：p yi x=p x yi p(yi)p(x)考慮到分母對于所有類別為常數(shù)，因此只

44、需要考慮分子部分，根據(jù)樸素貝葉斯的假設(shè)，x的特征xi之間互相條件獨立，因此有：m70p x yi p yi= p x1 yip x2 yi p xm yip yi= p yi p xj yij=1分類的典型算法及分析-樸素貝葉斯分類算法樸素貝葉斯算法： 遍歷整個數(shù)據(jù)集，可以統(tǒng)計得到在k個類別下各個特征的條件概率估計，即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ù)以上的貝葉斯公式，可以計算得出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注：盡管樸素貝葉斯分類算法對于樣本數(shù)據(jù)稀疏時非常敏感（需要“拉普拉斯平滑”），但仍然是應(yīng) 用最廣的分類算法之一，被廣泛應(yīng)用于文本分類領(lǐng)域、用戶行為分析等大數(shù)據(jù)分析挖掘領(lǐng)域。分類的典型算法及分析-支持向量機算法支持向量機算法的基本思想： 尋找一個滿足分類要求的最優(yōu)分類超平面，使得該超平面在保證分類精度的 同時，能夠使超平面兩側(cè)的間隔最大化。圖 線性的支持向量機原理

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

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

48、證（Cross-validation） 二折交叉驗證假設(shè)把數(shù)據(jù)分為相同大小的兩個子集，首先選擇其中一個子集作為訓(xùn)練集，另一個 作為測試集，然后交換兩個子集的角色，這種方法稱為二折交叉驗證。分類總誤差通過 對兩次運行的誤差求和得到。 K折交叉驗證K折交叉驗證方法是二折交叉驗證的推廣，即把數(shù)據(jù)集分成獨立并數(shù)量相同的K份。 每次驗證時選擇其中的一份作為測試集，其余的 K 1 份都作為訓(xùn)練集，該過程重復(fù) K 次， 使得每份數(shù)據(jù)都用于測試恰好一次。同樣，分類的總誤差是說有K次誤差之和。分類算法（分類器）性能的評估準(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ù)測類別+-實際 類別+正確的正例（TP）錯誤的負(fù)例（FN）-錯誤的正例（FP）正確的負(fù)例（TN）分類算法（分類器）性能的評估ROC曲線與AUC的一些說明ROC曲線與AUC(FPR=0,TPR=0)意味著分類器將每個樣本都預(yù)測為負(fù)例(FPR=1,TPR=1)意味著分類器將每個 樣本都預(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對應(yīng)的分類器性能優(yōu)于A。求AUC 值的最通用方法是通過積分法求ROC 曲線下方的面積。X軸是錯誤的正例率（False Positive Rate，F(xiàn)PR），F(xiàn)PFPR =FP + TNY軸是正確的正例率（True Positive Rate，TPR），TPTPR =TP + FNROC曲線與AUC目錄概述1聚類算法及測評2分類算法及測評3推薦系統(tǒng)及測評4推薦系統(tǒng)概述 個性化推薦系統(tǒng)：是一種利用用戶

51、歷史行為數(shù)據(jù)，建 立用戶行為模型，幫助用戶過濾無關(guān)信息、提供最能 滿足用戶個性化需求信息的智能系統(tǒng)。推薦系統(tǒng)的核心流程用戶特征收集模塊：該模塊負(fù)責(zé)收集用戶的歷史行為，比如評分、購買、瀏覽、評論等行為，這些行 為可以用來描述用戶的偏好。用戶行為建模與分析模塊：該模塊根據(jù)收集得到的用戶歷史行為，構(gòu)建合適的數(shù)學(xué)模型來分析用戶的 偏好或找出相似偏好的用戶。物品的排序與推薦模塊：該模塊將用戶的行為信息作為特征，通過推薦算法快速獲得用戶感興趣的物 品，并將物品排序后推薦給用戶。推薦系統(tǒng)的評估模塊：該模塊負(fù)責(zé)評估推薦系統(tǒng)是否滿足應(yī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)容向量，其可以從物品的 特征信息中獲得。那么，對于任意一個用戶u和一個他不知道的物品c，用戶物品偏好向量 UserProfile u 與Content(c)的相似度可定義如下：s u, c= sim(UserProfile , )接下來，就可以通過比

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

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

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

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

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

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

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

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