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

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

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

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

最大半徑MinPts:

在最大半徑范圍內(nèi)所出現(xiàn)的最小領(lǐng)點(diǎn)個(gè)數(shù)NEps(p):{qbelongstoD|dist(p,q)≤Eps}CorePointq：|NEps(q)|≥MinPtsBorderPointp：|NEps(q)|≥MinPtsPbelongstoNEps(q),q是corepointOutlierCoreBorderOutlierEps=1cm,MinPts=5基于密度的聚類(lèi)基于數(shù)據(jù)密度的聚類(lèi)過(guò)程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方法過(guò)程隨機(jī)選擇一個(gè)點(diǎn)p在給定Eps和MinPts的情況下，獲取所有從pdensity-reachable的點(diǎn)如果p是corepoint，一個(gè)簇構(gòu)建成功如果p是borderpoint，沒(méi)有點(diǎn)是從pdensity-reachable，DBSCAN方法掃描下一個(gè)數(shù)據(jù)點(diǎn)重復(fù)迭代上述過(guò)程，直至所有點(diǎn)都被方法掃描并處理Dbscan的優(yōu)缺點(diǎn)優(yōu)點(diǎn):不需要提前指定類(lèi)別個(gè)數(shù)可發(fā)現(xiàn)任意形狀的簇可處理噪音數(shù)據(jù)兩個(gè)參數(shù)需要指定：Eps,MinPts不適用于高維數(shù)據(jù)聚類(lèi)：高維空間中數(shù)據(jù)較低維空間中數(shù)據(jù)分布要稀疏，其中數(shù)據(jù)間距離幾乎相等是普遍現(xiàn)象對(duì)于低維數(shù)據(jù)效果較好局限:聚類(lèi)結(jié)果評(píng)測(cè)如何評(píng)判聚類(lèi)結(jié)果的好壞？?jī)梢桓睋淇伺频木垲?lèi)？有幾種聚類(lèi)結(jié)果？聚類(lèi)結(jié)果評(píng)測(cè)用于評(píng)測(cè)聚類(lèi)結(jié)果是否足夠“好”怎樣定義足夠“好”和“足夠相似”？評(píng)測(cè)過(guò)程具有主觀性聚類(lèi)結(jié)果評(píng)測(cè)方法用戶驗(yàn)證InternalClusterValidation不知道真實(shí)類(lèi)別標(biāo)簽ExternalClusterValidation知道真實(shí)類(lèi)別標(biāo)簽，將聚類(lèi)結(jié)果與真實(shí)類(lèi)別對(duì)比InternalClusterValidation測(cè)量聚類(lèi)結(jié)果的兩個(gè)方面:Cohesion:類(lèi)內(nèi)數(shù)據(jù)之間的相似度盡量大Separation:類(lèi)間數(shù)據(jù)盡量不同.多種internalvalidationmeasures兩個(gè)示例:ExternalClusterValidation將聚類(lèi)結(jié)果與真實(shí)類(lèi)別標(biāo)簽對(duì)比.EntropyPurityF-measurePartitioncoefficientValidationofinformationV-measure好的聚類(lèi)結(jié)果應(yīng)該是：聚類(lèi)結(jié)果中的每一類(lèi)都只包含原始數(shù)據(jù)中的一種數(shù)據(jù)C1C2C3C1+

C2+

C3+

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

C2+

C3+

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

C2+

C3+

數(shù)據(jù)挖掘的發(fā)展方向Web應(yīng)用數(shù)據(jù)流處理以及針對(duì)易丟失數(shù)據(jù)等特殊情況的專(zhuān)用處理方法大規(guī)模高維數(shù)據(jù)集的聚類(lèi)方法信息搜索技術(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