商務(wù)智能原理與方法（第3版）-課件 Lecture2-Clustering

數(shù)據(jù)挖掘——聚類數(shù)據(jù)挖掘流程輸入數(shù)據(jù)Knowledge

Discovery數(shù)據(jù)挖掘數(shù)據(jù)預處理數(shù)據(jù)后處理數(shù)據(jù)聚集數(shù)據(jù)標準化特征選取維度規(guī)約模式發(fā)現(xiàn)關(guān)聯(lián)分析分類聚類其他方法…………模式評估模式選取模式解釋模式可視化聚類是數(shù)據(jù)挖掘的核心方法之一數(shù)據(jù)預處理數(shù)據(jù)聚集將兩個或多個數(shù)據(jù)對象合并為單個數(shù)據(jù)對象常通過求和或求平均值的方式減少數(shù)據(jù)量，減少計算負載，使用開銷更大的方法可能導致細節(jié)丟失數(shù)據(jù)抽樣有放回抽樣無放回抽樣數(shù)據(jù)預處理維度規(guī)約/屬性選擇降低數(shù)據(jù)屬性的個數(shù)減少噪音，降低復雜度屬性創(chuàng)建對舊的屬性進行處理，創(chuàng)建新的數(shù)據(jù)集對照片數(shù)據(jù)處理，提取一些高層次的特征人臉識別：人臉高度相關(guān)的邊和區(qū)域眼睛、鼻子、嘴、下巴等局部之間結(jié)構(gòu)關(guān)系的幾何描述，可作為識別人臉的重要特征離散化將連續(xù)屬性轉(zhuǎn)化為離散屬性什么是聚類將原始數(shù)據(jù)劃分成簇(Cluster)聚類準則:類內(nèi)數(shù)據(jù)足夠相似類間數(shù)據(jù)盡量不同聚類問題也是有優(yōu)化問題：同時優(yōu)化類內(nèi)相似（盡量大）和類間相似（盡量?。┚垲惖膽?yīng)用：有助于分析未知數(shù)據(jù)的分布情況可在別的分析方法之前對數(shù)據(jù)進行先期分析文本分析、客戶管理管理、氣候分析、社會網(wǎng)絡(luò)、醫(yī)療分析…聚類的起源1854年8月31日，倫敦爆發(fā)大規(guī)模霍亂JohnSnow，將上報的霍亂病例進行聚類英國歷史上最大的一次霍亂.發(fā)現(xiàn)大量的霍亂病例集中在一處水井的附近確定水井為霍亂的根源聚類vs分類有監(jiān)督學習有數(shù)據(jù)類別信息聚類結(jié)果的評判是一個主觀問題填空題vs問答題分類無監(jiān)督學習無數(shù)據(jù)類別信息聚類聚類過程輸入數(shù)據(jù)數(shù)據(jù)預處理聚類聚類結(jié)果檢驗輸出聚類結(jié)果數(shù)據(jù)相似度計算聚類方法相似度計算方法，聚類方法，聚類結(jié)果檢驗測度:聚類領(lǐng)域的三個主要研究方面測度相似度計算方法聚類方法設(shè)計相似度計算數(shù)據(jù)之間相似程度越高，距離越近數(shù)據(jù)之間相似程度越低，距離越遠Sim(i,j)相似關(guān)系用于計算數(shù)據(jù)之間相似程度（距離）BooleanNominalNumericText相似度(距離函數(shù))的計算方法因數(shù)據(jù)類型的不同而不同數(shù)值屬性的相似關(guān)系Euclideandistance（歐幾里得距離）:相似度計算方法:Manhattandistance（曼哈頓距離）:Minkowskidistance（閔可夫斯基距離）:加權(quán)歐式距離平方歐式距離(加大距離較遠的權(quán)重)平方歐式距離(加大距離較遠的權(quán)重)二值屬性的相似關(guān)系兩個狀態(tài)值1或0布爾屬性1,0同等重要1,0不同等重要對稱屬性非對稱屬性混合矩陣Jaccard距離二值屬性的相似關(guān)系給定以下兩個數(shù)據(jù)點，它們的每個屬性都是對稱的布爾屬性兩個數(shù)據(jù)點之間的距離為x11110100x20110010如果是非對稱的布爾屬性？SimilarityofNominalAttribute具有多于兩個狀態(tài)或值數(shù)據(jù)的屬性數(shù)目為r計算兩個數(shù)據(jù)之間屬性值匹配的屬性數(shù)目為q選擇一個屬性作主導屬性，其他屬性進行轉(zhuǎn)換Apple、Orange、Pear，根據(jù)水果價格轉(zhuǎn)化成區(qū)間度量屬性不同類型的屬性單獨計算距離，加權(quán)平均給定兩個數(shù)據(jù)點ti和tj混合屬性文本相似關(guān)系向量空間模型(Salton,1975)用同樣維度的向量表示文本第一次出現(xiàn)在SMART系統(tǒng)中文本分詞TF-IDF模型文本頻率,ti在文本集合中出現(xiàn)的次數(shù)詞頻，ti在文本dj中出現(xiàn)的次數(shù)AnExampled1=“我在人民大學學習?！?(我，人民大學，學習)d2=“我在人民大學工作?！?(我，人民大學，工作)d3=“我在人民大學工作，工作很愉快?！?(我，人民大學，工作，愉快)三個文檔共5個維度：我，人民大學，學習，工作，愉快對于文檔d1第一個分量“我”:tf=1,df=3,idf=0,tf*idf=0;第二個分量“人民大學”:tf=1,df=3,idf=0,tf*idf=0;第三個分量“學習”:tf=1,df=1,idf=0.477,tf*idf=0.477第四、五個分量“工作”“愉快”:tf=0,tf*idf=0;d1=(0,0,0.477,0,0)AnExampled1=“我在人民大學學習。”=(0,0,0.477,0,0)d2=“我在人民大學工作?！?(0,0,0,0.176,0)d3=“我在人民大學工作，工作很愉快?！?(0,0,0,0.352,0.477)Similaritybetweendocuments大量的實踐證明tf-idf模型的有效性新模型：BM25，PLSI，LDASim(d1,d2)=(0,0,0.477,0,0)*(0,0,0,0.176,0)/(|d1|*|d2|)=0;Sim(d1,d3)=(0,0,0.477,0,0)*(0,0,0,0.352,0.477)/(|d1|*|d3|)=0;Sim(d2,d3)=(0,0,0,0.176,0)*(0,0,0,0.352,0.477)/(|d2|*|d3|)=0.594;簇的相似關(guān)系MinSimilarity簇間數(shù)據(jù)對相似關(guān)系的最小值dist(Ki,Kj)=min(tip,tjq)MaxSimilarity簇間數(shù)據(jù)對相似關(guān)系的最大值dist(Ki,Kj)=max(tip,tjq)Average簇間數(shù)據(jù)對相似關(guān)系的平均值dist(Ki,Kj)=avg(tip,tjq)Centroid兩個簇的centroids之間的距離dist(Ki,Kj)=dist(Ci,Cj)Medoid兩個簇的medoids之間的距離，dist(Ki,Kj)=dist(Mi,Mj)Medoid:簇中真實存在的一個點，位于中心或中心附近Centroid:簇中虛擬存在的一個點，位于中心聚類算法可擴展性處理不同數(shù)據(jù)的能力發(fā)現(xiàn)任意形狀的聚類用于決定輸入?yún)?shù)的領(lǐng)域知識最小化處理“噪聲”數(shù)據(jù)的能力對于輸入記錄的順序不敏感高維度基于約束的聚類聚類算法Partitioningapproach（劃分式方法）構(gòu)建不同劃分，選擇劃分結(jié)果最好的k-means,k-medoids,CLARANS構(gòu)建一個層次的樹狀結(jié)構(gòu)Diana,Agnes,BIRCH,CAMELEON基于連接和密度函數(shù)DBSACN,OPTICS,DenClueHierarchicalapproach（層次式方法）Density-basedapproach（基于密度的方法）FuzzyClustering-based（模糊聚類方法）允許一個數(shù)據(jù)屬于多于一個類別FuzzyC-means劃分式方法

(K-means)將原始數(shù)據(jù)劃分成k個簇K-means:每個簇可通過中心代表(中心可以為虛擬)K-medoids:每個簇可通過一個實點代表第一步：選擇k個點作為初始中心第二步：將數(shù)據(jù)劃分到最近的中心第三步：重新計算每個簇的中心第四步：重新計算數(shù)據(jù)到k個中心的聚類，將數(shù)據(jù)劃分到距離最近的中心第五步：重新回到步驟三，直至劃分結(jié)果不再變化K-means聚類過程K-means示例012345678910012345678910012345678910012345678910K=2隨機選擇k個點作為中心劃分數(shù)據(jù)更新簇中心更新簇中心重新劃分重新劃分K-means優(yōu)點適用于凸形分布的數(shù)據(jù)時間復雜度低，適用于大規(guī)模數(shù)據(jù)O(tkn),n:objects,k:clusters,t:iterationtimesK-means局限剩下數(shù)據(jù)點分到最近的中心剩下的數(shù)據(jù)點進行分類對噪音數(shù)據(jù)敏感平均相似度去除那些比較遠的數(shù)據(jù)點隨機采樣，先用采樣點聚類，分配其他數(shù)據(jù)K-means局限傾向于將數(shù)據(jù)劃分為均勻分布K-means局限局部最優(yōu)需要提前指定k中心點選取計算全體中心，每次選取最遠的數(shù)據(jù)點異常點無效，進行數(shù)據(jù)采樣套接別的聚類方法層次式方法建立簇的層次結(jié)構(gòu)（樹狀結(jié)構(gòu)）匯聚式"bottomup"初始時假設(shè)每個數(shù)據(jù)單獨構(gòu)成一個簇，方法的每一步合并兩個簇分裂式"topdown"初始時所有數(shù)據(jù)構(gòu)成一個簇，方法的每一步分裂一個簇Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerativedivisive層次式方法的優(yōu)缺點優(yōu)點:不需要指定k不會將數(shù)據(jù)聚成均勻分布可通過一次聚類構(gòu)成樹狀分布，同時提供多粒度的聚類結(jié)果不能發(fā)現(xiàn)和修正聚類過程中的錯誤時間復雜度高至少O(n2)，不適用于處理大規(guī)模數(shù)據(jù)局限:基于密度的聚類基于數(shù)據(jù)密度的聚類過程DBscanEps:

最大半徑MinPts:

在最大半徑范圍內(nèi)所出現(xiàn)的最小領(lǐng)點個數(shù)NEps(p):{qbelongstoD|dist(p,q)≤Eps}CorePointq：|NEps(q)|≥MinPtsBorderPointp：|NEps(q)|≥MinPtsPbelongstoNEps(q),q是corepointOutlierCoreBorderOutlierEps=1cm,MinPts=5基于密度的聚類基于數(shù)據(jù)密度的聚類過程Directlydensity-reachable：

p屬于

NEps(q)q是corepoint:|NEps(q)|≥MinPtsDensity-reachable:Apointpisdensity-reachablefromapointqw.r.t.Eps,MinPts具有一條p1,…,pn,p1=q,pn=p

pi+1directlydensity-reachablefrompi

MinPts=5Eps=1cmpqpqp1Apointpisdirectlydensity-reachablefromapointqw.r.t.Eps,MinPtsifDbscan方法過程隨機選擇一個點p在給定Eps和MinPts的情況下，獲取所有從pdensity-reachable的點如果p是corepoint，一個簇構(gòu)建成功如果p是borderpoint，沒有點是從pdensity-reachable，DBSCAN方法掃描下一個數(shù)據(jù)點重復迭代上述過程，直至所有點都被方法掃描并處理Dbscan的優(yōu)缺點優(yōu)點:不需要提前指定類別個數(shù)可發(fā)現(xiàn)任意形狀的簇可處理噪音數(shù)據(jù)兩個參數(shù)需要指定：Eps,MinPts不適用于高維數(shù)據(jù)聚類：高維空間中數(shù)據(jù)較低維空間中數(shù)據(jù)分布要稀疏，其中數(shù)據(jù)間距離幾乎相等是普遍現(xiàn)象對于低維數(shù)據(jù)效果較好局限:聚類結(jié)果評測如何評判聚類結(jié)果的好壞？兩一副撲克牌的聚類？有幾種聚類結(jié)果？聚類結(jié)果評測用于評測聚類結(jié)果是否足夠“好”怎樣定義足夠“好”和“足夠相似”？評測過程具有主觀性聚類結(jié)果評測方法用戶驗證InternalClusterValidation不知道真實類別標簽ExternalClusterValidation知道真實類別標簽，將聚類結(jié)果與真實類別對比InternalClusterValidation測量聚類結(jié)果的兩個方面:Cohesion:類內(nèi)數(shù)據(jù)之間的相似度盡量大Separation:類間數(shù)據(jù)盡量不同.多種internalvalidationmeasures兩個示例:ExternalClusterValidation將聚類結(jié)果與真實類別標簽對比.EntropyPurityF-measurePartitioncoefficientValidationofinformationV-measure好的聚類結(jié)果應(yīng)該是：聚類結(jié)果中的每一類都只包含原始數(shù)據(jù)中的一種數(shù)據(jù)C1C2C3C1+

C2+

C3+

信息熵在信息論中，熵被用來衡量一個隨機變量出現(xiàn)的期望值。它代表了在被接收之前，信號傳輸過程中損失的信息量，又被稱為信息熵。信息熵也稱信源熵、平均自信息量。在1948年，克勞德·艾爾伍德·香農(nóng)將熱力學的熵，引入到信息論，因此它又被稱為香農(nóng)熵。信息熵在信息論中，如果一個信號源能夠發(fā)出不同的信號A={a1,a2,…,an}，每個信號的概率為pi，并且∑pi=1，假設(shè)所有的信號都是獨立的，那么整個信息熵定義為：如果P1=P2=…=Pi=1/n，則信息熵最大，等于logn如果一個為1，其余為0，則信息熵最小，等于0“熵”源自熱物理學在一個封閉系統(tǒng)中，熵總是最大的兩種氣體，完全混合時，可以達到熱物理學中的穩(wěn)定狀態(tài)，熵最高Entropy測量聚類結(jié)果中每一個類在真實類別上的分布情況.Entropy越小，聚類結(jié)果越好對于一個給定的類Cp,相應(yīng)的entropy是:聚類結(jié)果的整體Entropy為每一個類的Entropy的加權(quán)平均C1C2C3C1+

C2+

C3+

Purity測量角度與Entropy類似Purity越大，聚類結(jié)果越好對于一個給定的類Cp,相應(yīng)的purity是:聚類結(jié)果的整體purity為每一個類的Purity的加權(quán)平均C1C2C3C1+

C2+

C3+

數(shù)據(jù)挖掘的發(fā)展方向Web應(yīng)用數(shù)據(jù)流處理以及針對易丟失數(shù)據(jù)等特殊情況的專用處理方法大規(guī)模高維數(shù)據(jù)集的聚類方法信息搜索技術(shù)，信息推薦和歸納大數(shù)據(jù)與數(shù)據(jù)挖掘關(guān)注用戶關(guān)注多源數(shù)據(jù)數(shù)據(jù)挖掘的新特征ExtractingRepresentativeInformationonIntra-organizationalBloggingPlatformsLivinginBigDataBlogSystemsWikiERPCRMWeibo/TwitterSearchResultsSocialNetworkOnlineReviewEnterprisesaresurroundedwithlargevolumeofinternalandexternaldata.Internaldata:BlogSystems,Wiki,CRM,ERPExternaldata:Weibo,SocialNetwork,OnlineReview,SearchResulsCopeWithBigDataInternal/Externaldataisveryimportantforenterprisemanagement.InternalData:helpunderstandthesituationoftheorganization,Optimizeorganizationalstructure,ImproveefficiencyExternalDate:Improveservicequality,Competitivemarketing.Informationfromlarge-scaledatathatexceedsthehumanprocessingcapacitycausesabiginconvenienceformanagers.Itisverynecessarytoproviderepresentativeinformation.ResearchQuestions:DesignPerspectiveManagerialneeds:Informationaccumulatedonsuchacrowd-basedplatformispotentiallyusefulformanagerstosupporttheirmanagerialwork.However,difficultyliesinthehugeamountofdatageneratedonsuchaplatform.Inordertobetterunderstandtheprevailingthoughtsandemergingopinionsamongtheemployees,whicharticlesshouldtheyread?Informationneeds:OnpublicblogsuserscontentthatfitswiththeirowninterestwidelydiscussedtopicsManagerialusersbemoreawareofdiversevoicesemergingideasandopinionsTarget:RepresentativenessResearchQuestions:RepresentativenessRepresentativenessSubsetoforiginalinformation.(Compactcontent)Thecontentredundancyislow.(Compactcontent)Covermostoriginalcontent.(Richcontent)BlogSystemsWikiERP…RepresentativeSubsetManagerialDecisionCovermore,lessredundantLearnmore,costlessOriginalInformationResearchQuestionHowtofindrepresentativeinformationtosupporttheneedofmanagement?…RepresentativeSubsetInformationSourceDesignScienceResearchParadigm(Hevneretal.,2004;GregorandHevner,2013)DesignFrameworkThecoreintheframeworkistheextractionengine.RequirementsfortheExtractionMethodFromtheperspectiveoffunctionalityTheextractedarticlesshouldbeindeedrepresentativeTheyshouldcoverthecontentofthetargetedarticlepopulationtoalargeextentFromtheperspectiveofusabilityUserswouldliketofreelyspecifythenumberofrepresentativearticlestodisplayTheresultsshouldbepresentedinrealtimeFromtheperspectiveofinformationgranularityUserswouldliketo“drilldown”onrepresentativeSuchqueriesshouldalsoberespondedtoinrealtime.TheREPSETProcedureThecoreintheprocedureistheclusteringalgorithm.RequirementsfortheClusteringAlgorithmThequality(accuracy)ofclusteringresultsshouldbehigh.BasisforhighqualityofrepresentativeextractionThenumberofclustersshouldnotbearbitrarilydeterminedinadvance.Itshouldbeabletobeflexiblyadjustedwhenwanted,sothatthesystemcanrespondimmediatelyoncetheuserhasselectedadifferentnumberofrepresentativearticlesThereshouldbeamulti-levelstructureintheresultingclusters,sothatthenavigationfeaturessuchas“drilldown”forrepresentativearticlescanbefacilitated.FeaturesofExistingClusteringMethodsRelatedwork(VLDB,2000;TKDS,2002,2004;JCSS,2003;TKDE,2004;ACS,2008;INS,2009,2011;SIGIR,1998,2001;JETWI,2010;IPM2005)Twocommonlyuseddocumentclusteringalgorithms,PartitionalandHierarchicalClustering.(Steinbachetal.,2000)Steinbach,M.,Karypis,G.,&Kumar,V.(2000,August).Acomparisonofdocumentclusteringtechniques.InKDDworkshopontextmining(Vol.400,No.1,pp.525-526).PartitionclusteringTypically,k-meansanditsvariationsManagersneedtospecifythenumberofk.Verydifficult.Notpractical.HierarchicalclusteringTypically,agglomerativeclusteringalgorithmClusterallthedocumentsintoonedendrogramNoneedtopre-determinedthenumberofkCannotallocatedataobjectsthathavebeenassignedatpreviousstages.FeaturesofExistingClusteringMethodsTable1:FeaturesofClusteringMethods.MethodsAccuracyNumberofclustersMulti-levelclustersApplicableforvaryingsizes,densities,andstructuresPartitionalclusteringmedium-highfixednonoDensity-basedclusteringmedium-highfixednoyesHierarchicalclusteringlow-mediumflexibleyesyesExistingdocumentclusteringalgorithmarenotsuitable,andcannotmeetthemanagerialrequirements.Weneedtoproposeanewdocumentclusteringalgorithmbasedonthehierarchicalclusteringalgorithm.Why?LocalOptimumvsGlobalOptimumRepSetClusteringAlgorithmIncorporatetwonewfeaturesintotraditionalagglomerativeclusteringmethodsanoptimizationstrategytoidentifythedocumentsassignedintowrongclusterswhilemerginganotherstrategytore-allocatethewrongdocumentsEffectivenessofRepSetIdentifythepotentialwrongdataobjectswithinanewclusterAssignittoarightclusterABCDEFGHABABCK=1K=2K=3DEFGHBCAK=4BCDHGFAERepSetClusteringAlgorithmEvaluationThreestagesBenchmarkdataevaluationEmpiricalEvaluationTheperformanceoftheproposedclusteringalgorithmEntropyPurityParametertuningIdentifyingboundariesofthenewclusterTheperformanceoftherepresentativeinformationextractionmethod“defacto”measuresperceivedmeasuresEvaluation-Stage1BenchmarkDataEvaluation:accuracyoftheclusteringalgorithm10widely-usedclusteringalgorithms30benchmarkdatasetsComparedwith10

othercommonlyusedclusteringalgorithmsUsed30

benchmarkdatasetsUsed2measuresofclusteringaccuracy(EJOR,2006)Entropy(Theless,thebetter)Purity(Themore,thebetter)Intotal,660testinginstancesEvaluation-Stage1EfficiencyPerformanceRunningtimeMemoryconsumptionEvaluation-Stage2Thevalueoftheparameterλmayaffecttheaccuracyoftheclusteringalgorithms.Beforetheextractionofrepresentativeinformation,thevalueofλcanbetunedinlightofthefollowingmeasure:Theclusteringresultisbetterwhenin-clustersimilaritiesarehighandbetween-clusterssimilaritiesarelow.Ahigh-levelvalueofCS.AhigherCSvalueindicatesamoreappropriatevalueofλ.SincetheexpressionofCSdoesnotexplicitlyincludeλ,acommonlyusedparameter-tuningtechniquecalledstepwiseself-tuning.Thevalueofλcanbesetas{0.1,0.2,0.3,…,0.9},respectively.CSvaluescanbecalculatedateverylevelofthedendrogram.Evaluation-Stage2Withregardtotheproportionsofre-allocatedobjects,wehaveaddedaboxplotshowingtheaveragere-allocationproportionacrossthe30benchmarkdatasetsineverystageofiterations.Evluation-Stage3EmpiricalEvaluationsDataExperiments“defacto”measures:coverage,redundancy,F1MeasureUserExperimentsPerceivedmeasures:coverage,redundancy,F1MeasureReal-worldbloggingdataDatain6years10,092,206articles31,356,918reads17,633,882commentsSurveydataApril20132,051employees,72questionnaireitems4clusteringalgorithms,3LDAalgorithms,Random,Top-rated,Most-read,Top-commentedEvluation-Stage3“Defacto”measures:coverage,redundancy,F1-MeasureContentcoverageontheoriginaldatasetT(defactocoverage):ContentredundancywithinthesubsetR(defactoredundancy):BenchmarkDataBenchmarkDataUserExperimentsUserExperimentsUserExperimentsConclusionIntheeraofBigData,abundantinformationofinternal/externaldatamaycauseabiginconvenienceforenterprisemanagersintheirdecision-makingprocess.ProposearepresentativeinformationextractionmethodThesu