商务智能原理与方法（第3版）-课件 Lecture2-Clustering

数据挖掘——聚类数据挖掘流程输入数据Knowledge

Discovery数据挖掘数据预处理数据后处理数据聚集数据标准化特征选取维度规约模式发现关联分析分类聚类其他方法…………模式评估模式选取模式解释模式可视化聚类是数据挖掘的核心方法之一数据预处理数据聚集将两个或多个数据对象合并为单个数据对象常通过求和或求平均值的方式减少数据量，减少计算负载，使用开销更大的方法可能导致细节丢失数据抽样有放回抽样无放回抽样数据预处理维度规约/属性选择降低数据属性的个数减少噪音，降低复杂度属性创建对旧的属性进行处理，创建新的数据集对照片数据处理，提取一些高层次的特征人脸识别：人脸高度相关的边和区域眼睛、鼻子、嘴、下巴等局部之间结构关系的几何描述，可作为识别人脸的重要特征离散化将连续属性转化为离散属性什么是聚类将原始数据划分成簇(Cluster)聚类准则:类内数据足够相似类间数据尽量不同聚类问题也是有优化问题：同时优化类内相似（尽量大）和类间相似（尽量小）聚类的应用：有助于分析未知数据的分布情况可在别的分析方法之前对数据进行先期分析文本分析、客户管理管理、气候分析、社会网络、医疗分析…聚类的起源1854年8月31日，伦敦爆发大规模霍乱JohnSnow，将上报的霍乱病例进行聚类英国历史上最大的一次霍乱.发现大量的霍乱病例集中在一处水井的附近确定水井为霍乱的根源聚类vs分类有监督学习有数据类别信息聚类结果的评判是一个主观问题填空题vs问答题分类无监督学习无数据类别信息聚类聚类过程输入数据数据预处理聚类聚类结果检验输出聚类结果数据相似度计算聚类方法相似度计算方法，聚类方法，聚类结果检验测度:聚类领域的三个主要研究方面测度相似度计算方法聚类方法设计相似度计算数据之间相似程度越高，距离越近数据之间相似程度越低，距离越远Sim(i,j)相似关系用于计算数据之间相似程度（距离）BooleanNominalNumericText相似度(距离函数)的计算方法因数据类型的不同而不同数值属性的相似关系Euclideandistance（欧几里得距离）:相似度计算方法:Manhattandistance（曼哈顿距离）:Minkowskidistance（闵可夫斯基距离）:加权欧式距离平方欧式距离(加大距离较远的权重)平方欧式距离(加大距离较远的权重)二值属性的相似关系两个状态值1或0布尔属性1,0同等重要1,0不同等重要对称属性非对称属性混合矩阵Jaccard距离二值属性的相似关系给定以下两个数据点，它们的每个属性都是对称的布尔属性两个数据点之间的距离为x11110100x20110010如果是非对称的布尔属性？SimilarityofNominalAttribute具有多于两个状态或值数据的属性数目为r计算两个数据之间属性值匹配的属性数目为q选择一个属性作主导属性，其他属性进行转换Apple、Orange、Pear，根据水果价格转化成区间度量属性不同类型的属性单独计算距离，加权平均给定两个数据点ti和tj混合属性文本相似关系向量空间模型(Salton,1975)用同样维度的向量表示文本第一次出现在SMART系统中文本分词TF-IDF模型文本频率,ti在文本集合中出现的次数词频，ti在文本dj中出现的次数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;簇的相似关系MinSimilarity簇间数据对相似关系的最小值dist(Ki,Kj)=min(tip,tjq)MaxSimilarity簇间数据对相似关系的最大值dist(Ki,Kj)=max(tip,tjq)Average簇间数据对相似关系的平均值dist(Ki,Kj)=avg(tip,tjq)Centroid两个簇的centroids之间的距离dist(Ki,Kj)=dist(Ci,Cj)Medoid两个簇的medoids之间的距离，dist(Ki,Kj)=dist(Mi,Mj)Medoid:簇中真实存在的一个点，位于中心或中心附近Centroid:簇中虚拟存在的一个点，位于中心聚类算法可扩展性处理不同数据的能力发现任意形状的聚类用于决定输入参数的领域知识最小化处理“噪声”数据的能力对于输入记录的顺序不敏感高维度基于约束的聚类聚类算法Partitioningapproach（划分式方法）构建不同划分，选择划分结果最好的k-means,k-medoids,CLARANS构建一个层次的树状结构Diana,Agnes,BIRCH,CAMELEON基于连接和密度函数DBSACN,OPTICS,DenClueHierarchicalapproach（层次式方法）Density-basedapproach（基于密度的方法）FuzzyClustering-based（模糊聚类方法）允许一个数据属于多于一个类别FuzzyC-means划分式方法

(K-means)将原始数据划分成k个簇K-means:每个簇可通过中心代表(中心可以为虚拟)K-medoids:每个簇可通过一个实点代表第一步：选择k个点作为初始中心第二步：将数据划分到最近的中心第三步：重新计算每个簇的中心第四步：重新计算数据到k个中心的聚类，将数据划分到距离最近的中心第五步：重新回到步骤三，直至划分结果不再变化K-means聚类过程K-means示例012345678910012345678910012345678910012345678910K=2随机选择k个点作为中心划分数据更新簇中心更新簇中心重新划分重新划分K-means优点适用于凸形分布的数据时间复杂度低，适用于大规模数据O(tkn),n:objects,k:clusters,t:iterationtimesK-means局限剩下数据点分到最近的中心剩下的数据点进行分类对噪音数据敏感平均相似度去除那些比较远的数据点随机采样，先用采样点聚类，分配其他数据K-means局限倾向于将数据划分为均匀分布K-means局限局部最优需要提前指定k中心点选取计算全体中心，每次选取最远的数据点异常点无效，进行数据采样套接别的聚类方法层次式方法建立簇的层次结构（树状结构）汇聚式"bottomup"初始时假设每个数据单独构成一个簇，方法的每一步合并两个簇分裂式"topdown"初始时所有数据构成一个簇，方法的每一步分裂一个簇Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerativedivisive层次式方法的优缺点优点:不需要指定k不会将数据聚成均匀分布可通过一次聚类构成树状分布，同时提供多粒度的聚类结果不能发现和修正聚类过程中的错误时间复杂度高至少O(n2)，不适用于处理大规模数据局限:基于密度的聚类基于数据密度的聚类过程DBscanEps:

最大半径MinPts:

在最大半径范围内所出现的最小领点个数NEps(p):{qbelongstoD|dist(p,q)≤Eps}CorePointq：|NEps(q)|≥MinPtsBorderPointp：|NEps(q)|≥MinPtsPbelongstoNEps(q),q是corepointOutlierCoreBorderOutlierEps=1cm,MinPts=5基于密度的聚类基于数据密度的聚类过程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，一个簇构建成功如果p是borderpoint，没有点是从pdensity-reachable，DBSCAN方法扫描下一个数据点重复迭代上述过程，直至所有点都被方法扫描并处理Dbscan的优缺点优点:不需要提前指定类别个数可发现任意形状的簇可处理噪音数据两个参数需要指定：Eps,MinPts不适用于高维数据聚类：高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象对于低维数据效果较好局限:聚类结果评测如何评判聚类结果的好坏？两一副扑克牌的聚类？有几种聚类结果？聚类结果评测用于评测聚类结果是否足够“好”怎样定义足够“好”和“足够相似”？评测过程具有主观性聚类结果评测方法用户验证InternalClusterValidation不知道真实类别标签ExternalClusterValidation知道真实类别标签，将聚类结果与真实类别对比InternalClusterValidation测量聚类结果的两个方面:Cohesion:类内数据之间的相似度尽量大Separation:类间数据尽量不同.多种internalvalidationmeasures两个示例:ExternalClusterValidation将聚类结果与真实类别标签对比.EntropyPurityF-measurePartitioncoefficientValidationofinformationV-measure好的聚类结果应该是：聚类结果中的每一类都只包含原始数据中的一种数据C1C2C3C1+

C2+

C3+

信息熵在信息论中，熵被用来衡量一个随机变量出现的期望值。它代表了在被接收之前，信号传输过程中损失的信息量，又被称为信息熵。信息熵也称信源熵、平均自信息量。在1948年，克劳德·艾尔伍德·香农将热力学的熵，引入到信息论，因此它又被称为香农熵。信息熵在信息论中，如果一个信号源能够发出不同的信号A={a1,a2,…,an}，每个信号的概率为pi，并且∑pi=1，假设所有的信号都是独立的，那么整个信息熵定义为：如果P1=P2=…=Pi=1/n，则信息熵最大，等于logn如果一个为1，其余为0，则信息熵最小，等于0“熵”源自热物理学在一个封闭系统中，熵总是最大的两种气体，完全混合时，可以达到热物理学中的稳定状态，熵最高Entropy测量聚类结果中每一个类在真实类别上的分布情况.Entropy越小，聚类结果越好对于一个给定的类Cp,相应的entropy是:聚类结果的整体Entropy为每一个类的Entropy的加权平均C1C2C3C1+

C2+

C3+

Purity测量角度与Entropy类似Purity越大，聚类结果越好对于一个给定的类Cp,相应的purity是:聚类结果的整体purity为每一个类的Purity的加权平均C1C2C3C1+

C2+

C3+

数据挖掘的发展方向Web应用数据流处理以及针对易丢失数据等特殊情况的专用处理方法大规模高维数据集的聚类方法信息搜索技术，信息推荐和归纳大数据与数据挖掘关注用户关注多源数据数据挖掘的新特征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