技术领域
本发明涉及数据处理技术领域,特别是涉及一种基于信息增益权重的增量聚类方法及装置。
背景技术
作为统计学的一个分支,聚类是一种通过观察学习不断调整自身模型的机器学习方法,当前已被广泛应用于网络检测入侵、图像识别等领域。随着大数据时代的来临,为了克服传统聚类算法在大规模数据计算下的局限性,技术人员利用已有的算法模型进行增量改造,提出了增量聚类方法:当有一批聚类结果时,若新增加数据,则只对新增数据进行聚类,并对已有的聚类结果进行增量式修改,无需对新增数据后的整个数据集进行重新聚类。
现有的聚类方法包括利用扩展矢量化方法对新增的数据进行聚类,首先设定一个阈值,当新增数据与现有中心点的最小距离小于这个阈值时,就将其归入到现有类中,否则其作为一个单独的类对象,由于该方法需人为指定阈值,往往鲁棒性较差。
发明内容
针对上述技术问题,本发明提供一种基于信息增益权重的增量聚类方法及装置,通过将各类别的最大半径设定为增量阈值,消除人工设定阈值带来的影响,有效提高方法鲁棒性。
本发明实施例提供一种基于信息增益权重的增量聚类方法,包括:
根据初始数据属性特征的信息增益权重,计算各个特征的分类贡献率;
根据所述分类贡献率分别计算所述初始数据到初始聚类中心的类内距离,并将所述类内距离小于距离阈值的类进行迭代合并,得到聚类结果,所述聚类结果包括各类别的聚类中心和最大类内距离;
根据所述分类贡献率分别计算新增数据点到所述聚类中心的距离,确定最小距离和对应聚类中心;
当所述最小距离小于等于对应聚类中心的最大类内距离时,将所述新增数据点合并至所述对应聚类中心的类别内,当所述最小距离大于对应聚类中心的最大类内距离时,则确定为一个单独类别。
在某一个实施例中,所述初始数据属性特征的信息增益权重根据初始数据的信息熵确定。
在某一个实施例中,所述各个特征的分类贡献率∝
其中W(T)为属性特征T的信息增益权重。
在某一个实施例中,所述根据所述分类贡献率分别计算所述初始数据到初始聚类中心的类内距离,具体为:
在某一个实施例中,对初始数据属性的连续值进行离散化处理。
在某一个实施例中,所述距离阈值包括初始数据到初始聚类中心的类内距离中最小的类内距离。
本发明实施例还提供一种基于信息增益权重的增量聚类装置,包括:
第一初始化单元,用于根据初始数据属性特征的信息增益权重,计算各个特征的分类贡献率;
第二初始化单元,用于根据所述分类贡献率分别计算所述初始数据到初始聚类中心的类内距离,并将所述类内距离小于距离阈值的类进行迭代合并,得到聚类结果,所述聚类结果包括各类别的聚类中心和最大类内距离;
数据计算单元,用于根据所述分类贡献率分别计算新增数据点到所述聚类中心的距离,确定最小距离和对应聚类中心;
数据聚类单元,用于当所述最小距离小于等于对应聚类中心的最大类内距离时,将所述新增数据点合并至所述对应聚类中心的类别内,当所述最小距离大于对应聚类中心的最大类内距离时,则确定为一个单独类别。
在某一个实施例中,所述初始数据属性特征的信息增益权重根据初始数据的信息熵确定。
在某一个实施例中,所述距离阈值包括初始数据到初始聚类中心的类内距离中最小的类内距离。
本发明实施例还提供一种计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时,实现如上述任一个实施例所述的方法。
相比现有技术,本发明实施例的有益效果在于:
本发明提供的一种基于信息增益权重的增量聚类方法及装置充分考虑不同属性特征对聚类的贡献,利用信息增益比例权重计算数据到聚类中心的距离,并通过将聚类结果中各类别的最大类内距离作为增量数据归类阈值,消除人为指定阈值的影响,提高了增量聚类方法的鲁棒性。
附图说明
为了更清楚地说明本发明的技术方案,下面将对实施方式中所需要使用的附图作简单地介绍,显而易见地,下面描述中的附图仅仅是本发明的一些实施方式,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。
图1是本发明实施例提供的基于信息增益权重的增量聚类方法流程示意图;
图2是本发明实施例提供的基于信息增益权重的增量聚类装置结构示意图。
具体实施方式
下面将结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅仅是本发明一部分实施例,而不是全部的实施例。基于本发明中的实施例,本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例,都属于本发明保护的范围。
应当理解,文中所使用的步骤编号仅是为了方便描述,不对作为对步骤执行先后顺序的限定。
应当理解,在本发明说明书中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本发明。如在本发明说明书和所附权利要求书中所使用的那样,除非上下文清楚地指明其它情况,否则单数形式的“一”、“一个”及“该”意在包括复数形式。
术语“包括”和“包含”指示所描述特征、整体、步骤、操作、元素和/或组件的存在,但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。
术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合,并且包括这些组合。
如图1所示,本发明一个实施例提供一种基于信息增益权重的增量聚类方法,包括下述步骤。
S11:根据初始数据属性特征的信息增益权重,计算各个特征的分类贡献率。
在该实施例中,对初始数据属性的连续值进行离散化处理。
在该实施例中,首先设置聚类参数,包括初始数据集合X,属性集合T和分类类别Y,其中T={T
对于初始数据集合X,可根据分类类别Y的不同取值对应划分为集合C,C={C
在该实施例中,对于初始数据的特征T
具体地,信息增益权重W(T
IG(T
式中,
式中
对于IS(T
进一步地,根据信息增益权重W(T
S12:根据所述分类贡献率分别计算所述初始数据到初始聚类中心的类内距离,并将所述类内距离小于距离阈值的类进行迭代合并,得到聚类结果,所述聚类结果包括各类别的聚类中心和最大类内距离。
在该实施例中,所述距离阈值包括初始数据到初始聚类中心的类内距离中最小的类内距离。
在该实施例中,设定聚类类别为d,并在初始数据集合X中随机选取初始聚类中心集合center,定义center={ct
在迭代过程中,根据下述公式计算初始数据集合X中的数据点x到个初始聚类中心ct
得到所述距离中的最小值Min(dist(x,c
其中更新后的聚类中心ct
当更新后的聚类中心点偏移时,返回执行S12,直到更新后聚类中心点不再偏移或迭代完成,此时记录各类别的最大类内距离。
在该实施例中,利用本次迭代的聚类中心点减去上一次迭代的聚类中心点集合,比较各个差值与聚类精度elig的大小,若各个差值均小于等于elig,则更新后的聚类中心点不发生偏移,迭代结束;若存在差值大于elig,则更新后的聚类中心点发生偏移。
迭代结束后,得到聚类结果,所述聚类结果包括各类别的聚类中心和最大类内距离。
S13:根据所述分类贡献率分别计算新增数据点到所述聚类中心的距离,确定最小距离和对应聚类中心。
在该实施例中,对于新增的数据点x
并根据new_min=Min(dict(x
S14:当所述最小距离小于等于对应聚类中心的最大类内距离时,将所述新增数据点合并至所述对应聚类中心的类别内,当所述最小距离大于对应聚类中心的最大类内距离时,则确定为一个单独类别。
在该实施例中,将最小距离new_min与对应类别的最大类内距离进行比较,当new_min≤最大类内距离时,将该新增的数据点归入该类别中,否则将该新增数据点设定为一个单独的类别。
对于数据集的不同属性,属性的信息增益最大,包含的不确定信息越多,越有益于聚类,本发明实施例通过利用属性特征的信息增益比例权重计算数据到聚类中心的距离,将属性信息增益引入到聚类中,同时通过将聚类结果中各类别的最大类内距离作为增量数据的归类判断阈值,避免了人为指定阈值对聚类效果的影响,有效提高增量聚类方法的鲁棒性。
如图2所示,本发明一个实施例还提供一种基于信息增益权重的增量聚类装置,包括第一初始化单元101、第二初始化单元102、数据计算单元103和数据聚类单元104。
第一初始化单元101用于根据初始数据属性特征的信息增益权重,计算各个特征的分类贡献率。
第二初始化单元102用于根据所述分类贡献率分别计算所述初始数据到初始聚类中心的类内距离,并将所述类内距离小于距离阈值的类进行迭代合并,得到聚类结果,所述聚类结果包括各类别的聚类中心和最大类内距离。
数据计算单元103用于根据所述分类贡献率分别计算新增数据点到所述聚类中心的距离,确定最小距离和对应聚类中心。
数据聚类单元104用于当所述最小距离小于等于对应聚类中心的最大类内距离时,将所述新增数据点合并至所述对应聚类中心的类别内,当所述最小距离大于对应聚类中心的最大类内距离时,则确定为一个单独类别。
上述装置内的各单元之间信息交互、执行过程等内容,由于与本发明方法实施例基于同一构思,具体内容可参见本发明方法实施例中的叙述,此处不再赘述。
本发明实施例还提供一种计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时,实现如上述任一个实施例所述的方法。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程,是可以通过计算机程序来指令相关的硬件来完成,所述的程序可存储于计算机可监听存储介质中,该程序在执行时,可包括如上述各方法的实施例的流程。其中,所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-Only Memory,ROM)或随机存储记忆体(Random AccessMemory,RAM)等。
以上所述是本发明的优选实施方式,应当指出,对于本技术领域的普通技术人员来说,在不脱离本发明原理的前提下,还可以做出若干改进和润饰,这些改进和润饰也视为本发明的保护范围。
机译: 基于关系权重的交通拥堵下因果道路分析的链路聚类方法
机译: 基于关系权重的交通拥堵下因果道路分析链路聚类方法
机译: 依赖标准化随机度量的增量树聚类方法和装置