资源描述：
《基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
学校代号10532学号S151000916分类号TP311密级硕士学位论文基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究学位申请人姓名陈晓菲培养单位信息科学与工程学院导师姓名及职称常炳国副教授学科专业软件工程研究方向数据挖掘论文提交日期2018年5月8日 学校代号：10532学号：S151000916密级：湖南大学硕士学位论文基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究学位申请人姓名：陈晓菲导师姓名及职称：常炳国副教授培养单位：信息科学与工程学院专业名称：软件工程论文提交日期：2018年5月8日论文答辩日期：2018年5月22日答辩委员会主席：秦拯教授 StudyonTextMiningAlgorithmforUltrasoundExaminationofChronicLiverDiseasesBasedonSpectralClusteringbyCHENXiaofeiB.E.(NorthMinzuUniversity)2015AthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringinSoftwareEngineeringintheGraduateSchoolofHunanUniversitySupervisorAssociateProfessorChangBingguoMay,2018 学位论文原创性声明和版权使用授权书湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研宄做出重要贡献２的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：崎曰期：剔２年５月４曰学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于１、保密□，在年解密后适用本授权书。２、不保密Ｍ。“”（请在以上相应方框内打Ｖ）作者签名：陈日期：从卩年Ｓ月乂日导师签名：日期：年ｉｒ月Ｗ日 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究摘要超声波检查是通过弱超声波仪器照射病灶，将病灶组织的反射波(echo)生成图像并处理，医生读取超声检查影像形成报告文本。超声检查影像受呼吸的干扰小，因此超声检查对慢性肝病的诊断准确率较高。近年来，我国慢性肝病患者不断增多，已积累了大量的超声检查报告文本。论文采用改进谱聚类算法，对具有高维数据特征的超声检查报告文本进行聚类分析，挖掘超声检查报告文本中潜在的价值，为慢性肝病的预测和诊断提供技术支持。主要工作如下：1.论文分析了谱聚类算法中聚类数难以确定，以至于聚类效率较低的特点，分别运用肘方法和轮廓系数法求得两个聚类数K值，作为确定聚类数取值区间。论文在搜狗新闻中文语料库上选取了12类1200条实际文本数据，验证了实际聚类数在论文计算所得取值区间内。论文比较研究了谱聚类和k-means算法的聚类效果，结果显示谱聚类算法得到的Rand指数比k-means算法提高了11.34%，Jaccard指数比k-means算法提高了14.67%；2.论文选择了110份真实慢性肝病患者的超声波检查报告文本，经过文本预处理后，运用上述算法。选定Calinsky准则为聚类的有效性指标，确定最优聚类数K值为5。论文制作高频词云图，分析得出了5种类型超声报告出现的高频词与诊断结果的关联关系，为提高慢性肝病超声检查诊断的准确率提供支持。论文对谱聚类算法进行了部分改进，提出了较为准确地定义聚类数的实现方法，通过实际慢性肝病超声检查报告应用样本，验证了论文改进算法的有效性，具有一定的实践应用价值。关键词：慢性肝病；谱聚类；机械学习；文本挖掘；超声检查II 硕士学位论文AbstractUltrasoundexaminationistoirradiatethelesionwithaweakultrasonicinstrument,generatetheimageoftheechoofthelesiontissueandprocessit,andthedoctorreadstheultrasonicexaminationimageformationreporttext.Ultrasoundimagesarelesslikelytobedisturbedbyrespiration,sothediagnosticaccuracyofultrasonographyforchronicliverdiseaseishigh.Inrecentyears,thenumberofpatientswithchronicliverdiseaseinChinahasbeenincreasing,andalargenumberofultrasoundexaminationreporttextshavebeenaccumulated.Thepaperadoptsanimprovedspectralclusteringalgorithmtoclustertheultrasoundexaminationreporttextswithhigh-dimensionaldatafeatures,andminesthepotentialvalueoftheultrasoundexaminationreporttextstoprovidetechnicalsupportforthepredictionanddiagnosisofchronicliverdiseases.Themainworkisasfollows:1.Thispaperanalyzesthecharacteristicsofspectralclusteringalgorithmwhichisdifficulttodeterminethenumberofclusters,andthustheclusteringefficiencyislow.ThetwoclusteringnumbersKvaluesareobtainedbyusingtheelbowmethodandthecontourcoefficientmethodrespectively,whichareusedtodeterminethenumberofclusters.Valueinterval.Thepaperselects12typesof1200actualtextdataontheSogouNewsChinesecorpus,andverifiesthattheactualnumberofclustersiswithinthevalueintervalcalculatedbythepaper.Thepapercomparestheclusteringeffectofspectralclusteringandk-meansalgorithm.TheresultsshowthattheRandindexobtainedbythespectralclusteringalgorithmis11.34%higherthanthek-meansalgorithm,andtheJaccardindexisincreasedby14.67%comparedwiththek-meansalgorithm.2.Thepaperselected110ultrasoundexaminationreporttextsofpatientswithrealchronicliverdisease.Aftertextpreprocessing,theabovealgorithmwasused.TheselectedCalinskycriterionistheeffectivenessindexoftheclusterandtheoptimalclusternumberKisdeterminedtobe5.Thepaperproducedhigh-frequencywordcloudmaps,andanalyzedtherelationshipbetweenhigh-frequencywordsanddiagnosticresultsofthefivetypesofultrasoundreports,andprovidedsupportforimprovingtheaccuracyofultrasounddiagnosisofchronicliverdiseases.III 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究Inthispaper,thespectralclusteringalgorithmispartiallyimproved,andamethodforaccuratelydefiningthenumberofclustersisproposed.Throughtheactualapplicationofchronicliverdiseaseultrasoundreportsamples,thevalidityoftheimprovedalgorithmofthepaperisverified,andithascertainpracticalapplicationvalue.Keywords:Chronicliverdisease;Spectralclustering;Mechanicallearning;Textmining;UltrasonographyIV 硕士学位论文目录学位论文原创性声明..................................................................................................I学位论文版权使用授权书..........................................................................................I摘要........................................................................................................................IIAbstract....................................................................................................................III插图索引.................................................................................................................VII附表索引................................................................................................................VIII第一章绪论...............................................................................................................11.1研究背景及意义...........................................................................................11.2国内外研究现状...........................................................................................21.2.1国外研究现状........................................................................................21.2.2国内研究现状........................................................................................41.3本文研究内容...............................................................................................51.4论文组织框架...............................................................................................5第二章文本聚类关键技术........................................................................................72.1聚类分析......................................................................................................72.2文本预处理...................................................................................................82.2.1文本分词................................................................................................82.2.2去除停用词............................................................................................82.3文本表示模型.............................................................................................92.4文本特征选择.............................................................................................102.5文本聚类方法.............................................................................................112.5.1划分方法..............................................................................................112.5.2层次方法..............................................................................................122.5.3基于密度的方法..................................................................................122.5.4基于网格的方法...................................................................................132.6谱聚类基础.................................................................................................132.6.1谱聚类概述..........................................................................................132.6.2无向权重图..........................................................................................132.6.3相似矩阵..............................................................................................142.6.4拉普拉斯矩阵......................................................................................152.6.5切图聚类..............................................................................................16V 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究2.7聚类效果评价指标.....................................................................................192.8本章小结....................................................................................................20第三章改进的谱聚类算法......................................................................................213.1谱聚类算法.................................................................................................213.2确定K值的谱聚类算法.............................................................................223.2.1确定聚类数目K..................................................................................223.2.2肘方法..................................................................................................223.2.3轮廓系数..............................................................................................233.3.4算法分析与流程...................................................................................243.4验证实验....................................................................................................263.4.1文本预处理过程...................................................................................263.4.2确定K值.............................................................................................273.4.3实验结果..............................................................................................293.5本章小结....................................................................................................29第四章谱聚类算法在医学上的应用.......................................................................304.1实验环境及流程..........................................................................................304.2数据集.........................................................................................................304.3文本预处理.................................................................................................324.3.1去噪处理...............................................................................................334.3.2文本分词...............................................................................................334.3.3建立文档-词条关系矩阵.....................................................................344.4算法应用....................................................................................................344.4.1计算拉普拉斯矩阵..............................................................................344.4.2确定聚类数目K值.............................................................................354.5结果分析....................................................................................................384.6本章小结....................................................................................................41结论...........................................................................................................................42参考文献...................................................................................................................44附录A攻读学位期间主要研究成果.......................................................................48致谢.......................................................................................................................49VI 硕士学位论文插图索引图2.1文本聚类流程图.....................................................................................8图2.2无向权重图切图问题...........................................................................16图3.1确定k值范围图...................................................................................24图3.2轮廓系数与K值关系图.......................................................................28图3.3手肘图..................................................................................................28图4.1实验流程图...........................................................................................30图4.2数据导入图...........................................................................................32图4.3分词结果图...........................................................................................33图4.4聚类值K与SSE值关系图..................................................................36图4.5轮廓系数与K关系图...........................................................................37图4.6不同k值对应的Calinsky指标............................................................38图4.75种类的高频词云图……………………………………………………....39图4.8不同词条间对应的二维平面的聚类情况............................................40VII 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究附表索引表3.1文本测试集............................................................................................26表3.2分词结果表............................................................................................26表3.3部分停用词表........................................................................................27表3.4文本集二种聚类算法结果对比.............................................................29表4.1数据集形式…………………………………………………………………42表4.2聚类数小于10时SSE值......................................................................35表4.3K的取值范围表....................................................................................37VIII 硕士学位论文第一章绪论1.1研究背景及意义大数据应用使得各行各业发生了日新月异的变化。借助计算机机器学习挖掘隐藏的有价值的知识，提高了数据的利用率和价值。医疗大数据包括病人交谈记[1]录、检查报告、生化检验过程生成的海量文本、图片等结构化、非结构化数据。文本挖掘从半结构化和非结构化的生物医学文本中提取知识，在这些文本隐藏着的信息中很可能含有极具价值的知识。现在它在生物学中被广泛使用，例如[2][3][4][5]医学研究生物医学实体识别、药物发现、靶标选择、识别药物副作用、预[6]测蛋白质交互作用等方面。医学知识组织系统的使用，帮助人们获得新的知识[7]及其相关能力，将概念标准化、发现和推理关系、组织知识顺序化。随着移动互联网、云计算、数据挖掘等技术的不断使用，社会逐渐走入了大数据的时代，医院也进入了大数据医疗。医疗大数据的开始相对较晚，其发展比较迅速。根据医疗数据具有的异构性、海量性、数学表征不显著、主观性、标准化危机、法律性这些特点，在医疗领域里数据挖掘运用广泛。常用的挖掘模式有——频繁模式、聚类分析、离群点分析等。常用的算法有神经网络算法、决策树以及关联规则。人工神经网络算法在医药领域运用广泛。它依靠模仿生物神经网络的运作而逐渐发展，层层构建。医药数据有不确定、不完全、不精准等特性。神经网络运用医药数据时，具有良好的容错性、鲁棒性以及高精度。它符合医药挖掘模型的精确性需要。利用CRF模型和LSTM模型在医疗领域的语料上实验，证明与双向[8]LSTM模型与CRF模型的效果相比仍有一定的提升。建立了邻域粗糙集融合贝[9]叶斯神经网络的组合医疗决策模型，提升医疗决策的效率和有效性。决策树是一种简单常用的分类器，该算法从特征入手，根据特征进行分类。每次选择其中一个特征对样本集进行分类，对分类后的子集自上而下不断采取上述步骤。计算信息增益，如果增益够大，将分割后的样本集作为决策树的子节点，否则停止分割。决策树易于理解，与医生的思考方式类似，因此普遍使用。运用[10]较多的决策树算法有：ID3（Iterativedichotamizerversion3）算法、C4.5算[11]法。肺癌诊断的数据为实验文本，采用基于属性依赖改进的可分辨矩阵属性约简的C4．5算法，快速提取有用的医疗价值。1 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究关联就词的本意来说指的是万事万物之间的联系，在计算机领域里是指变量间的取值存在某种规律以及隐藏的关系。关联规则算法出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。由频集产生强关联规则，这些规则必须达到最小可信度与最小支持度的要求。然后使用找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项。最常用[12]的是Apriori算法。它分为频繁模式和分类模式。以关键词和关联规则为基础的规则生成算法，以及基于本体的抽取算法，自动构建健康知识库。基于动态训练集选择和基于关联规则属性约减的TAN方法辅助医疗诊断领域，帮助医生在较短的时间内，利用较少的信息为患者进行疾病诊断。聚类分析作为当今数据挖掘领域有效手段，是聚类分析一个重要的研究热门。为人们探索大自然万事万物的联系提供了新的方法。谱聚类算法的优点在于，该方法不但思想简单，易于实现，并且可以辨别具有非凸分布的聚类，改进局部最优解，收敛于全局最优解，非常适合许多实际的应用。1.2国内外研究现状1.2.1国外研究现状国外的研究现状，分医疗文本和聚类技术两个方面阐述。(1)在国外生物医疗领域中，数据挖掘的信息数据来源大多的都来自于MEDLINE数据库。MEDLINE数据库是一种有价值的资源，可以让科学家基于关键字搜索检索文章。这个基于查询的信息检索是非常有用，但它只允许在生物摘要对可用的知识进行检索利用。它是由美国国家医学图书馆制作的，涉及的内容包括临床医学、健康服务管理、护理、毒理学、营养学、药学、实验医学、精神病学、病理学等，文献数量在800万篇以上，存储量占整个MEDLARS系统50%以上，是MEDLARS系统的首选数据库。2001年，欧洲生物信息学中心（EBI）的Iliopulos等人将每篇文档表示为一个由多个词项频度构成的向量，采用经典的向量空间模型开发的TextQuest生物[13][14]医学文本聚类系统。日本东京大学的Yamamoto等采用摘要和标题中的内容[15]信息来进行聚类，开发乐名为McSyBi的生物医学文献聚类系统。Zhu等人将MeSh主题词加入到文本聚类中，聚类效果不错。通过利用FACTA生物医药文本挖掘工具，从MEDLINE的文章中为每种风湿病提取症状频率，通过创建数据集，[16]应用聚类分析来判断疾病中共有的且最为特别的症状。[17]在医疗保健方面，GuerganaKSavova等人开发了一个整体医疗保健分析系统叫做GEMINI（“GeneralizableMedicalInformationAnalysisandIntegrationSystem）。系统以两类人为目标：一种是为医院正常运行管理临床数据的管理员；2 硕士学位论文一种是为了管理病患的临床关怀，需要查询数据的医学专家，例如，列出单个医生负责的在院患感染病的病患，列出所有正在接受beta-受体阻滞药治疗的病人。还有，预测病患在近将来得心脏病的风险或者出院后30天内重新入院的风险。该系统由两部分组成：资料框架模块和分析模块。在资料框架模块部分从各种各患者的数据源提取数据并将它们存储为在患者个人资料图中。数据源包括结构化数据，例如，病人的基本资料（例如，年龄，性别等）、检验结果（例如，HbA1c值）、药物和非结构化数据（例如含有医生的说明的自由文本）。该患者个人资料图提供了一个全面统一的病人的临床资料视图，这简化了管理员和医疗保健专家的工作。分析模块组件分析患者个人资料图来推断隐含信息并且为预测任务提取相关特征。文献[18]以网上的医疗论坛的文本信息为挖掘内容，提出了一种端到端的文本挖掘方法，提早发现不良药物反应。该方法有三个主要特征，分别是，基于头驱动短语结构语法解析器、特定领域关系模型以及自动化的后处理算法。该方法可以先于药物管理局发现不良药物反应。文献[19]确定一组语法规则被用于判断病历报告是否符合医学条件。将该语法规则用于新的病历报告，该语法规则至少执行特征选择的步骤而被事先确定，并被用于确定一整组的语法规则。这些技术可以通过程序产品执行。(2)在聚类技术方面，在国外60年代后期，电子文本信息的大量积累迎来了新的信息检索技术的挑战。为了利用各种来源的自由文本信息，出现了很多信息检索的方法。在《InformationRetrieval》这本书中叙述了使用文本聚类分析技术提高信息检索的准确性。然而，在当时其他条件的影响下，文本聚类技术在20世纪90年代才取得重大进展。文本聚类可分为基于划分、基于层次、基于密度、基于网格的多种文本聚类算法。每种类型的聚类算法又衍生出许多新的改进的聚类算法。最著名的是k-means算法。Yahoo搜索引擎使用k-means算法进行文档整理归类。RatioCut[20]算法是谱聚类算法中比较重要的一环，主要解决谱聚类中图最小划分的问题，以期达到最佳划分。由于谱聚类算法在处理复杂的样本数据具有更优的聚类效果，[21][22][23][24]具有广泛的应用前景，如计算机视觉、文本摘要、语音识别和文本挖掘等领域。谱聚类算法发展还有改进的地方，存在确定聚类个数、构造相似矩阵、确定特征向量等标准有待规范，还需国内外学者的进一步探索。3 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究1.2.2国内研究现状在国内，“互联网+医疗”的研究与应用在互联网技术的推动下，我国医疗事业迅速发展。在“大数据+”的大环境下,人们开始研究将数据挖掘技术更好的应用于医疗数据分析上。现阶段医疗大数据的主要应用有以下几个方面：(1)临床数据研究。临床数据研究主要是利用电子病历、医学影像数据，依靠方法学工具进行问题驱动的数据解读。由于医学文本的数据结构和文字处理方法无法量化，因此构建了基于潜在语义树的医学文本数据挖掘的语义分析模型，[25]效果不错。为了实现计算机辅助诊断中类似病例发现这一功能，将文本和医学图像视为各种形式的相互补偿信息，用这两种信息分别构建图模型，构建多图融合框架，然后对融合图进行多重排序并以确定最终结果。在乳腺X线影像数据库和肺部CT影像数据库上的实验结果表明，该算法在病例检索方面具有更好的搜[26]索效率。文献[27]运用一种改进的相似性算法，解决疾病诊断报告中同义词识别。根据这种新的自动识别类个数的相似性度量算法，聚类实现同义文本识别。之后合并和优化类别数，精确实验结果。对原始的健康管理类APP数据采用相应的运算方法提取信息后，进行两步清洗，以通过特定的数据管理和统计分析方法[28]处理移动医疗健康管理类APP纵向大数据，供科学研究。文献[29]识别中医文本的评论语句并进行情感计算，并实验验证了其有效性。(2)临床辅助诊断。使用一种面向自然语言文本的电子病历文档关键信息提[30]取算法，帮助医生解读复杂医疗病历中的核心信息。针对常见的5类疾病:胃炎、肺癌、哮喘、高血压和糖尿病,采用机器学习模型条件随机场，使用逐一添加特征[31]的方式，验证所提特征的有效性，取得较高的准确率。文献[32]以儿童先天性心脏病超声心动检查报告中的文字描述信息为挖掘文本，运用决策树算法推导医师解读心脏超声报告的决策路径，分析与临床风险评估结果的相关性，为医师诊疗决策提供依据。[33](3)健康管理。为了提高全民健康指数，建立相应的系统。健康医疗大数据平台在对慢病患者、慢病高危人群、健康个体进行健康医疗数据收集和监测的基础上，通过深度学习、数据挖掘、云计算等技术建立慢病预测分析模型，可对导致慢病发生的高危因素进行定位，对健康个体给予健康管理相关指导，对高危人群进行健康危险评估和预警并引导其进行有效的干预，对慢病患者进行个性化[34]治疗与预后跟踪监测。(4)管理决策。利用医疗健康大数据进行管理、制定决策成为必然趋势。在提高管理效率方面，使用全文索引技术来索引与医学文本数据相关的关键字，运用[35]基于余弦公式与全文索引技术的医学文本相似度分析算法，提高检索性能。4 硕士学位论文1.3本文研究内容本文介绍谱聚类算法的基础理论后，针对聚类个数难以确定这一问题,采用轮廓系数和肘方法确定聚类数范围改进谱聚类算法。通过对比实现说明改进后的谱聚类算法下在聚类效果上具有良好表现。将改进后的聚类算法应用到慢性肝病的超声波检查报告。研究内容主要有以下三点。（1）对慢性肝病超声波检查报告的预处理工作。本文选择符合条件的样本数据，通过对慢性肝病超声波检查报告的分析，在计算样本间相似度之前，先对其进行预处理工作，这样在一定程度上提高了数据的质量。（2）谱聚类算法中k值的确定。本文通过对谱聚类算法热点问题的分析，从k值的确定着手，利用肘方法和轮廓系数，提出了一个确定k值范围的方法，对k值的选取具有一定的参考价值。（3）本文把改进后的谱聚类算法应用到慢性肝病的超声波检查报告上，分析每种类型超声报告出现高频词与诊断结果关系，为提高诊断率提供支持。通过分析聚类结果可知，每个类是一个小型的病例网，将该类中医治成功率高的医生推荐给该类中其他未被治疗的病人，也可以给病人带来便利，提供更好的服务。1.4论文组织框架本文主要内容是在介绍课题的研究意义背景以及基础技术后，提出一种确定聚类数范围的方式，并在数据集上进行验证。针对慢性肝病超声波检查报告这一特殊文本信息的进行数据挖掘，分析其价值。论文分为五章，具体内容安排如下。第1章。绪论。本章叙述课题的背景及意义、国内外研究现状这几节来阐述，介绍了论文的主体内容以及结构。第2章。这一章介绍了文本聚类的流程，主要是预处理、文本表示模型、常见的聚类方法等，阐述了与本文密切相关的谱聚类算法基础以及聚类效果评价指标，为之后的实验提供理论支持。第3章。利用肘方法和轮廓系数得到k1和k2两个参考来确定k值范围，再选一个聚类有效性指标，通过聚类结果得到最佳聚类指标对应的k值即最佳k值。最后在搜狗新闻中文语料库进行了验证。第4章。首先对慢性肝病超声波文本数据进行了分析以及处理，利用第四章提出的方法进行实验，针对最终的结果，分析聚类结果的价值。5 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究第5章。总结与展望。对谱聚类算法的研究和对算法的改进进行总结，提出了一些待改进的地方，并且展望未来对算法的改进几个关键点。并对论文中需要进一步研究的问题进行阐述。6 硕士学位论文第二章文本聚类关键技术2.1聚类分析聚类分析简称聚类，就是将大量的数据划分成簇的过程。在这些簇中，相似度比较高的对象被分在同一簇，不同簇样本之间的对象相似度比较低，这对挖掘数据内部结构信息具有非常重要的作用和意义。由聚类分析产生的簇的集合称作为一个聚类。在这种情况下，相同的数据集在不同的聚类方法下可能产生不同的聚类。如果给定一个对象集合Xxx,,,x，假设每个对象x具有m个特12ni征，用向量的方式来表示对象的特征，xll,,,l，k为聚类的结果数，im12k那么聚类结果就应该满足下面的条件：c,i1,...;kcX;ii1icc,iji,1,...,kj1,...k。ij数据聚类正在蓬勃发展，由于数据库中搜集了大量的数据，数据挖掘日益热[36]门，其典型要求如下：1）可伸缩性：许多算法适用于小于数百个数据对象的小数据集，但大型数据库可能包含数百万甚至数十亿个对象，在运用算法时就可能出现诸多问题。因此，需要具有适应性广的聚类方法。2）发现任意形状的簇：许多聚类算法基于欧几里德度量等距离计算方式来确定簇。基于这些距离度量的算法倾向于发现具有尺寸和密度大小相似的球形集群。然而，集群可能是任意形状的。3）对于输入参数的确定：聚类结果对于特定领域的输入参数十分敏感。这些参数很难确定，对于高维数据集和用户尚未深入理解的数据来说更是如此。特定领域知识使聚类的质量难以把握。4）聚类高维数据的能力：在文档聚类时，每个关键字都可以看作是一个维，并且常常有数以千计的关键词。在数据稀疏并且高度倾斜时，发现高维空间中数据对象的簇对许多聚类算法是一个挑战。5）可解释性和可用性：聚类可能需要与特定的语义解释和应用程序相关联。重要的是研究应用目标如何影响聚类特征和聚类方法的选择。所谓文本聚类，就是将相似的文本聚集在一起，而将不相似的文本划分到不同的类别的过程，是文本分析之中十分重要的一种手段。通过聚类，将世界上纷繁复杂的信息，简化为少数方便人们理解的类别，是人类认知这个世界的最基本7 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究方式之一。聚类是无监督的过程，聚类的文本集不用经过训练操作，也不用预先标注数据类别，如此造就了文本聚类的多变性。流程如图2.1所示。预处理文本集分词去停用词提取特征聚类结果评构建文本模聚类结果聚类分析价型图2.1文本聚类流程图2.2文本预处理2.2.1文本分词一个词，表达语义的基本单位，用来表征语料的含义。在中文里，单词之间没有空格，单词本身没有明显的形态标记。分词结果会间接影响聚类的性能。中[37]文分词根据实现原理和特点，分词技术分如下2个类别。(1)基于词典分词算法。也称为机械分割法或字符串匹配分词算法。此算法是按照一定的策略将待匹配的字符串和一个已建立好的足够大的词典中的词进行匹配，若找到某个词条，则说明匹配成功，识别了该词。根据前进方向将其划分为正向、逆向和双向匹配。根据匹配策略划分单词以匹配最大值和最小值之间的匹配。优点是分割速度快，缺点是精度低且不能进行歧义分割。(2)基于统计的机器学习算法。常用的是算法是HMM、CRF、SVM、深度学习等算法。随着深度学习的兴起，也出现了基于神经网络的分词器。其基本思想是将文本中的上下文转化成数理逻辑。在统计词组方面，使用贝叶斯来计算共现概率。公式表示为P(a|b)=P(b|a)P(a)/P(b)，但通常采用其互信息熵MI(a，b)=logP(a，b)/P(a)*P(b)进行计算。基于统计的分词技术计算概率进行分词，可能导致误拆词组。2.2.2去除停用词停用词来源于英文单词stopwords。大致分为功能词和应用十分广泛的词。功能词例如：“在”、“的”、“一些”等。应用十分广泛的词指的是在数据文本中都存在的一些词，例如网页文本数据中“网站”一词。停用词一般对文本实8 硕士学位论文[38]现聚类贡献不大，不能表征文本的特征。从文本降维的要求来看，适当的减少停用词出现的频率，降低文本维数，提高聚类效果。常见的停用词表有哈尔滨工业大学停用词词库、百度停用词表等。目前没有完全自动一步到位的实现，更常见的做法是根据自己数据特点，以常见的停用词表为基础，建立专属的停用词表。去停用词的步骤如下：先将文本进行分词处理，再建立停用词表，检查分词后的词汇中是否含有停用词，如果存在，则在分完词的文本中删除该词，否则保留该词。目前常用停用词表建立方式有，崔彩霞结合语言知识提出的一种停用词[39]选取方法，将句子作为一个考虑因素，计算包含特定词语的句子的发生概率以[40]该句子在语料库中的发生概率，计算其联合熵，由此选用停用词。2.3文本表示模型文本信息是机器无法识别的非结构化对象，为了使计算机能够真正处理文本特征，必须对文本特征进行特征加权。只有将原始文本表示成机器能运算处理的数值数据，这一点必须依赖于文本表示模型。[41][42]常用的文本表示模型有向量空间模型、布尔模型、概率模型和语义模型[43]、图空间模型等。例如：布尔模型由于属于基于特征的严密匹配模型，它可以看作是向量模型的一种特例，根据特征是否在文档中出现，特征的权值只能取[44]或。由于进一步减小语义信息方面损失的需要，图空间模型逐渐发展。例如使用二维视图方法，将特征的信息用二维平面的局部能量和全局能量表示，还有后缀树模型等。[45]向量空间模型的常用方法为词频-逆文档频率方法。使用TF-IDF公式，计算得到对应的TF-IDF值，定义为：假定d篇文档，由n个单词构成；t是第jij个单词在文档i中出现的次数，即词频TF(Termfrequency,TF)；a是矩阵的元素ij点；d是出现第j个单词的文档数目，n代表文档数目。则有jtdija=lg.ijnd2jtijj=1(2.1)其中，用TF和IDF(inversedocumentfrequency)的乘积来描述单词的权值。根据公式可以得知，某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率产生高权重的TF-IDF值，常用词的词权将被给予较小的值。9 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究2.4文本特征选择经过前面的预处理过程，得到的文本特征一般都是词集合，具有语义信息。在文本特征选择中，根据分词结果，维数有时高达数万维。这些数万维的词不一定都有用，文本特征选择由此显得特别重要。根据评估准则得到各个词的权重，根据权重大小选择特征词。常用的文本特征提取方法有有文档频率、信息增益、[46]卡方统计量、互信息等。（1）基于文档频率的特征提取方法概念：DF（documentfrequency）指出现某个特征项的文档的频率。步骤1：在语料库中统计包含某个词的文档个数，并计算频率。步骤2：根据预先输入的最大或最小阈值，当该词的文档频率值小于阈值时，去掉该词。因为没有代表性，在该词的文档频率值大于最大阈值时，去掉该词。因为这个特征使文档出现的频率太高，没有区分度。优点：降低向量计算的复杂度，去掉部分噪声，提高分类的准确率，且简单易行。缺点：对于出现频率低但包含较多信息的特征，对分类很重要，去掉会降低准确率。（2）IG——信息增益概念：IG（InformationGain）根据某特征项t(i)能为整个分类提供的信息量来很衡量该特征的重要程度，来决定对该特征的取舍。一般而言，就是有这个特征和没有这个特征对整个分类能提供的信息量的差别。信息量一般用熵来衡量。所以一个特征的信息增益为不考虑任何特征时文档所含的熵减去考虑该特征后文档的熵。具体公式如下：mmPck(|)Pck(|)iiIGk()Pk()pck(|)*logiiPk()pck(|)*logii11pc()iipc()(2.2)P(k)表示含特征词k的文本的概率；pc()是在属于簇c文本的概率；m为簇ii的个数。Pck(|)是含特征值k并且属于簇c的文本的条件概率；pck(|)与Pck(|)iiii相反，是不包含特征值k并且属于簇c的文本的条件概率。i步骤1：计算不含任何特征整个文档的熵步骤2：计算包含该特征的文档的熵步骤3：前者-后者优点：准确率较高，因为你选择的特征是对分类有用的特征。缺点：实际情况里，有些信息增益较高的特征出现的频率较低。（3）CHI——卡方统计量10 硕士学位论文概念：卡方统计量的中心思想为“假设检验”。如果与卡方统计量相关联的p值小于选定的a水平，检验将拒绝两个变量彼此独立的原假设。CHI衡量的是特征项t(i)和C(j)之间的相关联程度。如果特征对于某类的卡方统计值越高，相关性越大，携带的信息越多，繁殖则越少。步骤：方法1：计算特征对每个类别的CHI值，在整个语料上分贝找每个类别的最大的值，把这个值设置为阈值，低于阈值的，则删除。方法2：计算个特征对于各类别的平均值，以这个平均值作为各类别的CHI值。缺点：会对低频词有所偏袒(4)MI——互信息法概念：MI（mutualinformation）指互信息，越大，则特征t(i)和C(j)之间共同出现的程度越大，如果两者无关，那么互信息=0。步骤：两种方法，和CHI一样，最大值方法和平均值法优点：选择稀有词作为文本的最佳特征，稀有词的互信息值高。缺点：受词条边缘概率的影响，选词有时不准。2.5文本聚类方法特征词集经过文本特征选择后，会形成结构化数值数据。这种数值形式数据会成为之后算法的输入。由于聚类算法的蓬勃发展，现有的聚类算法多种多样。可根据聚类目的、实际问题选择特定算法。常用的聚类算法有：划分方法、层次[47]方法、基于密度的聚类方法、基于网格的聚类方法等，以下分别阐述。2.5.1划分方法给定n个数据点的数据集合，构建数据集合的出K个划分，每个划分表示一种类，21）单元c至少有I个点，[52]仅当c的每个（k-1）-维投影（它是（k-1）-维单元）至少有1个点。算法需要两个参数：一个是网格的步长，确定空间的划分；第二个是密度的阈值用来定义密集网格。算法的基本思想：首先判断是不是密集网格，如果是密集网格。那么对其相邻的网格进行遍历，看是否是密集网格，如果是的话，那么属于同一个簇。CLIQUE算法整个聚类过程是非常高效的。反之，对于高维数据，CLIQUE算法容易表现很差。2.6谱聚类基础2.6.1谱聚类概述谱聚类（SpectralClustering）主要思想是把所有的数据看做空间中的点，点之间用边连接起来。距离近的点之间权重高，距离远的点之间权重低，由此得到带权无向图。源自于谱图划分，对所有数据点组成的图切图。理想结果是，切图[53]后不同的子图间边权重和低，而子图内的边权重和高，以此达到聚类的目的。2.6.2无向权重图由于谱聚类是基于图论的，因此先介绍图的概念。对于一个图G，一般用点的集合V和边的集合E来描述。即为G=(V,E)。其中V即为数据集里面所有的点13 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究{,,...,}vvv。对于V中的任意两个点，可以有边连接，也可以没有边连接。定12n义权重w为点v和点v之间的权重。由于是无向图，所以ww。ijijijji对于有边连接的两个点v和v，w0,对于没有边连接的两个点v和v，ijijijw=0。当v和v相距较近的时候，w用较大的值表示；当v和v相距较远的时ijijijij候，w用较小的值的表示。其中对于任意i，w1。对于图中的任意一个点v，ijiii它的度d定义为和它相连的所有边的权重之和，即indwiij（2.2）j1利用每个点度的定义，可以得到一个nn的度矩阵D,它是一个对角矩阵，只有主对角线有值，对应第i行的第i个点的度数，定义如下：d......1...d2...D（2.3）......dn利用所有点之间的权重值，得到图的邻接矩阵W。它是一个nn的矩阵，第i行的第j个值对应的权重w。ij除此之外，对于点集V的一个子集A⊂V，定义：|A|:=子集A中点的个数volA():di（2.4）iA2.6.3相似矩阵基本思想是，距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高。可以通过样本点距离度量的相似矩阵S来获得邻接矩阵W。构建邻接矩阵W的方法有三类。-邻近法，K邻近法和全连接法。对于-邻近法，它设置了一个距离阈值，然后用欧式距离s度量任意两点ij2x和x的距离。即相似矩阵的sxx，然后根据s和的大小关系，ijijijij2来定义邻接矩阵W如下：0sijW（2.5）ijsij14 硕士学位论文从上式可见，两点间的权重要不就是,要不就是0，没有其他的信息了。距离远近度量很不精确，因此在实际应用中，较少使用-邻近法。第二种定义邻接矩阵W的方法是KNN算法。在遍历所有的样本点后，取每个样本最近的k个点作为近邻，只有和样本距离最近的k个点之间的w0。为了ij解决重构之后的邻接矩阵W非对称问题，采取下面两种方法之一：第一种K邻近法是只要一个点在另一个点的K近邻中，则保留s。ij0xKNNx()andxKNNx()ijji2WWxx（2.6）ijjiij2exp()xKNNx()orxKNNx()2ijji2第二种K邻近法是必须两个点互为K近邻中，才能保留s。ij0xKNNx()orxKNNx()ijji2WWxx（2.7）ijjiij2exp()xKNNx()andxKNNx()2ijji2第三种定义邻接矩阵W的方法是全连接法。全连接法使所有的点之间的权重值都大于0。选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的是高斯核函数RBF，此时相似矩阵和邻接矩阵相同。实际应用中这种方式最常用，在这种方式下，使用高斯径向核RBF是最普遍，公式如下：2xxij2WSexp()（2.8）ijji222.6.4拉普拉斯矩阵后面的算法和这个拉普拉斯矩阵(GraphLaplacians)的性质息息相关。拉普拉斯矩阵定义很简单，LDW。D即为度矩阵，它是一个对角矩阵。而W即为邻接矩阵。拉普拉斯矩阵有一些很好的性质如下：1）拉普拉斯矩阵是对称矩阵，这可以由D和W都是对称矩阵而得。2）由于拉普拉斯矩阵是对称矩阵，则它的所有的特征值都是实数。3）对于任意的向量f,有nT12fLfwij()fifj（2.9）2ij,115 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究这个利用拉普拉斯矩阵的定义很容易得到如下：nnnnT11222fLf(dfii2wffijijdfjj)wij(fifj)（2.10）22i1ij,1j1ij,14)拉普拉斯矩阵是半正定的，且对应的n个实数特征值都大于等于0，即0=且最小的特征值为0，这个由性质3很容易得出。12n2.6.5切图聚类对于无向图G的切图，的目标是将图GVE(,)切成相互没有连接的k个子图，每个子图点的集合为：，，，，它们满足V。12k12k对于任意两个子图点的集合,,V,定义A和B之间的切图权重为：Ww(,)ij（2.11）ij,那么对于k个子图点的集合：，，，，定义切图cut为：12kk1cut(12，，，k)W(i,i)（2.12）2i1其中为的补集，意为除子集外其他V的子集的并集。iii为了切图可以让子图内的点权重和高，子图间的点权重和低，一个自然的想法就是最小化cut(，，，),但是可以发现，这种极小化的切图存在问题，12k如下图：ABDECFGHSmallestcutBestcut图2.2无向权重图切图问题选择一个权重最小的边缘的点，比如C和H之间进行cut，这样可以最小化cut(，，，),却不是最优的切图。两种方式切图可以用来找到类似图中12k"BestCut"这样的最优切图。第一种称为RatioCut切图，RatioCut切图为了避免的最小切图，对每个切图，不光考虑最小化cut(，，，)，它还同时考虑最大化每个子图点的个数，即：12k16 硕士学位论文1kW(,)iiRatioCut(12，，，k)=（2.13）2i1i最小化RatioCut函数时，引入指示向量hhh,,hj1,2,k,对于jk12任意一个向量h它是一个n维向量（n为样本数），定义h为：jji0vijhji=1（2.14）vijjT那么对于hLh,有：iiT11221hLhii(wmn(0)wmn(0))2miniiimini（2.15）111RatioCut(i,i)(wwmnmn)（2.16）2miniiimini上述第（1）式用了上面第四节的拉普拉斯矩阵的性质3.第二式用到了指示T向量的定义。可以看出，对于某一个子图i，它的RatioCut对应于hLh,那么的kii个子图对应的RatioCut函数表达式为：kkTTTRatioCut(12，，，k)=hLhii(HLH)iitrHLH()（2.17）ii11T其中trHLH()为矩阵的迹。也就是说，的RatioCut切图，实际上就是最小化TT的trHLH()。注意到HHI,则的切图优化目标为：TTargmintrHLHst()..HHI（2.18）HH矩阵里面的每一个指示向量都是n维的，向量中每个变量的取值为0或者1n，就有2n种取值。有k个子图的话就有k个指示向量，共有k2种H。因此i找到满足上面优化目标的H是一个NP难的问题。TT用如下方法解决：观察trHLH()中每一个优化子目标hLh,其中h是单位iiT正交基，L为对称矩阵，此时hLh的最大值为L的最大特征值，最小值是L的ii最小特征值，用维度规约的思想来近似解决这个NP难的问题。17 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究kTTT对于hLhii，的目标是找到最小的L的特征值，而对于trHLH()=hLhii，则i1的目标就是找到k个最小的特征值，一般来说，k远远小于n，也就是说，此时进行了维度规约，将维度从n降到了k，从而近似可以解决这个NP难的问题。通过找到L的最小的k个特征值，可以得到对应的k个特征向量，这k个特征向量组成一个nk维度的矩阵，即为的H。对H矩阵按行做标准化，即h*ijh（2.19）ijk122()hitt1维度规约会丢失少量信息，导致优化后的指示向量h对应的H不能完全指示各样本的归属。因此在得到nk维度的矩阵H后需要对每一行进行聚类，比如使用KNN聚类。[54]Ncut切图和RatioCut切图很类似，但是把RatioCut的分母|Ai|换成vol(Ai).由于子图样本的个数多并不一定权重就大，切图时基于权重也更合的目标，因此一般来说Ncut切图优于RatioCut切图。1kW(,)iiNCut(12，，，k)（2.20）2i1vol(i)1Ncut切图对指示向量h做了改进。Ncut切图使用子图权重标示指vol()j示向量h，定义如下:0vijh1（2.21）jivijvol()jT那么对于hLh,有：iiT111hLh(cut(,)cut(,)iiiiii2vol()vol()（2.22）jj111NCut(,)(cut(,)cut(,)（2.23）iiiiii2vol()vol()jj推导方式和RatioCut完全一致。优化目标仍然是kkTTTNCut(12，，，k)=hLhii(HLH)iitrHLH()（2.24）ii11TT但是此时的HHI,而是HDHI。推导如下：18 硕士学位论文nT211hDhiihdijjwvjvol(i)1（2.25）jv1vol(ii)vol()ji此时的优化目标最终为：TTargmintrHLHst()..HDHI（2.26）H此时H中的指示向量h不是标准正交基，所以在RatioCut里面的降维思想不能直接用，需要将指示向量矩阵H做一个小转化。1/2TT1/21/2TT令HDF,则HLHFDLDF,HDHFFI也就是说优化目标变成了:TT1/21/2argmintrFD(LDFst)..FFI（2.27）F1/21/2这个式子和RatioCut基本一致，只是中间的L变成了DLD。可以继续1/21/2按照RatioCut的思想，求解DLD的前k个特征向量并标准化，得到最后的特征矩阵F。对F进行聚类（比如K-Means）。1/21/2一般来说，DLD相当于对拉普拉斯矩阵L做了一次标准化，即Lij。dd*ij2.7聚类效果评价指标对聚类结果的评价也就是聚类有效性问题。本质是在某数据集上强加一个假设，然后按照这个假设设计聚类算法，并在此数据集进行聚类。聚类分析与分类稍有不同，它不依赖于样本数据是否已知分类结果，它是一种无监督的学习。不需要给出训练样例来指明数据应该具有怎样的关系。并不清楚数据的具体结构，这对来说是未知的。所以对于最终的聚类结果，在理论上，不能通过样本的已知分类情况和聚类结果的分类情况比较来评价聚类算法的优劣。在对数据样本未知的情况下，如何不依赖于如标记类等先验信息，来评价聚类结果是一个很关键的难点问题。到目前未知，虽然不少研究学者提出了一系列聚类有效性的指标，但是这些指标往往都存在各种各样的缺陷，比如说需要有特定的实验环境，在特地的环境中可以很好的对聚类结果进行评价，而在其他环境中得到的评价结果往往效果欠佳。总体来说，通常聚类效果考虑最终聚类结果的两个方面，一个是紧凑性，另一个是耦合性。紧凑性是指同一子类中的所有对象之间的相似程度，如果相似程度越高，则紧凑性越好；而耦合性是指不同子类之间的对象之间相似程度，如果19 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究相似程度越小，则耦合性就越好。群集方差与群集内的最大比率方差或Calinsky准则（CalinskyandHarabasz，1974）：Bk()/(k1)CWk()/(nk)(2.26)其中B（k）是群集之间的平方和，W（k）是一个聚类内的平方和，n是观[55]察数，k是簇的数量。所以Calinskycriterion值越大，聚类效果越好。为了估计已经标记好的文本聚类质量，运用Rand指数和Jaccard系数作为评价标准，通过人为加入分类标识集合g={1,2,…,m}，通过聚类获得的集合C={c1,c2,…,cm}，（xv，xu）表示数据集中任一对数据点。分情况统计计算a,b,c,d四个参数的值。a表示两个数据点是集合g中的同一类，且是集合C中的同一聚类；b表示两个数据点是集合g中的同一类，且不是集合C中的同一聚类；c表示两个数据点不是集合g中的同一类，却是集合C中的同一聚类；d表示两个数据点不是集合g中的同一类，且不是集合C中的同一聚类。a和d表示正确划分的情况，b和c表示出现偏差的情况。M为a、b、c、d之和，表示能组成的最大数据点对数。n表示文本数据集的数目。公式如下：nn(1)M(2.27)2Rand指数计算公式为：adR(2.28)M[56]Jaccard系数计算公式为：aJ=(2.29)abc2.8本章小结本章首先介绍了文本聚类的流程，主要是预处理、文本表示模型、常见的聚类方法等，阐述了与本文密切相关的聚类效果评价指标以及谱聚类算法基础，为之后的实验提供理论支持。20 硕士学位论文第三章改进的谱聚类算法一般谱聚类算法最终都会用到k-means算法。原始K-means算法最开始随机选取数据集中K个点作为聚类中心，对剩下的每个对象，根据每个簇中心的欧式距离，将它分配到最相似的簇。然后，k-means算法迭代地改善簇内方差。对于每个簇，它使用上次迭代分配到该簇的对象，计算新的均值。然后，使用改善后的均值作为下一轮的簇中心，重新分配所有对象。一直迭代到分配趋于稳定的状态。但是实际上，在对无标签文本进行聚类是，聚类数K是很难确定的。3.1谱聚类算法谱聚类算法将数据聚类看作一个定向图的多路分割问题，把每个文本看作是图的顶点，根据文本之间的相似度，把各个顶点之间的连接边赋以权值，得到基于文本相似度的非定向加权图。遵循最优分割原则，划分任意两个子图之间的相似度最小，子图内部相似度最大。把图分割问题转换为Laplacian矩阵的谱分解，得到图谱分割在连续域中的全局最优解。谱聚类算法步骤如下：第1步：计算数据样本的相似度矩阵，以及预先定义的聚类数。第2步：计算拉普拉斯矩阵。第3步：求矩阵Lsym的前k个最大特征值和相应的特征向量v1,v2,…,vk，构n*k造特征向量空间矩阵V={v1,v2,…,vk}∈R第4步：将特征向量空间矩阵的每一行看成是空间内的一点，利用K-means聚类方法将其聚成k类。谱聚类算法相比于KNN、K-means的等聚类算法，处理复杂的样本数据具有更优的聚类效果，具有广泛的应用前景。根据谱聚类算法确定聚类个数、构造相似矩阵、确定特征向量等问题，研究热点如下所示：（1）聚类个数的确定在对无标签数据进行聚类是，由于无法事先预知聚类数，聚类数将直接影响聚类质量。确定最佳聚类数的方法有PAM(PartitioningAroundMedoids)围绕中心点的分割算法、GapStatistic、轮廓系数(Averagesilhouettemethod)等。目前没有出现伸缩性较大确定最佳聚类数目的方法。（2）相似矩阵的构造衡量样本之间的相似度的影响聚类效果的一个关键点。选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的21 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究是高斯核函数RBF。核函数需要一些预先输入一些参数，参数的选取也会影响最终的聚类效果。（3）特征向量的确定一般选定拉普拉斯矩阵的前k个特征向量，但目前尚无充足的理论支持这一做法。特征向量的选取仍需重点关注。(4)在大规模数据集上的运用谱聚类算法中，拉普拉斯矩阵矩特征值分解的计算复杂度是数据对象总数的3次方。这一点限制了谱聚类算法的进一步推进。3.2确定K值的谱聚类算法3.2.1确定聚类数目K除了k-means这样的聚类算法需要簇数，合适的簇数还可以控制适当的聚类分析粒度，确定簇数十分重要。确定簇数并非信手拈来，“正确的”簇数常常琢磨不透。传统确定聚类数目的方法，是根据多次选取不同的k值进行聚类，再选取一个聚类有效性指标，通过聚类结果得到最佳聚类指标对应的k值，再进行聚类。一种简单的经验方法是，对于n个点的数据集，设置簇数k大约为n。在期望情况下，每个簇大约有n个点。具体的过程如下：Step1：确定聚类数目的取值范围，通常k的取值为kk[2,],k为聚类maxmax数目的最大值，且k的取值为kn，这是一个经验规则，其中，n为数据maxmax样本数。Step2：针对每一个可能的k值，在利用聚类算法来进行聚类。Step3：最后根据聚类的有效性指标，来评价各个k值对应的聚类结果，从中选出聚类效果最好的k值。这样得到的聚类数虽然比较精确，但是往往带来了复杂度很高的计算，因为它要不断的尝试可能存在的k值。谱聚类的最后一步使用K-means算法，在实现的过程中也要确定k的取值，如果确定了聚类数目k，选取Laplacian矩阵的特征向量时就可以参考，而且最后聚不用人力估算，预防k值得不确定性带来的误差。3.2.2肘方法肘方法工作：增加簇数有助于降低每个簇的簇内方差之和。更多的簇可以捕获更细的数据对象簇，簇中对象之间更为相似。如果形成过多簇，则降低簇内方差和的边缘效应可能下降，因为把一个凝聚的簇分裂成两个只会引起簇内方差和的稍微降低。使用簇内方差和关于簇数的曲线的拐点是较为合适个一个方法。手肘法的核心指标是SSE(sumofthesquarederrors，误差平方和)22 硕士学位论文k2SSEpmi（3.1）i1pCi其中，Ci是第i个簇，p是Ci中的样本点，mi是Ci的质心（Ci中所有样本的均值），SSE是所有样本的聚类误差，代表了聚类效果的好坏。当k小于真实聚类数时，k的增大会增加每个簇的聚合程度，SSE的下降幅度大。当k到达真实聚类数时，再增加k所得到的聚合程度会变小，SSE的下降幅度会骤减，之后随着k值的继续增大而趋于平缓。SSE和k的关系图是一个凹函数的形状，凹部对应的k值为数据的真实聚类数。给定k>0，使用一种像k-means这样的算法对于数据集聚类，并计算簇内方差和SSE(k)。绘制SSE关于k的曲线。曲线的第一个（或最显著的）拐点暗示“正确的”簇数。3.2.3轮廓系数轮廓系数使用数据集的对象之间的相似性度量来度量对象。对于n个对象的数据集D，假设D被划分为K个簇CC,,。对于每个对象1kD，计算o与o所属的簇的其他对象之间的平均距离a(o)。类似地，b(o)是o到不属于o的所有簇的最小平均距离。假设C(1ik)，则idistoo(,)oCoo,ao()i（3.2）C1i而distoo(,)oCbo()mini（3.3）C:1jkji,jCi对象o的轮廓系数定义为bo()ao()so()（3.4）max{(),()}aobo轮廓系数的值在-1和1之间。a(o)的值反映o所属的簇的紧凑性。该值越小，簇越紧凑。b(o)的值捕获o与其他簇的分离程度。b(o)的值越大，o与其他簇越分离。比较理想的情况是，o的轮廓系数值接近1，包含o的簇是紧凑的，并且o远离其他簇。当轮廓系数的值为负时（即b(o)>a(o)），o距离其他簇的对象比距离与自己同在簇的对象更近。在更多情况下，这是很糟糕的，应该避免。在b(o)足够大或者a(o)足够小时，s(o)趋近于1，聚类效果比较好。23 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究3.2.4算法分析与流程开始Kmin=min(k1,k2)Kmax=max(k1,l2)数据预处理计算相似性矩阵Kmin<=k<=kmaxW，度矩阵D、拉普拉斯矩阵Lsym通过肘方法和轮廓系数检验得到k1和结束k2图3.1确定k值范围图通过上面的分析可知，传统的k值确定法是让k从2一直到n取值，总共需要尝试n-1次，当n很大时，相应的k值也就需要尝试很多次才能确定下来，这给运算带来极大的不便，算法性能差，并且这种经验范围缺少理论依据，24 硕士学位论文不具有普适性。通过因子分析，可以大概估计出最佳k值的范围，甚至从而缩小了搜索范围，进一步提高了运算的效率，更加重要的是，利用肘方法和轮廓系数具有比较好的理论基础，而不至于出现选择的盲目性。选择肘方法和轮廓系数这两种方法，是因为通过分析其公式可以发现，轮廓系数考虑了分离度b(o)，也就是样本与最近簇中所有样本的平均距离。轮廓系数大，可能是b(o)和a(o)都很大的情况下b(o)相对a(o)大得多，a(o)是有可能取得比较大的，此时，样本与同簇的其他样本的平均距离就大，簇的紧凑程度就弱，那么簇内样本离质心的距离也大，从而导致SSE较大。分析SSE的公式，SSE可以得到各个簇中样本点到其中心点差值的平方和。SSE越小，聚集的越密集。SSE可以避免轮廓系数中a(o)过大的这一情况。根据上面的理论分析，归纳出最终的算法描述如下：输入：数据样本集步骤1根据数据样本集构造文档词条矩阵A。步骤2根据矩阵A构造数据样本的相似度矩阵W。步骤3通过相似度矩阵W求得规范化的构造拉普拉斯矩阵L。步骤4通过肘方法和轮廓系数检验得到k1和k2，确定k的取值范围[kk,]，kk,可由上面的分析得出。minmaxminmax步骤5选取聚类有效性指标，通过聚类结果得到最佳聚类指标对应的k值。步骤6求矩阵L的前k个最大特征值和相应的特征向量v1,v2,…,vk，构造特n*k征向量空间矩阵V={v1,v2,…,vk}∈R。Vij步骤7将矩阵V按行向量进行单位化，得到新的矩阵Y，即Y。ij2Vijj步骤8将矩阵Y的每一行看成是空间内的一点，利用K-means聚类方法将其聚成k类。输出：最终的谱聚类划分AA,,A。12k从上面的算法计算过程看出，相对传统的谱聚类算法，本文提出的改进的地方是确定聚类数目k值。在此，通过分析，利用肘方法和轮廓系数法得到聚类数目的一个大概的参考范围，这样就避免了盲目的对k值进行搜索。这不仅对整个算法的性能带来一定的提升，而且提供了选取的理论依据，而不仅仅是凭经验去多次尝试。因为当样本数量达到很大规模的时候，需要尝试的次数会不断的增加，这对算法性能带来极大的影响。25 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究3.4验证实验为了验证本文改进的算法，选用搜狗语料库进行实验，这个数据在机器学习领域使用比较频繁。选择搜狐新闻数据的文化、军事、娱乐、女士、奥运等12个人工标记的种类。表3.1列出了测试集。每种一百篇文本，按顺序排列。接着分别用经典的K-means算法和谱聚类算法在这个数据集上进行实验。表3.1文本测试集类别财经IT健康体育旅游教育招聘文化军事娱乐女士奥运数目1001001001001001001001001001001001003.4.1文本预处理过程Rwordseg算法适合英文分词，在处理中文分词时文本选择结巴分词，这种分词算法在中文分词领域分词效果相对好，下表为原文本与分完词之后的结果。表3.2分词结果表分词前分词后"据""长期""致力于""高原病""研究""的""中国工程院""院士""吴""天一""介绍""海拔""米""米""的""林区""或""植被""丰富""的""地方""最""有利于""激发""人体""的""生理""机能""而""又""不至于""造成""低氧""损伤""位于""青海省""省会""西宁""附近""的""国家级""多巴""高原""训练""基地""被""称为""世界冠军""的""摇篮""铸造""金牌""的""工厂""海拔""为""米""一些""国家""和""地区""已""开始""利用""高山""气候""加""身体""锻炼""来""提高""人的心""肺""功能""提高""健康""水平""延年益寿""吴""天一""院士""介绍"26 硕士学位论文（续表3.2）"高原气候""还""非常""有利于""某些""疾病""的""治疗""和""康复""如""早期""高血压""冠心病""心肌""硬化症""糖尿病""支气管""哮喘""帕金森病""等""同时""初步""研究""发现""高原""低氧""还有""一定""的""减肥""效应""青海""拥有""众多""海拔""米""米""的""高原""旅游景点""这里""风光秀丽""气候宜人"分完词后，对比文本中是否存在停用词表中的词，若存在则删除该词，不存在则保留。部分停用词表如下表3.3所示：表3.3部分停用词表序号停用词1不只2不少3的4以来计算特征词的TF-IDF值，计算数据样本的相似度矩阵，构建拉普拉斯矩阵。3.4.2确定K值根据样本数据，求出样本集在不同的K值下，得出不同的轮廓系数值，如下图3.2所示：27 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究图3.2轮廓系数与K值关系图有前面的分析可知，当轮廓系数趋近于1，说明聚类效果比较好，观察上图，当k=17时，聚类效果最好，得出k1=17。图3.3手肘图28 硕士学位论文从图中观察可知，当k=12时出现第一个拐点，开始变平并形成一条几乎是平行斜率的线，由此可知k2=12。因此，可以得到k为12，k为17，所以kminmax的取值范围为[12,17]。只需要通过尝试k=12，13，14，15，16，17这6个数就可以确定最佳的k值，这里可以根据数据样本集本身可以知道分类数即为3。如果根据选取k值传统的经验取值方法，k的范围是[2,34]，意味着总共需要尝试33次才能得到最佳的k值。只用一种方法确定的K值并不能代表其有效性，而从上面的实验结果可知，本文通过改进的谱聚类算法，通过理论指导确定k值范围，最后需要的尝试的次数较少，较只使用一种方法更有效。3.4.3实验结果根据2.7节里提出的对已标记文本的聚类效果评估策略，对比k-means方法，采用Rand指数和Jaccard指数对聚类效果进行评估，结果如表3.2所示。表3.4文本集二种聚类算法结果对比方法RandJaccardk-means算法0.79360.6115谱聚类算法0.88280.7012由上表可知，k-means算法、谱聚类算法在Rand指标和Jaccard指标上效果都不错，但是谱聚类算法的聚类精度高于k-means算法，在Rand指数上提高了11.34%，在Jaccard指数上提高了14.67%。由此可知，在处理文本聚类问题时，谱聚类比k-means更有优势。3.5本章小结本章从确定k值入手，利用肘方法和轮廓系数得到k1和k2两个参考来确定k值范围，通过在真实数据集验证，与真实聚类数对比，确定真实聚类数在k的取值范围内，证明方法的有效性，更重要的是提供了理论依据，而不是盲目的去尝试所有可能的情况。通过算法对比，证明谱聚类算法聚类在文本聚类上效果更优。29 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究第四章谱聚类算法在医学上的应用4.1实验环境及流程实验是在Window7的台式电脑上运行，所使用的是32位的操作系统。采用的编程语言是R语言，所使用的软件是Ri386和Tinn-R。Ri386使用了3.3.0和3.0.0二个版本。使用3.0.0版本的原因是在建立语料库时，在3.3.0版本下语料库里容易会出现难以预料的回车符，这将导致后期实验的不准确性。因此在3.0.0版本下建立语料库并保存在本地，在3.3.0版本上导入语料库继续进行实验。实验中使用的部分方法对于java环境有依赖，安装java环境，在Tinn-R中安装rJava包，具体实验根据改进的谱聚类算法，图4.1展示了算法的基本流程图。选取聚类有效指开始标，确定最佳k值求出前k小个特征值和特征数据预处理向量把特征向量按列排列组成矩阵V，单计算相似性矩阵位化后为YW，度矩阵D、拉普拉斯矩阵Lsym将Y的每一行看成一个样本，用K-means进行聚类通过肘方法和轮廓系数检验得到k1和k2,确定Kmin和Kmax,得到K值的范围[Kmin,Kmax]结束图4.1实验流程图4.2数据集本文实验将不同病情、不同病程患者的检查文本视为独立样本。每条数据包含病患编号、病情描述以及检查提示。入选条件：1）患者均接受过卧位扫查或半卧位扫查等检查；2）患者的被怀疑患有不同严重程度的慢性肝病。根据上述标准初步选出与慢性肝病相关的110组慢性肝病超声波文本信息作为数据集进行实30 硕士学位论文验。本文样本数据包含编号、病情描述以及诊断提示三部分，其中诊断中提示包含较多的是肝硬化、脂肪肝和腹腔积液。样本形式如下：表4.1数据集形式病情描述诊断提示卧位扫查：脂肪肝。左肝28x50mm，右肝最大斜径138mm,肝硬化，门脉高压。肝缘变钝，包膜不光滑，轮廓清，实质光点胆囊内壁强光团：考虑附壁结石？息肉样病增粗，回声近场增强，远场衰减，光点细密，变？分布不均匀，肝内管系结构显示欠清，肝内脾切除术后。胆管未见扩张，内未见明显结石及肿块声像。胆囊大小78x30mm，胆囊内壁可见一大小为5x6mm强回声光团，后伴声影，随体位移动不明显。门静脉内径13mm，内清晰。胆总管内径5mm，内清晰。胰头、胰体、胰尾大小分别为20mm，13mm，17mm，形态规则，轮廓清，实质回声均匀，主胰管未见扩张，未见明显肿块声像。脾呈切除声像。左肾大小120x58mm，右肾大小118x50mm，形态规则，轮廓清，实质回声低于肝脾，双肾集合系统未见分离，未见明显肿块及结石声像。双输尿管未见明显扩张。膀胱充盈欠佳，内未见明显结石声像。腹腔未见明显液暗区。腹膜后未见明显肿大淋巴结声像。CDFI：门静脉血流充填好，双肾血流信号丰富，呈"树枝状"分布，以上各脏器未探及明显异常血流信号。31 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究4.3文本预处理传统的TXT文件中，数据与数据之间需要有必须用逗号隔开电脑才能识别，会增加人工的工作量。为了方便数据的导入，将文件类型转化为逗号分隔值形式文件（CSV），CSV格式是最常见的数据库和电子表格导入和导出格式。CSV格式比Excel格式具备的优势：1）CSV是纯文本文件，支持追加模式写入，节省内存。Excel是结构复杂的二进制文件，只支持一次性写入，较费内存。2）CSV的文件行数没有限制，在实际项目中已输出过上千万行的CSV文件；32位系统下Excel单个Sheet最多支持65535行。3）CSV是纯文本文件，可以使用任何文本编辑器进行编辑，因此可以在Linux终端下对其进行修改。Excel是二进制文件，目前已知的编辑工具有Office，OpenOffice，WPS，都为GUI工具，不支持在终端下编辑。本实验中主要是对文本中的病情描述进行聚类，所以单独抽取进行处理。数据中有9个变量，分别是X、EXAM_NO、EXAM_PARA、DESCRITION、IMRESSION、IS_ABNORMAL、USE_IMAGE、MEMO、REPORTNAME。EXAM_PARA、IS_ABNORMAL、USE_IMAGE、MEMO、REPORTNAM这5个属性值为空，数据没有医院导出。X所代表的是数据在被筛选之前的编号，EXAM_NO表示实际存在医院系统中的数据编号，DESCRITION表示的是病患的病情描述，IMRESSION表示的是诊断提示。属性DESCRITION是实验的主体数据。数据导入后如下图：图4.2数据导入图32 硕士学位论文4.3.1去噪处理提取属性为DESCRITION的部分进行实验，在进行分词之前，先要去除一些计算机意义不大和难以理解的内容，主要是删除英文字符、数字以及回车符。观察表4.1，英文字符在作为肝脏部位的大小单位“mm”和乘号“x”存在。每个文本中都含有，根据公式2.1计算TF-IDF值为0，对于聚类贡献小。去除数字有如下2点原因：1）文本之间具有相同的数字也不能确保这个数字是描述相同的部位；2）在对肝脏、胆囊这些部位进行大小描述后，后面都会有相应的文字说明，代表这些数字的意义。在文本分词时，回车符会对分词结果造成严重影响，在数据清理时需要删除。去除英文字符、数字以及回车符是为了确保后面实验聚类结果的可靠性。4.3.2文本分词实验采用基于词典的分词方法，词典来源为搜狗细胞词库，使用医学词汇大全、smile医学影像学词库、影像学词汇大全、超声医学和最全超声医学这五个词典。主要使用的包时jiebaR，该包的主要算法流程如下：利用导入的词典构造前缀词典；基于前缀词典对句子进行切分，得到所有切分可能；根据切分位置，构造一个有向无环图(DAG)。未登录词大概包含两大类：一类是特殊领域新出现的专业术语；另一类是专有名词。实验文本中第一类词出现可能性较大，对于未登录词，采用2.2.1节中的第二种方式——有汉字成词能力的HMM模型进行切分。为了降低数据维度，去除不能表征文本特征的词，建立停用词表。具体过程如下：先选取一个常用的停用词表，去除文本中包含的表中含有的词；观察首轮中分词结果，人工选取一些特殊词加入到停用词表，逐渐形成专有停用词表。在Tinn-R软件上，利用以上算法，对于超声检查报告的描述所见文本进行分析。图4.3为分词结果图。图4.3分词结果图33 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究4.3.3建立文档-词条关系矩阵将上一节中的中110个文本的分词结果以TXT形式保存在本地，在切换R3.3.0版本。将本地路径下的所有文档读入作为语料库。文档-词条关系矩阵是庞大的数据集，有必要删减稀疏的词条。本文中的词条库去除了出现次数少于5次的词条。根据上一节的流程，为了验证引用改进后的谱聚类算法在超声检查报告文本挖掘方面效果，使用110组慢性肝病超声检查报告文本的数据集进行实验和测试。对110个超声检查文本的特征提取采用TF-IDF方法，为了降低矩阵A的稀疏程度，剔除词频值小于5的词条。降维，去除了低于99.98%的稀疏条目项。文档-词条关系矩阵中横坐标是文本序号，纵坐标是词条，词条按照字母顺序表顺序进行排列。根据公式（2.1）计算所得文档词条矩阵A如下所示：0.000530.00390.002610.0007900.003860.001130.004150.00275A=110*3260.0007500.003670.00069000.000700.005170.003424.4算法应用4.4.1计算拉普拉斯矩阵根据公式（2.8）计算110个实验文本间的相似度矩阵W如下所示：10.96700.98290.99090.96800.98620.98200.96820.9767W=110*1100.98560.96580.98390.98490.96570.97990.98290.96631根据公式（2.10）和（2.25）计算所得到的拉普拉斯矩阵如下所示：34 硕士学位论文0.009350.009180.009210.009250.009180.009220.009200.009220.00917L=sym110*1100.009210.009180.009210.009210.009170.009180.009210.009220.00939超声检查报告文本在描述图像特征时，由于医生个人习惯等其他原因，文本报告大都遵循了一定格式，文本间的相似度大都达到了0.96以上。例如，大多数慢性肝病的超声检查报告都会先描述左肝右肝的形态大小以及肝缘情况，还有胆囊，胰腺等器官的一些信息，这些信息大多很相似。另外，本文针对慢性肝病这一特殊领域的超声检查报告文本进行研究，所涉及的词汇比较固定，由于慢性肝病的超声检查报告文本本身范围的局限性，导致它不会像别的大范围文本聚类那样就有较大的差异性。4.4.2确定聚类数目K值通过上面的方法和步骤，已经得到了相似性矩阵、度矩阵、特征值，接下来要确定聚类数目k的取值范围以及选取一个聚类有效性指标，通过聚类结果得到最佳聚类指标对应的k值即为最佳k值。因为样本集大小为110，所以先取10作为最大值，测试k在[2,10]范围内，对应的各个簇的组内平方和误差值，即SSE值。再将k为各个值时，对应的各个簇的SSE值相加作为K为固定值时的总SSE值。表4.2聚类数小于10时SSE值K12345SSE7.5871066.3599915.1978984.4379593.697858K678910SSE3.2686562.9353412.7539722.6383232.465616通过上面表格可以看到，从一开始，K变化时，即相邻两个SSE之间的差值比较大，但是当到了某个值的时候，变化变得平缓了，相邻特征值之间的差距越来越小了。再通过作图，可以更直观的观察和反应特征值大小的变化情况，开始斜率很大，到后面就几乎是一条接近平行斜率的线。如图4.4所示：35 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究图4.4聚类值K与SSE值关系图分析4.2.2里的公式可知，SSE值越小，簇内间点就越紧密。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。由上图可知，k为7时，曲线开始趋于平缓，由肘方法可知，这个临界值的取值为7，即k1的值为7。通过上面的工作之后，接下来在利用轮廓系数法求出k2。根据样本集大小，所以先取10作为最大值，求k在[2,10]范围内对应的轮廓系数。轮廓系数是类的密集与分散程度的评价指标，a(o)是测量组内的相似度,b(o)是测量组间的相似度。s(o)为轮廓系数，范围从-1到1，值越大说明组内吻合越高，组间距离越远——也就是说，轮廓系数值越大，聚类效果越好。为了更好地显示聚类值K与轮廓系数的关系，画图显示，图4.5如下所示：36 硕士学位论文图4.5轮廓系数与K关系图根据上图可知，当K=2时，轮廓系数最大，这个临界值的取值为2，即k2的值为2。通过上面的工作，首先利用相似度矩阵求出所有特征值，根据这些特征值的各种特征，然后再利用之前分析的肘方法和轮廓系数法得到k1和k2两个参考值来确定k值范围，k为k1和k2中较小的那个值，k为k1和k2中较大minmax的那个值，而k的取值范围则k和k在之间。它们的具体的取值情况如表所minmax示。表4.3K的取值范围表k1k2kkkminmax7227[2，7]在本文中，样本数为110，所以取n=110，根据传统经验的k值确定法需要尝试10次，但是这只是根据经验得出的一个k值的取值范围，缺乏理论依据，不具有普适性。而通过本文提出的改进方案需尝试37次，并且这种k值的选择方案，根据本文的分析，是具有一定的理论依据，对k值得选取具有很大的参考价值。至此可以知道，选定一个聚类有效性指标，只要尝试运行聚类算法37次就能得到最佳聚类效果对应的k值，亦即最终的k值。利用第三章介绍的聚类37 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究效果的评价指标，本文选取的是Calinsky指标，Calinsky指标指出，Calinskycriterion值一般来说是越大，聚类效果越好。图4.6不同k值对应的Calinsky指标横坐标代表不同的K值，纵坐标表示的是Calinsky指标。通过实验，确定样本对应的k值为5。对所有的5个类进行分析发现，类中样本数最多有50多个，而少的则2个，原因是因为由于医生个人书写习惯，对于相同的病症表述形式不一样，或者是省略对于一些内脏处于正常范围内的体征描写。从结果中还发现样本数最多的类，诊断结果中大多都含有脂肪肝这一诊断提示，有一个类的诊断提示中几乎只有腹腔积液这一项，根据对比同一类文本中的病情描述部分，发现有一些固定的病情描述语句，这是相同病情的常见特征，所以这类用户极有可能是病情相似。4.5结果分析本文根据聚类的情况，显示出5种类中出现频率最高的一些词，用词云的方式进行图形化显示，词的出现频率越高，字体越大。38 硕士学位论文图4.75种类的高频词云图通过观察图4.7，能确定每个类的频率较高的且特有的词条。第c1类中最高频的几个词分别是“中等”、“游离”、“深处”等。第c2类中最高频的几个词分别是“暗区”、“深约”、“液”等。第c3类中最高频的几个词分别是“约”、“游离”、“深处”等。第c4类中最高频的几个词分别是“近场”、“远场”、“衰减”等。第c5类中最高频的几个词分别是“胸腔”、“透声”、“约”等。最为特殊的是第c3类，它的词汇最少，原因有二点：1）该类的超声波文本检查描述最少，病情描述都类似“卧位扫查： 腹腔可探及游离液暗区，较深处39 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究30mm。”，诊断提示也只有“腹腔积液”；2）该类超声文本数目也是最少的，只有3个。第c4类的超声波检查文本的检查提示中大多都含有脂肪肝这一项诊断，从而推断“近场”、“远场”、“衰减”与脂肪肝有密切联系。对比c4类中的原文本，可以发现，“近场”、“远场”等词来源于描述肝脏的句子“肝脏大小正常,形态规则，轮廓清，实质回声近场增强，远场衰减”。可以判断该句是诊断脂肪肝的重要语句。第c1类和第c3类有相似的地方，“游离”、“深处”等词出现的频率较高，观察原文本，发现c1类的诊断提示中大都含有“腹腔积液”这一诊断提示。“中等”一词来自于“形态规则，轮廓清，实质回声中等，分布均匀”这句，这是提示胰腺、脾脏指标正常的句子。第c2类中“暗区”一词的出现的频率最高，分析c2类中的诊断提示，发现诊断提示中“腹腔积液”较多，与c3类不同的是，还有一些是“胸腔积液”和无积液。根据这些发现能确定“暗区”与“积液”之间存在这必然的联系。第c5类，出现频率最高的是“胸腔”这个词条，可以认定该类超声波检查报告跟胸腔的联系最为紧密。在以后对该类病情分析总结时，对这种联系好好进行分析。“胸腔”一词在这个图中出现了2次，一次是作为“胸”、“腔”两个单独的字出现，另一次是作为一个词出现。图4.8不同词条间对应的二维平面的聚类情况40 硕士学位论文由于很难描绘出数据在326个词条空间内的分布情况。本文选取了“中等”、“游离”、“液”这3个在110组数据中分布频率较高的词条，以两两为一组，分别画出110组数据在这两个词条上的分布情况，图像关于正对角线对称，观察时只观察下半角。每一组数据为平面上的一个点。当两个点重合时，只会显示后面一个点的颜色。上图中显示了分别以三个词条为x轴和y轴聚类的情况。不同的颜色的点，代表不同的类，第c1类到第c5类的颜色分别用黄色、红色、灰色、绿色、蓝色。如上图4.8。红色的c2类在以“游离”和“液”为轴时呈y=x的直线分布，证明“游离”与“液”在c2类中几乎是同时出现，结合上面c2的词频图可推知“游离”与“液”共同能确诊“腹腔积液”这一诊断。在绿色的c4类中，不含“游离”一词，含“中等”一词较多，以及少量的“液”。灰色的c3类中不含“中等”，且数量极少。各个类在图中大多以直线分布。根据以上结果，确定了部分词与诊断提示的关联性，相同类中病情的相似性。同一类中的每个类是一个小型的病例网，将该类中医治成功率高的医生推荐给该类中其他未被治疗的病人，这样既可以为医院诊断率带来提升，也可以给病人带来福祉，提供更好的服务。4.6本章小结首先对慢性肝病超声波文本数据进行了分析以及预处理，对数据样本集进行处理建立文档-词条关系矩阵，然后对文档-词条关系矩阵运用改进后的谱聚类算法，主要是利用肘方法和轮廓系数得到k1和k2两个参考来确定k值范围，再选定一个聚类有效性指标，通过聚类结果得到最佳聚类指标对应的k值，进行最终的聚类。针对最终的结果，分析聚类结果的价值。41 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究结论世界卫生组织报告表明，全球大约有4亿人正遭受着慢性肝病的困扰，且中国是患慢性肝病的大国，慢性肝病是一种危害性大、流行较广泛、治愈率很低、[57]死亡率却很高的传染病。伴着科技技术的不断发展和应用，社会各个领域都步入了大数据时代，提高病人的治愈率越来越重要。为了更准确更快速有效的获取所需要的信息，聚类技术应遇而生。它与机器学习的无监督学习有关，具有广泛的应用。聚类作为一个充满挑战的领域，其典型的要求包括可伸缩性、处理不同类型的数据和属性的能力、发现任意形状的簇、处理噪声数据的能力、增量聚类、聚类高维数据的能力以及聚类的可解释性和可用性。谱聚类算法通过利用简单的线性代数知识——特征分解，可以得到全局最优解，这是该算法的优点。谱聚类算法通过求出样本的相似度或者Laplacian矩阵，然后计算特征值和特征向量，再选取特征向量，将它进行聚类。本文首先在第一章简单介绍了一下介绍了关于谱聚类的背景、现状和研究的热点难点问题，展示了谱聚类简要轮廓，接着在第二章详细的阐述了谱聚类算法的基本理论及谱聚类算法的基础等相关内容，对其做出了详细的分析和论述，并且在第三章通过从确定k值入手，通过因子分析，利用肘方法和轮廓系数来确定聚类数目，进而提出了相应改进的方案，最后在第四章，对数据样本集先进行相似性计算求得相似性矩阵，利用肘方法和轮廓系数得到聚类数目k值得范围，再选定一个聚类有效性指标，通过聚类结果得到最佳聚类指标对应的k值，进行最终的聚类，通过实验验证改进后算法。针对最终的结果，分析聚类结果的价值。本文所做的重要几方面的工作如下：（1）对慢性肝病超声波检查报告的预处理工作。本文选择符合条件的样本数据，通过对慢性肝病超声波检查报告的分析，在计算样本间相似度之前，先对其进行预处理工作，这样在一定程度上提高了数据的质量。（2）谱聚类算法中k值的确定。本文通过对谱聚类算法热点问题的分析，从k值的确定着手，利用肘方法和轮廓系数，提出了一个确定k值范围的方法，对k值的选取具有一定的参考价值。（3）本文把改进后的谱聚类算法应用到慢性肝病的超声波检查报告上，分析每种类型超声报告出现高频词与诊断结果关系，为提高诊断率提供支持。通过分析聚类结果可知，每个类是一个小型的病例网，将该类中医治成功率高的医生推荐给该类中其他未被治疗的病人，也可以给病人带来便利，提供更好的服务。42 硕士学位论文虽然本文对谱聚类算法进行了改进，并且也取得了一定的效果，但是还处于完善阶段，还存在许多工作需要进一步的深入研究。（1）优化数据预处理步骤在本文中，预处理阶段的工作略微有点粗糙，即首先就将数字或者英文字母只是做简单的删除，这样做简化了数据预处理流程，但是可能删掉了一些潜在的有价值的记录。下一步的工作将要对这些记录进行分析，用其他办法来分析这些数字和字母的价值。（2）拐点的自动选择研究在根据手肘法画出拐点图后，需要人工选择拐点。人工选择拐点会存在一定的误差，影响实验结果，需要一个更有效的方式确定拐点。（3）大规模数据的应用由于谱聚类需要大量的计算，这也使得它在大规模数据的应用方面存在着一定的局限性，不利于大规模的计算，以至于在当前互联网发展受阻。下一步可以通过一些高新技术，将谱聚类算法实现并行化，使谱聚类在并行化框架上得以运行。43 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究参考文献[1]吴汉华.大数据时代中如何进行医疗数据挖掘与利用.硅谷,2014(5):13-13.[2]龙光宇，徐云.CRF与词典相结合的疾病命名实体识别.微型机与应用，2017(21):51-53.[3]InokuchiA,WashioT,MotodaH.AnApriori-BasedAlgorithmforMiningFrequentSubstructuresfromGraphData//EuropeanConferenceonPrinciplesofDataMiningandKnowledgeDiscovery.Springer-Verlag，2000:13-23.[4]李仁泽.基于数据挖掘方法的综合症—药物关系挖掘：[南京大学硕士学位论文].南京：南京大学计算机科学与技术系，2013.23-25.[5]程亮喜.基于评论挖掘的药物副作用发现：[生物医学工程硕士学位论文].大连：大连理工大学生物医学工程学院，2014.31-32.[6]魏志森，杨静宇，於东军.基于加权PSSM直方图和随机森林集成的蛋白质交互作用位点预测.南京理工大学学报(自然科学版)，2015，39(4):379-385.[7]钱庆，吴思竹.基于知识组织系统的生物医学文本挖掘研究见：中华医学会全国医学信息学术会议论文汇编，北京，2015，100020[8]李剑风.融合外部知识的中文命名实体识别研究及其医疗领域应用：[哈尔滨工业大学硕士学位论文].哈尔滨：哈尔滨工业大学计算机科学与技术学院，2016，30-31.[9]王效俐，刘潇，苏强.邻域粗糙集融合贝叶斯神经网络在医疗决策中的应用研究.工业工程与管理，2016，21(5):141-147.[10]Sabharwal，ChamanL,Hacke,etal.FormationofclustersandresolutionofordinalattributesinID3classificationtrees.ComputerNetworks，2018，57(5):1217-1233.[11]夏修臣，王秀英.基于余弦相似度的改进C4.5决策树算法.计算机工程与设计，2018(1):120-125.[12]InokuchiA，WashioT，MotodaH.AnApriori-BasedAlgorithmforMiningFrequentSubstructuresfromGraphData//EuropeanConferenceonPrinciplesofDataMiningandKnowledgeDiscovery.Springer-Verlag，2000:13-23.[13]IliopulosI，EnrightAJ，OuzounisCA.Textquest:documentclusteringofMEDLINEabstractsforconceptdiscoveryinmolecularbiology，PacificSymposiumonBiocomputing，2001:384-395.44 硕士学位论文[14]YamamoY，TakagiT．Biomedicalknowledgenativigationbyliteratureclustering[J].JournalofBiomedicalInterformatics，2007，40:114130.[15]ZhuS，ZengJ，MamitsukaH.Enchancingmedlinedocumentclusteringbyincorporatingmeshsemanticsimilary.Bioinformatics，2009，25(15):1944-1951.[16]PYildirim，ÇinarÇeken，RHassanpour，etal.PredictionofSimilaritiesAmongRheumaticDiseases，JournalofMedicalSystems，2010，36(3):1485-90.[17]ZhengJyeLing，QuocTrungTran，JuFan，etal.GEMINI:AnIntegrativeHealthcareAnalyticsSystem.ProceedingsoftheVldbEndowment，2014，7(13):1766-1771.[18]FeldmanR，NetzerO，RosenfeldB,etal.UtilizingTextMiningonOnlineMedicalForumstoPredictLabelChangeduetoAdverseDrugReactions//ACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM，2015:1779-1788.[19]MarkatouM，BallR，BotsisT，etal.Textminingforlargemedicaltextdatasetsandcorrespondingmedicaltextclassificationusinginformativefeatureselection.2015.[20]HagenL，KahngAB.Newspectralmethodsforratiocutpartitioningandclustering.Computer-aideddesignofintegratedcircuitsandsystems，IEEETransactionson，1992，11(9):1074-1085.[21]MalikJ，BelongieS，LeungT，etal.ContourandTextureAnalysisforImageSegmentation.InternationalJournalofComputerVision，2001，43(1):7-27.[22]MckeownKR，BarzilayR，EvansD，etal.TrackingandsummarizingnewsonadailybasiswithColumbia'sNewsblaster//HumanLanguageTechnologyConference.2002:280-285.[23]TakahashiS，MorimotoT，TsurutaN.DocumentFilteringBasedonSpectralClusteringforSpeechRecognitionLanguageModel//InternationalMulticonferenceofEngineersandComputerScientists2007，Imecs2007，March21-23，2007，HongKong,China.DBLP，2007:393-398.[24]ZhengJ.TheApplicationofRoughSpectralClusteringonTextDataMining.ComputerKnowledge&Technology，2009.[25]李博，文敦伟，王珂等.基于隐含主题和语义树的医学文本自动批注.吉林大学学报（工学版），2012，42（1）：1671－5497[26]吴梦麟，陈强，孙权森.结合影像和文本信息的医学病例检索.计算机辅助设计与图形学学报，2014，26(9):1430-1437.45 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究[27]栗伟，许洪涛，赵大哲等.一种面向医学短文本的自适应聚类方法.《东北大学学报自然科学版》，2015，36(1):19-23.[28]徐海鹏，董冲亚，阎小妍，等.手机健康管理类应用纵向大数据管理与统计分析.中国循证医学杂志，2016(8):972-977.[29]窦鹏伟，王珍，佘侃侃等.基于文本挖掘的中医文本情感分析.中华中医药学刊，2017(5):1190-1193.[30]扈中凯.面向医疗数据的商务智能技术研究：[浙江大学博士学位论文].浙江大学，杭州：浙江大学信息与电子工程学院，2015，44-45[31]苏娅，刘杰，黄亚楼.在线医疗文本中的实体识别研究.北京大学学报(自然科学版)，2016，52(1):1-9.[32]施雅慧，李作峰，常才等.儿童先天性心脏病超声心动图报告与个体风险的相关性分析，《复旦学报(医学版)》，2018(2).[33]刘克浩，肖飞龙.基于云平台和大数据的新型健康管理模式.公共卫生与预防医学，2014，25(5):89-91.[34]李迎新，黄河.基于国家卫生与健康管理大数据平台的慢病防控模式.国际生物医学工程杂志，2017(6).[35]谢翠萍，陈家益，白金山.基于全文索引与余弦公式医学文本相似性分析.《微型电脑应用》，2014，30(1):25-27.[36]JiaweiHan，MichelineKamber，JianPei.数据挖掘：概念与技术(原书第3版).北京：机械工业出版社，2012.289-290.[37]秦赞.中文分词算法的研究与实现：[吉林大学硕士学位论文].吉林：吉林大学电子科学与工程学院，2016，21-22.[38]百度百科，停用词.baike.baidu.com/item/停用词/4531676?fr=aladdin，2017-08-01.[39]崔彩霞.停用词的选取对文本分类效果的影响研究.太原师范学院学报:自然科学版，2009，7(4):91-93.[40]顾益军，樊孝忠，王建华，等.中文停用词表的自动选取.北京理工大学学报,2005，25(4):337-340.[41]张振峰.基于向量空间模型的文本分类算法研究：[杭州电子科技大学硕士学位论文].杭州：杭州电子科技大学计算机学院，2011，23-25.[42]CrnicJ.IntroductiontoModernInformationRetrievalMcGrawpHill，1983.[43]ZadroznyS，KacprzykJ.AnExtendedFuzzyBooleanModelofInformationRetrievalRevisited//The,IEEEInternationalConferenceonFuzzySystems.IEEE，2005:1020-1025.46 硕士学位论文[44]李茹，王智强，李双红，等.基于框架语义分析的汉语句子相似度计算.计算机研究与发展，2013，50(8):1728-1736.[45]互动百科.TF-IDF.en.wikipedia.org/wiki/Tf–idf，2017-05-29.[46]杨凯峰，张毅坤，李燕.基于文档频率的特征选择方法.计算机工程，2010，36(17):33-35.[47]张吉文.基于谱聚类的文本聚类算法研究：[贵州大学硕士学位论文].贵州大学计算机科学与技术学院，2015.[48]刘云.基于蚁群聚类的特征基因选择算法研究：[湖南大学硕士学位论文].长沙：湖南大学信息科学与工程学院，2010.[49]百度百科.Jaccard.baike.baidu.com/item/杰卡德距离/15416212?fr=aladdin，2017-08-01.[50]WangW，YangJ，MuntzRR.STING:AStatisticalInformationGridApproachtoSpatialDataMining//InternationalConferenceonVeryLargeDataBases.MorganKaufmannPublishersInc.1997:186-195.[51]HåstadJ.Cliqueishardtoapproximatewithinn1−ε.ActaMathematica，1999，182(1):105-142.[52]席景科，谭海樵.空间聚类分析及评价方法.计算机工程与设计，2009，30(7):1712-1715.[53]邓庚盛，刘承启，熊艳.基于网格和密度的CLIQUE聚类算法的研究与实现.计算机与现代化，2008，2008(12):8-11.[54]刘建平Pinard.www.cnblogs.com/pinard/p/6221564.html.2016-12-29.[55]TanJ，WangWX,FengMS,etal.ANewApproachBasedonNcutClusteringAlgorithmforSignatureSegmentation.AasriProcedia，2012，1(3):14-20.[56]WöstenJHM，VerzandvoortSJE，LeenaarsJGB，etal.Soilhydraulicinformationforriverbasinstudiesinsemi-aridregions[J].Geoderma，2013，195-196(s195–196):79-86.[57]常炳国，李玉琴，冯智超，等.基于主成分机器学习算法的慢性肝病的智能预测新方法.计算机科学，2017(b11):65-67.47 基于谱聚类的慢性肝病超声检查报告文本挖掘算法研究附录A攻读学位期间主要研究成果[1]ChangBingguo，ChenXiaofei.StudyonTextMiningAlgorithmforUltrasoundExaminationofChronicLiverDiseasesBasedonSpectralClustering.20173rdInternationalConferenceonSoftComputinginInformationCommunicationTechnology，已录用，待发表，稿件编号SCICT-288[2]软件著作权：基于谱聚类算法的医疗文本分类系统48 硕士学位论文致谢转眼研究生的生活即将结束，回顾过去的24年学生生活，不经感触良多。小的时候总希望长大自主自己的人生，但在这个即将自我主掌自己人生的关键点上，却有很多的不舍。想起以往帮助过我的良师益友，总会有百般滋味在心头。但是首先，我要感谢我的导师，常炳国教授。是您为我提供了力所能及的一切支持，常老师品德高尚、严于律己、博学多才、和蔼可亲，在我三年多的研究生生涯中，他不仅传授了我做学问的技巧，还传授了我许多为人处世的道理，这些必将让我受益终身，并对我的小论文与硕士课题进行了耐心的指导，让我受益匪浅。研究生期间，在导师和各位任课老师们的指导下，我的学习能力、自主能力以及心态都有了很大的改善和提高，在前进的方向，导师永远是我的引路人。同时，感谢实验室的各位。感谢研一时师兄师姐的引导，没有你们，我将事倍功半；感谢研三时师弟师妹的帮助，在我不在学校的日子里各种帮忙跑材料。感谢你们这几年来的支持、帮助与信任。我还要感谢湖南大学曾经的和现在的实验室同僚。我特别感谢李玉琴师姐与我分享学术心得。感谢舍友田源、袁胜兰和李雅婷，无数个夜间闲聊都会让我意识到自己不足，解答自己的困苦。感谢师兄戴世稳、以及同门刘清星、陈志屹给予我的帮助，愿大家以后能再相聚。感谢湖南大学信息科学与工程学院。感谢辛勤工作的各位行政老师。湖大是我的根，不管走到哪，都要给湖大争脸。湖大校训——实事求是，敢为人先，我将永记心中。最后，感谢家人，没有你们从小的培养教诲，就不会有如今的我，正所谓羔羊跪乳、乌鸦反哺，之后的人生正是要回报的时候。还要感谢一直陪伴我的朋友们。在我不断失败，迷茫不知道该以什么为目标，是你们让我对实验充满干劲，驱散我的阴霾。谢谢你们，出现在我的人生；谢谢你们的等候。我的论文还有很多需要改进的地方，显得还很稚嫩。但是这次做论文的经历使我终身受益，让我明白很多道理。任何事情不可能一蹴而就，一蹴而就都是在前期很多工作上累积的。事前没有万全的准备，事后就必须加倍努力。要真真正正用心去做的一件事情，唯有认真和努力才不会辜负你的人生。在学术的道路上，我还有很多需要学习的地方。感谢湖南大学，感谢各位老师同学，感谢我的家人朋友，因为有你们，我的人生才能有不一样的色彩，我将秉承千年学府的校训和各位老师的教诲，走向更美好的未来。49
