加权三支决策增量软聚类算法及性能分析
发布时间：2021-03-21 16:00
现有的增量聚类算法虽然解决了数据增量和类簇重叠问题,但在距离度量时没有考虑属性重要度不同,且普遍拥有较高的时间复杂度。针对以上问题,提出一种基于属性重要度的加权三支决策增量软聚类算法（W-TIOC-TWD算法）,将属性重要度考虑到距离度量中,弥补了现有算法在聚类过程中将所有属性的重要程度视为相等的不足。该算法还引入离群点概念,降低了算法的时间复杂度。基于人工数据集和UCI数据集的实验结果表明,W-TIOC-TWD算法的聚类准确率优于比较算法。
【文章来源】：软件导刊. 2019,18(08)
【文章页数】：8 页
【部分图文】：
TIOC-TWD算法流程TIOC-TWD算法能同时解决增量聚类和重叠聚类问
第8期图2W-TIOC-TWD算法流程2.2.2创建代表点搜索树算法（算法2）树结构具有简单、快速、易查找和更新的特点，适合处理动态增量问题。搜索树的创建由属性重要度大小确定，采用自上向下的方式构建。本算法树结构节点由若干个代表点组成，每个树节点代表了这些代表点所处的数据空间区域。本文在建立搜索树时根据信息熵（公式4）确定属性优先程度，信息熵值越大其所对应属性的模糊程度越高，需要根据更多信息确定。2.2.3增量更新算法（算法3）针对新到来的增量数据提出增量更新算法。该算法由3部分组成：①根据算法1中代表点的寻找方法寻找增量数据代表点；②利用算法2创建的代表点搜索树，寻找增量数据代表点的邻居代表点；③对发生变化的代表点及代表区域进行更新，即更新代表点搜索树和代表点关系图。增量更新算法与原算法不同之处是，增量数据各属性的权重由初始数据集和增量数据集共同组成的数据集整体确定。2.2.4算法性能分析为降低算法的时间复杂度，提高算法效率，本文提出离群点这一概念，下面介绍隔离离群点方法对算法性能的影响。算法1是加权静态重叠聚类算法，设数据块大小为h，数据属性个数为m，代表点总数为|R|，则计算距离矩阵及寻找数据对象邻居所需时间为O(n2)，根据邻居个数数据对象的排序时间为O(nlog(n))。假设代表点代表区域中的数据对象个数为p，则寻找代表点所需时间为O(||R*p*m+nlog(n))，创建代表点关系图所需时间为O(2*||R2)。通过计算发现，寻找代表点及创建代表点关系图的时间复杂度均与|R|的大小直接相关。由此可知，通过隔离离群点的方法可使|R|变小，从而降低寻找代表点及创建代表点关
第8期集和增量数据集两个部分。随机选取真实数据集60%数据作为初始训练数据集，剩余40%的数据分别均分为4组和2组，模拟连续4次每次10%的数据增量实验，以及连续2次每次20%的数据增量实验，具体增量数据流如图3和图4所示。UU1U2U3U4图3连续4次10%增量数据流UU1U2图4连续两次20%增量数据流第二组实验参数采用0.1为间隔的插值分析方法进行调整，参数的取值范围［0，1］，W-TIOC-TWD算法采用δ、α、β三个参数最优值，见表2。3.3评价指标在第二组定量实验中，用准确率作为评价指标对比本文算法与比较算法的性能。定义12准确率（Accuracy）：设样本集X包括k个类，准确率计算公式如下：Accuracy=i=1kai||X（8）其中，ai表示被正确聚类到类Ci中的对象数，||X表示集合中包含的元素数。表2参数最优值数据集LetterABCLetterAGIBanknotePendigists1234Pendigists1469Waveformδ0.250.200.230.180.190.26α0.230.250.380.340.260.35β0.050.050.040.10.10.043.4实验结果及分析3.4.1人工数据集实验结果及分析增量数据到来时，本文算法对类簇增长、合并、发现新类簇等处理能力实验结果如图5-图7所示。由图5和图6可知，类2的数据个数随着增量数据的到来而增长。由图7和图8可知，随着增量数据的到来，类1和类2的边界域数据个数超过一定量时，两个类合并成一个类。由图9和图10可知，增量数据到来时，算法能够识别出新产生的类2。结论1：通过在人工数据集的实验可?
【参考文献】：
期刊论文
[1]基于k-means的自动三支决策聚类方法[J]. 于洪,毛传凯. 计算机应用. 2016(08)
[2]大数据聚类算法综述[J]. 海沫. 计算机科学. 2016(S1)
[3]不确定度模型下数据流自适应网格密度聚类算法[J]. 刘卓,杨悦,张健沛,杨静,初妍,张泽宝. 计算机研究与发展. 2014(11)
[4]基于信息熵的专家聚类赋权方法[J]. 周漩,张凤鸣,惠晓滨,李克武. 控制与决策. 2011(01)
[5]基于相对密度的增量式聚类算法[J]. 刘青宝,侯东风,邓苏,张维明. 国防科技大学学报. 2006(05)
本文编号：3093147
【文章来源】：软件导刊. 2019,18(08)
【文章页数】：8 页
【部分图文】：
TIOC-TWD算法流程TIOC-TWD算法能同时解决增量聚类和重叠聚类问
第8期图2W-TIOC-TWD算法流程2.2.2创建代表点搜索树算法（算法2）树结构具有简单、快速、易查找和更新的特点，适合处理动态增量问题。搜索树的创建由属性重要度大小确定，采用自上向下的方式构建。本算法树结构节点由若干个代表点组成，每个树节点代表了这些代表点所处的数据空间区域。本文在建立搜索树时根据信息熵（公式4）确定属性优先程度，信息熵值越大其所对应属性的模糊程度越高，需要根据更多信息确定。2.2.3增量更新算法（算法3）针对新到来的增量数据提出增量更新算法。该算法由3部分组成：①根据算法1中代表点的寻找方法寻找增量数据代表点；②利用算法2创建的代表点搜索树，寻找增量数据代表点的邻居代表点；③对发生变化的代表点及代表区域进行更新，即更新代表点搜索树和代表点关系图。增量更新算法与原算法不同之处是，增量数据各属性的权重由初始数据集和增量数据集共同组成的数据集整体确定。2.2.4算法性能分析为降低算法的时间复杂度，提高算法效率，本文提出离群点这一概念，下面介绍隔离离群点方法对算法性能的影响。算法1是加权静态重叠聚类算法，设数据块大小为h，数据属性个数为m，代表点总数为|R|，则计算距离矩阵及寻找数据对象邻居所需时间为O(n2)，根据邻居个数数据对象的排序时间为O(nlog(n))。假设代表点代表区域中的数据对象个数为p，则寻找代表点所需时间为O(||R*p*m+nlog(n))，创建代表点关系图所需时间为O(2*||R2)。通过计算发现，寻找代表点及创建代表点关系图的时间复杂度均与|R|的大小直接相关。由此可知，通过隔离离群点的方法可使|R|变小，从而降低寻找代表点及创建代表点关
第8期集和增量数据集两个部分。随机选取真实数据集60%数据作为初始训练数据集，剩余40%的数据分别均分为4组和2组，模拟连续4次每次10%的数据增量实验，以及连续2次每次20%的数据增量实验，具体增量数据流如图3和图4所示。UU1U2U3U4图3连续4次10%增量数据流UU1U2图4连续两次20%增量数据流第二组实验参数采用0.1为间隔的插值分析方法进行调整，参数的取值范围［0，1］，W-TIOC-TWD算法采用δ、α、β三个参数最优值，见表2。3.3评价指标在第二组定量实验中，用准确率作为评价指标对比本文算法与比较算法的性能。定义12准确率（Accuracy）：设样本集X包括k个类，准确率计算公式如下：Accuracy=i=1kai||X（8）其中，ai表示被正确聚类到类Ci中的对象数，||X表示集合中包含的元素数。表2参数最优值数据集LetterABCLetterAGIBanknotePendigists1234Pendigists1469Waveformδ0.250.200.230.180.190.26α0.230.250.380.340.260.35β0.050.050.040.10.10.043.4实验结果及分析3.4.1人工数据集实验结果及分析增量数据到来时，本文算法对类簇增长、合并、发现新类簇等处理能力实验结果如图5-图7所示。由图5和图6可知，类2的数据个数随着增量数据的到来而增长。由图7和图8可知，随着增量数据的到来，类1和类2的边界域数据个数超过一定量时，两个类合并成一个类。由图9和图10可知，增量数据到来时，算法能够识别出新产生的类2。结论1：通过在人工数据集的实验可?
【参考文献】：
期刊论文
[1]基于k-means的自动三支决策聚类方法[J]. 于洪,毛传凯. 计算机应用. 2016(08)
[2]大数据聚类算法综述[J]. 海沫. 计算机科学. 2016(S1)
[3]不确定度模型下数据流自适应网格密度聚类算法[J]. 刘卓,杨悦,张健沛,杨静,初妍,张泽宝. 计算机研究与发展. 2014(11)
[4]基于信息熵的专家聚类赋权方法[J]. 周漩,张凤鸣,惠晓滨,李克武. 控制与决策. 2011(01)
[5]基于相对密度的增量式聚类算法[J]. 刘青宝,侯东风,邓苏,张维明. 国防科技大学学报. 2006(05)
本文编号：3093147
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3093147.html
