 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
关联规则挖掘最小支持度阀值设定的优化算法研究
study on optimized method of minim.
下载积分：2000
内容提示：关联规则挖掘最小支持度阀值设定的优化算法研究
study on optimized method of minimum support for association rule mining
文档格式：PDF|
浏览次数：24|
上传日期： 14:32:18|
文档星级：
该用户还上传了这些文档
关联规则挖掘最小支持度阀值设定的优化算法研究
官方公共微信后使用快捷导航没有帐号？
查看: 1919|回复: 0
数据挖掘算法——神经网络模型
金牌会员, 积分 2978, 距离下一级还需 22 积分
论坛徽章:19
数据挖掘——模型
摘要：通过分析数据挖掘中现有的算法的研究现状以及它们的局限性，介绍一种基于数据库的数据挖掘算法——神经网络模型，本文最后也提出了神经网络模型在数据挖掘中存在的一些问题和发展前景。
关键字：神经网络模型，数据挖掘
引言: 数据挖掘是适应信息社会从海量的数据库中提取信息的需要而产生的新学科。它是统计学、、数据库、模式识别、等学科的交叉。数据挖掘往往针对特定的数据、特定的问题，选择一种或者多种挖掘算法，找到数据下面隐藏的规律，这些规律往往被用来预测、支持决策。它的应用非常广泛，只要该产业有分析价值与需求的数据库，皆可利用数据挖掘工具进行有目的的发掘分析。常见的应用案例多发生在零售业、制造业、财务金融保险、通讯及医疗服务。 数据挖掘技术的方法：
①神经网络方法：神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分3大类：以感知机、bp反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以hopfield的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以art模型、koholon模型为代表的，用于聚类的自组织映射方法。神经网络方法的缺点是&黑箱&性，人们难以理解网络的学习和决策过程。 ②遗传算法：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。&&
③决策树方法：决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。
④粗集方法：粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗集理论实用化的难点。
⑤覆盖正例排斥反例方法：它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则。
⑥统计分析方法：在数据库字段项之间存在两种关系：函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公式表示，但仍是相关确定性关系)，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计(求大量数据中的最大值、最小值、总和、平均值等)、回归分析(用回归方程来表示变量间的数量关系)、相关分析(用相关系数来度量变量间的相关程度)、差异分析(从样本统计量的值得出差异来确定总体参数之间是否存在差异)等。
国际体验设计协会IXDC 历届大会精彩集锦游戏用户体验大会
互联网产品大会
交互设计体验周
wk_ad_begin({pid : 21});wk_ad_after(21, function(){$('.ad-hidden').hide();}, function(){$('.ad-hidden').show();});& &
⑦模糊集方法：即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换模型--云模型，并形成了云理论。
神经网络发展历史：1943年，心理学家W.S.McCulloch和数理逻辑学家W.Pitts建立了神经网络和数学模型，称为MP模型。他们通过MP模型提出了神经元的形式化数学描述和网络结构方法，证明了单个神经元能执行逻辑功能，从而开创了人工神经网络研究的时代。1949年，心理学家提出了突触联系强度可变的设想。60年代，人工神经网络的到了进一步发展，更完善的神经网络模型被提出，其中包括感知器和自适应线性元件等。M.Minsky等仔细分析了以感知器为代表的神经网络系统的功能及局限后，于1969年出版了《Perceptron》一书，指出感知器不能解决高阶谓词问题。他们的论点极大地影响了神经网络的研究，加之当时串行计算机和人工智能所取得的成就，掩盖了发展新型计算机和人工智能新途径的必要性和迫切性，使人工神经网络的研究处于低潮。在此期间，一些人工神经网络的研究者仍然致力于这一研究，提出了适应谐振理论（ART网）、自组织映射、认知机网络，同时进行了神经网络数学理论的研究。以上研究为神经网络的研究和发展奠定了基础。1982年，美国加州工学院物理学家J.J.Hopfield提出了Hopfield神经网格模型，引入了“计算能量”概念，给出了网络稳定性判断。 1984年，他又提出了连续时间Hopfield神经网络模型，为神经计算机的研究做了开拓性的工作，开创了神经网络用于联想记忆和优化计算的新途径，有力地推动了神经网络的研究，1985年，又有学者提出了波耳兹曼模型，在学习中采用统计热力学模拟退火技术，保证整个系统趋于全局稳定点。1986年进行认知微观结构地研究，提出了并行分布处理的理论。90年代初，又有脉冲耦合神经网络模型被提出。人工神经网络的研究受到了各个发达国家的重视，美国国会通过决议将日开始的十年定为“脑的十年”，国际研究组织号召它的成员国将“脑的十年”变为全球行为。在日本的“真实世界计算（RWC）”项目中，人工智能的研究成了一个重要的组成部分。 神经网络的的基本特征：
（1）非线性 非线性关系是自然界的普遍特性。大脑的智慧就是一种非线性现象。人工神经元处于激活或抑制二种不同的状态，这种行为在数学上表现为一种非线性关系。具有阈值的神经元构成的网络具有更好的性能，可以提高容错性和存储容量。&&
（2）非局限性 一个神经网络通常由多个神经元广泛连接而成。一个系统的整体行为不仅取决于单个神经元的特征，而且可能主要由单元之间的相互作用、相互连接所决定。通过单元之间的大量连接模拟大脑的非局限性。联想记忆是非局限性的典型例子。&&
（3）非常定性 人工神经网络具有自适应、自组织、自学习能力。神经网络不但处理的信息可以有各种变化，而且在处理信息的同时，非线性动力系统本身也在不断变化。经常采用迭代过程描写动力系统的演化过程。&&
（4）非凸性 一个系统的演化方向，在一定条件下将取决于某个特定的状态函数。例如能量函数，它的极值相应于系统比较稳定的状态。非凸性是指这种函数有多个极值，故系统具有多个较稳定的平衡态，这将导致系统演化的多样性。
神经网络的应用：神经网络的应用已经涉及到各个领域，且取得了很大的进展。
自动控制领域：主要有系统建模和辨识，参数整定，极点配置，内模控制，优化设计，预测控制，最优控制，滤波与预测容错控制等。&&
处理组合优化问题：成功解决了旅行商问题，另外还有最大匹配问题，装箱问题和作业调度问题。&&
模式识别：手写字符，汽车牌照，指纹和声音识别，还可用于目标的自动识别，目标跟踪，机器人传感器图像识别及地震信号的鉴别。&&
图像处理：对图像进行边缘监测，图像分割，图像压缩和图像恢复。&&
机器人控制：对机器人轨道控制，操作机器人眼手系统，用于机械手的故障诊断及排除，智能自适应移动机器人的导航，视觉系统。&&
医疗：在乳房癌细胞分析，移植次数优化，医院费用节流，医院质量改进，疾病诊断模型等方面均有应用。
神经网络方法：神经网络方法用于分类、聚类、特征挖掘、预测和模式识别，神经网络方法模仿动物的脑神经元结构，以M—P模型和Hebb学习规则为基础。在本质上是一个分布式矩阵结构，通过对训练数据的挖掘，逐步计算神经网络连接的权值。神经网络模型大致可分为以下三种：（1）前馈式网络：以感知机、反向传播模型和函数型网络为代表，主要用于预测和模式识别等领域；（2）反馈式网络：以Hopfield离散模型和连续模型为代表，主要用于联想记忆和优化计算；（3）自组织网络：以自适应共振理论：ART模型和Kohonen模型为代表，主要用于聚类分析。
神经网络模型存在问题：①数据质量：由于许多数据是动态的、有冗余或不完整，致使产生的规则存在不真实和异常等问题。 ②非数值型数据的处理：合理量化此类数据往往凭人们的主观经验而定，这将影响挖掘结果。 ③学习样本的大小：对于数据量较小的数据库，可能出现错误的结果，这时就可以把这些数据作为新样本补充到学习样本中去。 ④激励函数的选取：激励函数是对多个输入进行处理产生输出的功能模块，它将关系到结果是否有价值和真实，对于数据库中模糊知识的发现，往往先对输出状态进行编码，采用符号函数作为激励函数。
⑤神经网络的训练速度问题：构造神经网络时要求对其训练许多遍，这意味着获得精确的神经网络需要花费许多时间。 神经网络的发展前景：针对神经网络存在的问题和社会需求，今后发展的主要方向可分为理论研究和应用研究两个方面。 （1）利用神经生理与认识科学研究大脑思维及智能的机理、 计算理论，带着问题研究理论。 人工神经网络提供了一种揭示智能和了解人脑工作方式的合理途径，但是由于人类起初对神经系统了解非常有限，对于自身脑结构及其活动机理的认识还十分肤浅，并且带有某种“先验”。而且，神经科学，心理学和认识科学等方面提出的一些重大问题，是向神经网络理论研究提出的新挑战，这些问题的解决有助于完善和发展神经网络理论。因此利用神经生理和认识科学研究大脑思维及智能的机理，如有新的突破，将会改变智能和机器关系的认识。 利用神经科学基础理论的研究成果，用数理方法探索智能水平更高的人工神经网络模型，深入研究网络的算法和性能，如神经计算、进化计算、稳定性、收敛性、计算复杂性、容错性、鲁棒性等，开发新的网络数理理论。由于神经网络的非线性，因此非线性问题的研究是神经网络理论发展的一个最大动力。特别是人们发现，脑中存在着混沌现象以来，用混沌动力学启发神经网络的研究或用神经网络产生混沌成为摆在人们面前的一个新课题，因为从生理本质角度出发是研究神经网络的根本手段。
（2）神经网络软件模拟， 硬件实现的研究以及神经网络在各个科学技术领域应用的研究。
由于人工神经网络可以用传统计算机模拟，也可以用集成电路芯片组成神经计算机，甚至还可以用光学的、生物芯片的方式实现，因此研制纯软件模拟，虚拟模拟和全硬件实现的电子神经网络计算机潜力巨大。如何使神经网络计算机与传统的计算机和人工智能技术相结合也是前沿课题；如何使神经网络计算机的功能向智能化发展，研制与人脑功能相似的智能计算机，如光学神经计算机，分子神经计算机，将具有十分诱人的前景 参考文献：
[1] 林筑英，林建勤& &数据挖掘技术及其所面临的问题& &贵州师范大学学报 ]闪四清，陈茵，程雁& &数据挖掘& & 清华大学出版社&&2003 [3]党建武&&神经网络技术及应用& &中国铁道出版社& &1999 [4]胡守仁&&神经网络应用技术& &国防科技大学出版社&&1998 [5]陈京民&&数据仓库与数据挖掘& &电子工业出版社& &2002
[6] 李庆亮，张彦峰&&人工智能的应用及发展前景&&洛阳师范学院学报& &1998&&[7]杨建刚&&人工神经网络实用教程& &浙江大学出版社& &2001.1
扫一扫加入本版微信群苹果/安卓/wp
积分 3010, 距离下一级还需 590 积分
权限: 自定义头衔, 签名中使用图片, 隐身, 设置帖子权限, 设置回复可见
道具: 彩虹炫, 涂鸦板, 雷达卡, 热点灯, 金钱卡, 显身卡, 匿名卡, 抢沙发, 提升卡, 沉默卡下一级可获得
道具: 千斤顶
购买后可立即获得
权限: 隐身
道具: 金钱卡, 彩虹炫, 雷达卡, 热点灯, 涂鸦板
本帖最后由 EchoEstelle 于
00:03 编辑
1.由适当的阈值确定：
2.根据数据点的散布图直观地确定类的个数：
3.根据统计量确定分类个数:
(1)R^2统计量：类间的离差平方和所占比例越大，类内的离差平方和比例越小，证明分类效果越好，R^2统计量就是使用类间的离差平方和占所有的离差平方和的比例。
(2)半偏R^2统计量：k+1次合并类后的R^2统计量与k次合并后R^2统计量的差值。
(3)伪F统计量：\[G_t类样品中n_t个样本的离差平方和：W_t=\sum_{i=1}^{n_t}(X_{(i)}^{(t)}-{\bar{X}}^{(t)})'(X_{(i)}^{(t)}-{\bar{X}}^{(t)})\]
\[所有样品的总离差平方和T=\sum_{t=1}^{k}\sum_{i=1}^{n_t}(X_{(i)}^{(t)}-\bar{X})'(X_{(i)}^{(t)}-\bar{X})\]
\[所有k个分类下各自样本离差平方和的和：P_k=\sum_{t=1}^{k}W_t\]
\[表示类间偏差平方和：B_k=\sum_{t=1}^{k} n_t({\bar{X}}^{(t)}-\bar{X})'({\bar{X}}^{(t)}-\bar{X})\]
\[R^2统计量：\frac{B_k}{T}=1-\frac{P_k}{T} \]
\[合并类G_k与G_L成G_M后类内离差平方和增值：{B_{KL}}^2=W_M-(W_K+W_L)\]
\[半偏R^2统计量：{B_{KL}}^2/T={R_{k+1}}^2-{R_k}^2\]
\[伪F统计量：伪F_k=\frac{(T-P_k)/(k-1)}{P_k/(n-k)}=\frac{B_k}{P_k}\frac{n-k}{k-1}\]
(4)伪t^2统计量：不具有t^2那样的分布性质
\[伪t^2=\frac{{B_{KL}}^2}{(W_K+W_L)/(n_K+n_L-2)}\]
4.根据谱系图确定分类个数的准则：
A.各类重心的距离必须很大
B.确定的类中，各类所包含的元素都不要太多
C.类的个数必须符合实用目的
D.若采用集中不同的聚类方法处理，则在各自的聚类途中因发现相同的类。
考虑将重心转移到不同集合来考察离差组成的关系，有总的离差和，类上的离差和，类重组导致的离差和的变更等等。
支持楼主：、
购买后，论坛将把您花费的资金全部奖励给楼主，以表示您对TA发好贴的支持
载入中......
我非我见我释我是我非我
EchoEstelle 发表于
<font color="#.由适当的阈值确定：
2.根据数据点的散布图直观地确定类的个数：
3.根据统计量确定分类个数:
谢谢分享
无限扩大经管职场人脉圈！每天抽选10位免费名额，现在就扫& 论坛VIP& 贵宾会员& 可免费加入
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
如有投资本站或合作意向，请联系（010-）；
邮箱：service@pinggu.org
投诉或不良信息处理：（010-）
京ICP证090565号
论坛法律顾问：王进律师> 数据挖掘之聚类分析学习笔记(3)主要聚类方法的分类算法的选择取决于数据的类型，聚类的目的和应用大体
数据挖掘之聚类分析学习笔记(3)主要聚类方法的分类算法的选择取决于数据的类型，聚类的目的和应用大体
ggyydgq & &
发布时间： & &
浏览：73 & &
回复：0 & &
悬赏：0.0希赛币
数据挖掘之聚类分析学习笔记(3)
　　主要聚类方法的分类
　　算法的选择取决于数据的类型， 聚类的目的和应用
　　大体上，主要的聚类算法可以划分为如下几类：
　　划分方法（partitioning methods）：给定一个n 个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k&=n。也就是说，它将数据划分为k 个组，同时满足如下的要求：（1）每个组至少包含一个对象；（2）每个对象必须属于且只属于一个组。注意在某些模糊划分技术中第二个要求可以放宽。
　　给定k，即要构建的划分的数目，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是：在同一个类中的对象之间的距离尽可能小，而不同类中的对象之间的距离尽可能大。
　　为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方法：（1）k-means 算法，在该算法中，每个簇用该簇中对象的平均值来表示。（2）k-medoids 算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。
　　层次的方法（hierarchical methods）：层次的方法对给定数据集合进行层次的分解。根据层次的分解。如何形成，层次的方法可以被分为凝聚的或分裂的方法。
　　凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后继续地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。
　　层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（1）在每层划分中，仔细分析对象间的联接，例如CURE 和Chameleon 中的做法。（2）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。
　　基于密度的方法：绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪音”数据，发现任意形状的簇。
　　DBSCAN 是一个有代表性的基于密度的方法，它根据一个密度阈值来控制簇的增长。OPTICS是另一个基于密度的方法，它为自动的，交互的聚类分析计算一个聚类顺序。
　　基于网格的方法（grid-based methods）：基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。
　　这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STING 是基于网格方法的一个典型例子。CLIQUE 和WaveCluster 这两种算法既是基于网格的，又是基于密度的
　　基于模型的方法（model-based methods）：基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳匹配。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据和孤立点，从而产生健壮的聚类方法。
　　划分方法（partitioning methods）
　　给定一个包含n 个数据对象的数据库，以及要生成的簇的数目k，一个划分类的算法将数据对象组织为k 个划分（k≤n），其中每个划分代表一个簇。通常会采用一个划分准则（经常称为相似度函数，similarity function），例如距离，以便在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。
　　算法：k-means。
　　输入：簇的数目k 和包含n 个对象的数据库。
　　输出：k 个簇，使平方误差最小。
　　方法：
　　（1） 任意选择k 个对象作为初始的簇中心；
　　（2） repeat
　　（3） 根据与每个中心的距离，将每个对象赋给“最近”的簇；
　　（4） 重新计算每个簇的平均值；
　　（5） until 不再发生变化
　　基于质心（centroid）的技术：k-Means 方法
　　k-means 算法以k 为参数，把n 个对象分为k 个簇，以使类内具有较高的相似度，而类间的相似度最低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。
　　“k-means 算法是怎样工作的？”k-means 算法的处理流程如下。首先，随机地选择k 个对象，每个对象初始地代表了一个簇中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。
　　这个算法尝试找出使平方误差函数值最小的k 个划分。当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度是O（nkt），n 是所有对象的数目，k 是簇的数目，t 是迭代的次数。通常地，k$<$n，且t$<$n。这个算法经常以局部最优结束。
　　但是，k-means方法只有在簇的平均值被定义的情况下才能使用。这可能不适用于某些应用，例如涉及有分类属性的数据。要求用户必须事先给出k（要生成的簇的数目）可以算是该方法的一个缺点。K-means方法不适合于发现非凸面形状的簇，或者大小差别很大的簇。而且，它对于“噪音”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。
　　“k-medoids 算法在大数据集合上的效率如何？”典型的k-medoids 算法，如PAM，对小的数据集合非常有效，但对大的数据集合没有良好的可伸缩性。为了处理较大的数据集合，可以采用一个基于样本的方法CLARA（Clustering LARge Applications）。
　　CLARA 的主要思想是：不考虑整个数据集合，选择实际数据的一小部分作为数据的样本。然后用PAM 方法从样本中选择代表对象。如果样本是以非常随机的方式选取的，它应当足以代表原来的数据集合。从中选出的代表对象很可能与从整个数据集合中选出的非常近似。CLARA 抽取数据集合的多个样本，对每个样本应用PAM 算法，返回最好的聚类结果作为输出。
　　层次方法
　　一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上，还是自顶向下形成，层次的聚类方法可以进一步分为凝聚（agglomerative）和分裂(divisive)层次聚类。一个纯粹的层次聚类方法的聚类质量受限于如下特点：一旦一个合并或分裂被执行，就不能修正。最近的研究集中于凝聚层次聚类和迭代重定位方法的集成。
　　一般来说，有两种类型的层次聚类方法：
　　凝聚的层次聚类：这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上有所不同。
　　分裂的层次聚类：这种自顶向下的策略与凝聚的层次聚类不同，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件，例如达到了某个希望的簇数目，或者两个最近的簇之间的距离超过了某个阈值。
　　在凝聚或者分裂的层次聚类方法中，用户能定义希望得到的簇数目作为一个结束条件。
　　四个广泛采用的簇间距离度量方法如下：
　　最小距离：dmin(Ci,Cj) = min p∈Ci,p’∈Cj |p-p’|
　　最大距离：dmax(Ci,Cj) = max p∈Ci,p’∈Cj |p-p’|
　　平均值的距离：dmean(Ci,Cj) = | mI - mj |
　　平均距离：davg(Ci,Cj) =Σ p∈Ci Σp’∈Cj |p-p’|
　　这里|p-p’|是两个对象p 和p’之间的距离，mI 是簇Ci 的平均值，而nI 是簇Cj 中对象的数目。
　　基于密度的方法
　　为了发现任意形状的聚类结果，提出了基于密度的聚类方法。这类方法将簇看作是数据空间中由低密度区域分割开的高密度对象区域。
　　DBSCAN:一个基于密度和高密度的连结区域的聚类算法
　　DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有“噪音”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。
　　基于密度的聚类的基本想法涉及一些新的定义。我们先给出这些定义，然后用一个例子加以说明。
　　n 一个给定对象周围半径e内的区域称为该对象的e –邻域。
　　n 如果一个对象的e–邻域至少包含最小数目MinPts 的对象，那么该对象称为核心对象。
　　n 给定一个对象集合D，如果p 是在q 的e–邻域内，而q 是一个核心对象，我们说对象p 从对象q 出发是直接密度可达的，。
　　n 如果存在一个对象链p1,p2,…,pn，p1=q， pn=p，对pi∈ D，1≤i≤n，pi+1 是从pi 关于e和 MinPts直接密度可达的，则对象p 是从对象q 关于e和MinPts 密度可达的(density-reachable)。
　　n 如果对象集合D 中存在一个对象o，使得对象p 和q 是从o 关于e和MinPts 密度可达的，那么对象p 和q 是关于e和MinPts 密度相连的（density-connected）。
　　密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。只有核心对象之间是相互密度可达的。不过，密度相连性是一个对称的关系。
　　基于网格的方法
　　基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中每一维上的单元数目。
　　基于网格方法的有代表性的例子包括STING，它利用了存储在网格单元中的统计信息；
　　WaveCluster，它用一种小波转换方法来聚类对象；CLIQUE，它是在高维数据空间中基于网格和密度的聚类方法。
　　STING：统计信息网格(STatistical INformation Grid)
　　STING 是一个基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值，最大值，和最小值）被预先计算和存储。这些统计变量可以方便下面描述的查询处理使用。
　　“这些统计信息怎样用于回答查询？”统计变量的使用可以以自顶向下的基于网格的方法。首先，在层次结构中选定一层作为查询处理的开始点。通常，该层包含少量的单元。对当前层次的每个单元，我们计算置信度区间（或者估算其概率），用以反映该单元与给定查询的关联程度。不相关的单元就不再考虑。低一层的处理就只检查剩余的相关单元。这个处理过程反复进行，直到达到最底层。此时，如果查询要求被满足，那么返回相关单元的区域。否则，检索和进一步的处理落在相关单元中的数据，直到它们满足查询要求。
　　“与其它聚类算法相比，STING 有什么优点？”STING 有几个优点：（1）由于存储在每个单元中的统计信息描述了单元中数据的与查询无关的概要信息，所以基于网格的计算是独立于查询的；
　　（2）网格结构有利于并行处理和增量更新；（3）该方法的效率很高：STING 扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O（n），n 是对象的数目。在层次结构建立后，查询处理时间是O（g），这里g 是最底层网格单元的数目，通常远远小于n。
　　WaveCluster：采用小波变换聚类
　　WaveCluster 是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原始的特征空间，在变换后的空间中找到密集区域。
　　在该方法中，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇总信息适合于在内存中进行多分辨率小波变换使用，以及随后的聚类分析。
　　“什么是小波变换？”小波变换是一种信号处理技术，它将一个信号分解为不同频率的子波段。
　　通过应用一维小波变换n 次，小波模型可以应用于n 维信号。在进行小波变换时，数据被变换以在不同的分辨率层次保留对象间的相对距离。这使得数据的自然聚类变得更加容易区别。通过在新的空间中寻找高密度区域，可以确定聚类。
　　“为什么小波变换对聚类是有用的？”它主要有如下的优点：
　　它提供了没有监控的聚类。它采用了hat-shape 过滤，强调点密集的区域，而忽视在密集区域外的较弱的信息。这样，在原始特征空间中的密集区域成为了附近点的吸引点（attractor），距离较远的点成为抑制点（inhibitor）。这意味着数据的聚类自动地显示出来，并“清理”了周围的区域。这样，小波变换的的另一个优点是能够自动地排除孤立点。
本问题标题：
本问题地址：
温馨提示：本问题已经关闭，不能解答。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&}