方差辗转的软集参数约简算法

计算机工程与科学

方差辗转的软集参数约简算法

林连海1,田立勤1,2,蔡铭楷1,李升宏1

（1.青海师范大学计算机学院,青海西宁 810008;2.华北科技学院计算机学院,河北廊坊 065201）

收稿日期:2019-09-03 修回日期:2019-11-26 出版日期:2020-02-25 发布日期:2020-02-25
基金资助:
国家重点研发计划(2018YFC0808306);青海省物联网重点实验室(2017-ZJ-Y21);河北省物联网监控工程技术研究中心(3142018055);河北省重点研发计划项目(19270318D)

A variance toss algorithm for parameter reduction of soft set

LIN Lian-hai1,TIAN Li-qin1,2,CAI Ming-kai1,LI Sheng-hong1

（1.School of Computer Science,Qinghai Normal University,Xining 810008;

2.School of Computer Science,North China Institute of Science and Technology,Langfang 065201,China）

Received:2019-09-03 Revised:2019-11-26 Online:2020-02-25 Published:2020-02-25

摘要/Abstract

摘要：

软集是一种处理不确定数据的理论、工具，通常用于决策论中。软集的参数约简是指删除对决策几乎没有影响的冗余参数，自从0-1线性规划算法提出以来，软集的参数约简问题基本得到了解决，但0-1线性规划算法实现复杂，需要依赖整数规划算法。在此，考虑软集的实际应用背景，将软集与概率论结合，设计出一个在大数据背景下的软集参数约简方法——方差辗转法，该算法的时间复杂度为O(m2n)，而0-1线性规划通常视为NP难问题。方差辗转法实现简单，在物集（或全集）较小，不超过属性集大小的2倍时，效果较差，但随着物集（或全集）大小的增长，效率会逐步上升，最终运算效率会全面优于 0-1线性规划算法的，对于约简稠密度高的软集效率会更高。

关键词: 软集, 参数约简, 概率论, 方差辗转法, 大数据

Abstract:

Soft set is a theory and tool for dealing with uncertain data. It is usually used in decision theory. The parameter reduction of soft set refers to the removal of redundant parameters that have little effect on decision-making. Since the 0-1 linear programming algorithm was proposed, the problem of parameter reduction of soft set has been basically solved, but the implementation of the 0-1 linear programming algorithm is complex and relies on the integer programming algorithm. Here, considering the practical application background of soft set, combining soft set with probability theory, a soft set parameter reduction method in the context of big data, called the variance toss algorithm, is designed. The time complexity of this algorithm is O(m2n), and 0-1 linear programming is usually regarded as a NP-hard problem. The variance toss algorithm is simple to implement. When the object set (or the complete set) is small and less than twice the size of the attribute set, the effect is poor. However, as the size of the object set (or the complete set) increases, the efficiency will gradually increase, and the final computing efficiency will be better than the 0-1 linear programming algorithm. It has higher efficiency for the soft set with high reduction density.

Key words: soft set, parameter reduction, probability theory, variance toss algorithm, big data

林连海1,田立勤1,2,蔡铭楷1,李升宏1. 方差辗转的软集参数约简算法[J]. 计算机工程与科学.

LIN Lian-hai1,TIAN Li-qin1,2,CAI Ming-kai1,LI Sheng-hong1. A variance toss algorithm for parameter reduction of soft set[J]. Computer Engineering & Science.

[1]	陈侨安1，李峰1，曹越1，龙明盛1,2. 基于运行数据分析的Spark任务参数优化[J]. J4, 20160101, 38(01): 11-19.
[2]	钟权, 陈志广, 高蓝光. EMRI-Tree：面向多分辨率可视化的层次式数据结构[J]. 计算机工程与科学, 2024, 46(05): 776-784.
[3]	杨浩艺, 陈微, 姚泽欢, 谭郁松, 李非. 基于转录组学数据的抗真菌药物预测方法研究[J]. 计算机工程与科学, 2023, 45(02): 246-251.
[4]	葛旭冉, 刘洋, 陈志广, 肖侬. 基于MPI的并行大数据集生成器[J]. 计算机工程与科学, 2022, 44(07): 1152-1161.
[5]	刘世缘, 李云春, 陈晨, 杨海龙. 面向大数据存储的主动与被动相结合的性能评测方法体系结构与实现[J]. 计算机工程与科学, 2022, 44(04): 584-593.
[6]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[7]	吕高锋, 王玉鹏, 杨鎔嘉, 唐竹. 基于聚合的FlowRadar网络数据采集加速模型设计[J]. 计算机工程与科学, 2022, 44(02): 220-226.
[8]	张元鸣, 虞家睿, 陆佳炜, 高飞, 肖刚. 基于Spark Streaming的视频大数据并行处理方法[J]. 计算机工程与科学, 2021, 43(10): 1736-1743.
[9]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[10]	刘亚波, 吴秋轩. 基于长短时记忆网络的电商大数据同一性标定[J]. 计算机工程与科学, 2021, 43(03): 407-415.
[11]	李琼, 宋振龙, 袁远, 谢徐超. 一种基于NVMeoF存储池的分域共享并发存储架构[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1711-1719.
[12]	马满福1,2，员欣淼1,2，李勇1,2，刘元喆1,2，王常青3. 虚拟空间中社会分层行为研究[J]. 计算机工程与科学, 2020, 42(05): 803-811.
[13]	覃福钿,李晶. 大数据对高校教学研的影响与探索[J]. 计算机工程与科学, 2019, 41(增刊S1): 238-241.
[14]	陈月娟. 大数据时代高校图书馆数字阅读平台研究与实践[J]. 计算机工程与科学, 2019, 41(增刊S1): 245-248.
[15]	翟俊海1,2，齐家兴1,2,沈矗1,2,宋丹丹1,2,王谟瀚1,2,田石1,2. 基于MapReduce和Spark的大数据主动学习比较研究[J]. 计算机工程与科学, 2019, 41(10): 1715-1722.