Exploiting Hybrid Kernel-Based Fuzzy Complementary Mutual Information for Selecting Features
-
摘要:
模糊粗糙集理论目前在数据挖掘和机器学习等领域受到了广泛的关注. 该理论提供了一种能克服离散化问题的有效工具，并能直接应用于数值或混合属性数据. 在模糊粗糙集模型中，定义模糊关系来测量对象之间的相似性，数值属性值不再需要离散化. 模糊粗糙集理论已经被成功应用于许多领域，如属性约简、规则提取、聚类分析和离群点检测. 信息熵被引入到模糊粗糙集理论进行模糊和不确定信息的表示，产生了不同形式的模糊不确定性度量，如模糊信息熵、模糊补熵和模糊互信息等. 然而，大部分所提关于决策的模糊互信息都是非单调的，这可能导致一个不收敛的学习算法. 为此，基于混杂核模糊补熵，定义了关于决策的模糊补互信息，证明了其随特征呈单调性变化. 进而，利用混杂核模糊补互信息探索特征选择方法并且设计了相关的算法. 实验结果展示了在大多数情况下所提算法可以选取更少的特征且能保持或提高分类准确率.
Abstract:Fuzzy rough set theory is currently receiving a lot of attention in the fields of data mining and machine learning. The theory provides an effective tool to overcome the discretization problem and can be applied directly to numerical or mixed attribute data. In the fuzzy rough set model, fuzzy relations are defined to measure the similarity between objects and numerical attribute values no longer need to be discretized. The theory has been successfully applied to many fields such as attribute reduction, rule extraction, cluster analysis and outlier detection. Information entropy has been introduced into fuzzy rough set theory for the representation of fuzzy and uncertainty information, resulting in different forms of fuzzy uncertainty measures such as fuzzy information entropy, fuzzy complementary entropy, and fuzzy mutual information. However, most of the proposed fuzzy mutual information on decisions is non-monotonic, which may lead to a non-convergent learning algorithm. To this end, the fuzzy complementary mutual information on decisions is defined based on the hybrid kernel fuzzy complementary entropy, which is shown to vary monotonically with features. Then, the feature selection method is explored by using the hybrid kernel-based fuzzy complementary mutual information and a corresponding algorithm is designed. Experimental results show that the proposed algorithm can select fewer features and maintain or improve the classification accuracy in most cases.
-
随着信息技术的发展，操作系统、数据库系统等系统软件已广泛应用于医疗、工业、军事、航空航天和能源等关键领域以及人们的日常生活中，是现代社会不可或缺的基础设施. 同时，伴随着人工智能、大数据、云计算等新技术的进步，以及可编程存储器、RDMA（remote direct memory access）网络硬件、可编程交换机等新硬件的涌现，为充分利用硬件支撑上层应用，系统软件的设计与实现不断面临着与时俱进的新要求. 这不仅是对系统软件实践者的挑战，也为系统软件研究带来新的机遇.
与此同时，机器学习方法近年来取得了令人瞩目的进展. 2015年，微软的研究人员使用深度残差网络（deep residual network, ResNet）在ImageNet测试集中达到超越人类表现[1]；2016年，DeepMind的研究人员使用深度强化学习（deep reinforcement learning, DRL）训练出AlphaGo模型并击败了围棋世界冠军李世石[2-3]；2018—2020年，OpenAI的研究人员基于Transformer模型架构[4]提出GPT系列模型[5-7]，并于2022年向公众发布ChatGPT模型，ChatGPT凭借其优秀的对话与推理能力引起社会各界广泛的关注与讨论.
面对构建复杂系统软件的迫切需求和机器学习方法的快速发展，一些系统研究人员开始思考并尝试回答：能否使用机器学习方法来赋能系统软件？近年来，研究领域中出现不少应用机器学习方法于系统软件的尝试，并受到研究人员与从业者的共同关注. 值此之际，本文将讨论使用机器学习方法赋能系统软件的机遇与挑战，介绍将机器学习方法应用于索引结构、键值存储系统、并发控制协议等方面的实践，总结经验与教训，并回顾国内外相关研究，希望为尝试应用机器学习方法的系统软件研究人员与从业者提供参考与帮助.
1. 机器学习方法赋能系统软件的机遇与挑战
随着软硬件环境的不断演变，系统软件的设计与实现日益复杂. 图灵奖得主Lampson[8-9]曾指出，系统软件不仅需要充分利用底层硬件资源为上层应用提供及时与高效的服务，同时还需要保证系统的稳定性和可靠性，并能够快速适应需求与环境的变化. 这些要求为机器学习方法在系统软件中发挥作用带来了新的机遇. 例如，可以使用机器学习方法来优化系统资源的利用和分配，以及实现自适应的系统配置和调整，从而提高系统软件的性能和可靠性. 同时，机器学习方法也可以对系统软件产生的大量运行数据进行分析和挖掘，以优化系统软件的运行效率和性能，从而满足不断增长的应用需求.
然而，机器学习方法赋能系统软件面临4点挑战：
1）面临设计面向系统软件定制化模型的挑战. 系统软件往往有复杂的架构与多样化的功能，以及与常见的机器学习任务所不同的优化目标，因此需要为具体系统和应用场景设计定制化的机器学习模型，以有效地进行优化. 因此，系统研究人员需要深入了解系统软件的工作原理和性能瓶颈，并具备机器学习领域的专业知识和经验，才能设计出合适的模型.
2）面临获取足量且高质量训练数据的挑战. 系统软件所使用的模型训练数据往往需要从系统运行过程中收集而来，但系统的每次运行往往会消耗大量时间与计算资源，而只能产生少量的训练数据，这给获取训练数据带来了成本和效率方面的挑战. 此外，为满足系统软件对稳定性与可靠性的高要求，训练数据往往需要覆盖各种可能的工作负载和异常情况，从而保证训练出的模型具有较好的鲁棒性和泛化能力，这进一步增加训练数据的获取难度.
3）面临降低模型开销对系统性能影响的挑战. 与数据分析等其他应用机器学习方法的场景不同，系统软件对实时性和并发度有极高的要求，因此对于模型执行的效率和响应时间要求非常高. 然而，由于神经网络等机器学习模型通常需要大量的计算资源和时间来执行，这会导致模型的执行开销影响系统软件的性能. 尤其是在嵌入式设备和边缘设备等资源受限的环境中，模型执行开销甚至可能大于使用机器学习方法带来的提升，进而对系统软件造成负面影响.
4）面临消除模型误差对系统正确性影响的挑战. 对于系统软件而言，始终保证系统行为的正确性至关重要. 然而，机器学习模型产生的结果总是伴随着误差，难以提供精确度保证. 因此，如何在使用模型输出时避免产生错误的系统行为也是应用机器学习方法所面临的重大挑战.
2. 机器学习方法赋能系统软件的实践
在系统软件实践者的视角下，机器学习方法可以被简单地看作一种函数近似器[10]. 因此，任何能够被表示为某种函数形式的系统组件都可以被机器学习模型近似拟合. 以数据库查询优化器为例，它的功能可以总结为将输入查询语句进行优化并输出具体的查询执行计划. 因此，一个以查询语句抽象语法树（abstract syntax tree, AST）和数据库内部统计信息为输入，输出物理执行计划的函数就可以表达查询优化器这一系统组件. 通过收集系统运行时查询优化器的真实输入输出以构建训练数据集，这样就使得采用机器学习方法替换这一组件成为可能. 尽管模型会产生误差，但这迈出了用机器学习方法优化关键系统软件组件的第一步.
下一个问题随之而来：哪些函数适合被机器学习方法所近似拟合呢？本节通过介绍上海交通大学并行与分布式系统研究所及相关合作者将机器学习方法应用于系统软件的3个具体案例来探讨这个问题. 本文旨在抛砖引玉，而非给出一个通用的答案.
2.1 机器学习方法在索引结构上的实践
索引结构是包括存储系统在内的许多系统软件中重要的组成部分，它们可以显著提高数据检索的速度和效率，减少系统资源的消耗，从而提升整个系统的性能. 常见的索引结构包括B+树、哈希表及其变种等. 索引结构本质上是一类记录数据存储位置并提供查找能力的数据结构，因此可以用一个以查询键（key）为输入，输出数据位置的函数来表示其功能. 因此，如图1所示，用机器学习方法替代传统索引结构的核心在于使用机器学习模型来近似拟合这一函数.
![]()
图 1 机器学习模型代替索引结构的示意图Figure 1. Illustration of replacing index structures with machine learning models使用机器学习方法近似拟合索引结构函数存在3个难点：1）机器学习模型必须具有高效的执行速度. 因为访问索引结构是存储系统查询处理关键路径的组成部分，机器学习模型推理时间必须是微秒级别才能避免对系统性能造成负面影响. 2）使用模型后，查询结果必须始终准确. 用户期望索引结构查询时返回且只返回匹配查询键数据的存储位置，遗漏数据或返回错误数据位置都会严重影响系统的可靠性. 3）模型必须能够快速适应数据更新. 插入、删除等操作会改变索引结构对查询键的输出，进而改变模型所近似拟合的函数. 如果不能及时更新模型以适应更新后的函数，系统正确性仍无法得到保障.
对于第1个难点，首先对导致模型执行效率低的原因进行分析. 我们发现，模型执行效率低往往是由于使用深度神经网络（deep neural network, DNN）等复杂模型导致，而之所以需要使用复杂模型则是因为所需近似拟合的函数本身较为复杂，需要高容量（capacity）的模型才能够提供足够的精度. 因此，解决模型执行效率问题的核心在于简化所需近似拟合函数的复杂度. 如图2所示，索引函数复杂是因为被索引数据往往是随机分散在存储介质的不同位置上，从而导致索引结构所代表的查询键与数据位置间的映射缺乏规律. 因此，只需要将数据进行排序，并使其连续存放于存储介质中，那么模型所需近似拟合的函数将单调递增，从而使用简单的线性模型就可以较好地对其进行近似. 这一思想最初由Kraska等人[11]提出，并进一步构建了递归模型索引（recursive model index, RMI）架构来索引数据.
![]()
图 2 将数据排序并连续存放可简化被拟合函数Figure 2. Sorting data and storing date continuously simplify the approximated function对于第2个难点，需要为模型误差设计一个后备机制（fallback mechanism）. 具体而言，尽管模型预测的数据位置可能存在误差，但通常情况下预测位置与数据真实位置差距并不大. 考虑到数据本身已经被排序并连续地存放于存储介质中，可以从预测位置出发进行指数搜索（exponential search），通过将当前位置数据与用户给定查询键进行比较，最终定位到数据真实位置. 指数搜索的复杂度为O（log（n）），其中n为模型预测误差. 因此，有了这样的后备机制，只需尽可能提高模型精度以减少指数搜索开销，而不用担心输出错误的查询结果.
对于第3个难点，发现直观的数据更新适应方案要么严重影响系统性能，要么会导致索引结构数据一致性问题. 为了简化索引函数并使用指数搜索来确定数据真实位置，被索引数据需要排序并连续地存储，因此每次数据插入与删除将会涉及到大量数据的移动操作. 就算使用内存作为存储介质，这一过程仍可消耗数秒时间来完成. 同时，数据位置发生改变时，模型也需要及时更新，以保证查询误差始终处于较低状态，这进一步加大了应对数据更新的开销. 对于这一问题，直观的解决方法是为数据修改设计单独的缓存，缓存足够大时在后台异步地完成数据移动与模型更新操作. 尽管这些操作耗费的时间未减少，但它们不再阻塞正常的索引查询与更新.
如图3所示，当后台线程将数据从旧索引的数据数组和缓存拷贝至新索引的数据数组时，前台线程仍然可以对旧索引进行更新操作. 由于后台线程此时仍未完成新索引的构建，新索引的数据数组无法暴露给前台线程，因此当前台线程对已被拷贝至新索引的数据进行更新时，拷贝后的数据并不会被正确更新. 这会导致数据一致性问题，即在后台线程完成新索引构建后，旧索引将被回收，导致用户成功完成的更新消失. 为了解决这个问题，我们提出了两阶段压缩（two-phase compaction）方法来正确进行新索引构建. 简单来说，将后台线程构建新索引的过程分为2个阶段：归并（merge）阶段和拷贝（copy）阶段. 在归并阶段，后台线程将旧索引的数据数组和缓存中的数据按照查询键进行归并排序，并将指向它们的指针存入新索引的数据数组中. 完成归并阶段后，我们使用RCU（read-copy-update）机制将所有前台线程的索引视图迁移至新构建的索引，进入拷贝阶段将新索引的数据数组中的指针替换为其所引用的具体数据. 使用两阶段压缩技术后，只有当所有前台线程均停止通过旧索引修改数据，才会执行数据拷贝，从而避免了直接拷贝数据后被前台线程修改导致的数据不一致问题.
![]()
图 3 通过两阶段压缩更新索引可避免数据一致性问题Figure 3. Updating indexes with two-phase compaction avoids data consistency issue如图4所示，我们的测试表明，将机器学习方法应用于索引结构来构建的XIndex索引结构[12-14]，不仅拥有超越传统索引结构的查询性能，而且在读写负载下具有优秀的可扩展性.
![]()
图 4 在类TPC-C负载下XIndex可扩展性良好且性能优于现有系统Figure 4. XIndex achieves good scalability in a TPC-C style workload and outperforms state-of-the-art baselines2.2 机器学习方法在键值存储系统上的实践
键值存储系统是一类重要的系统软件，它们能够快速地存储和检索大量的键值对数据. 许多大型分布式系统（如分布式数据库）均使用键值存储系统作为存储模块并在其上构建更为复杂的功能.
对于键值存储系统，数据索引效率是决定其性能的关键. 如图5所示，传统客户端服务器模式的键值存储系统中，客户端与服务器以远程过程调用（remote procedure call, RPC）的方式进行通信. 客户端向服务器发送的读写请求需经由服务器端CPU进行处理后再将结果返回给客户端. 随着近年来RDMA技术的发展，客户端与服务器间网络通信能力不断提升[15]. 然而服务器端CPU处理能力却未能获得相匹配的提高，因此这类架构的键值存储系统中服务器端CPU处理请求的性能逐渐成为整个系统的瓶颈. 与此同时，RDMA技术允许客户端直接对服务器端内存进行访问而不需服务器端CPU的参与，这使另一种直接由客户端驱动数据查询的架构成为可能. 在这种架构下客户端将代替原服务器端CPU完成对服务器端所管理的数据进行访问. 然而，服务器端数据往往以树状结构进行组织，以提供按顺序扫描的功能. 若简单地让客户端复刻服务器端CPU进行的查询过程，那对树状数据结构每一层的访问都将需要一次网络往返（network roundtrip）. 这不仅会大大增加查询操作所需的时间，还会加剧对网络带宽资源的消耗.
怎样设计键值存储系统才能充分发挥RDMA技术带来的卓越硬件性能成为我们思考的一个问题. 我们发现，在客户端对服务器端索引结构进行缓存可以有效减少查询时的网络往返，但这种方法会对客户端造成极大的内存空间开销，并在读写负载下导致大量缓存失效（cache invalidation）和缓存未命中（cache miss），引起系统性能下降.
为此，我们提出使用机器学习方法替代客户端的索引结构缓存，并称其为学习缓存（learned cache）. 正如2.1节所提到，机器学习方法可以有效替代传统索引结构，通过模型计算来替代传统索引结构中逐层访问过程，在提供高效查询性能的同时大幅度减少索引结构所需内存空间. 实现这一想法最大的难点来自于真实负载下数据的动态变化. 我们在XIndex中使用缓存来应对删除和插入操作，但这种思想难以用于RDMA键值存储系统. 首先，服务器端引入额外的缓存结构会导致客户端查询时额外的网络往返，从而严重增加查询延迟. 其次，对写操作有较好支持的缓存结构通常也是树状的，很难在客户端缓存这样快速变化的缓存结构. 最后，对数据和模型的重构会中断客户端发起的RDMA远程访问，并导致客户端的学习缓存完全失效.
为解决这些问题，我们提出了一种混合的系统架构并构建了原型系统XStore[16,17]. 如图6所示，该架构保留了服务器端的B+树索引结构以处理动态工作负载，并在客户端上使用学习缓存来处理静态工作负载. 对于get（）, scan（）等只读请求，客户端首先使用学习缓存预测查询键的位置范围，然后通过一次RDMA读操作获取这个范围的数据. 最后，客户端在本地获取的数据范围内搜索找到数据的实际位置，并使用另一次RDMA读操作获取完整数据. 对于update（）, insert（）, delete（）等写操作，客户端将使用传统RPC的方式将请求发给服务器. 服务器首先通过遍历B+树索引确定查询键的位置，然后插入新的键值对. 系统将在后台重新训练被更新树节点所对应的模型，客户端会根据需求独立地从服务器端获取新的学习缓存.
如图7所示，测试表明XStore能够在只读负载下每秒处理8000万次请求，在读写负载下每秒处理5300万次请求，相比于当前最先进的RDMA键值存储系统分别实现了高达5.9倍和3.5倍的提升.
![]()
图 7 在只读和读写负载下XStore性能均优于现有系统Figure 7. XStore outperforms state-of-the-art baselines in both read-only workload and read-write workload2.3 机器学习方法在并发控制协议上的实践
并发控制协议是并发系统高效执行用户请求并保证执行结果正确的关键组件. 在数据库系统中并发控制协议是保证用户事务隔离性（isolation）的核心，它通过协调并发事务中各个操作的执行，来保证高效的事务执行与正确的事务语义，例如可串行化（serializability）. 目前，为了最大化并发系统的性能，研究人员通常会针对具体应用负载场景手动设计并发控制协议. 但是，当工作负载发生变化时，原有的针对性并发控制协议优化将难以发挥作用，甚至低于其他简单的经典算法.
能否利用机器学习方法的适应能力来构建能够适配各种工作负载的并发控制协议是我们思考的一个问题. 首先，需要寻找能够表示并发控制协议的函数抽象. 受到强化学习的启发，我们发现尽管目前存在多种风格的并发控制协议，但它们都可以被简单地视为一个以事务当前执行状态为输入，并输出这个事务下一个行动（action）的函数. 这为我们应用机器学习方法构建并发控制协议奠定了基础.
使用机器学习方法近似拟合这个函数存在3个难点：1）如何表示事务的执行状态. 选择合适的表示方式需要考虑模型的执行开销、收集训练数据的日志开销，以及不同表示方式所对应的状态空间大小等. 因此需要一个足够精炼的表示方式以避免潜在的性能问题. 2）如何定义并表示事务的行动. 类似于执行状态表示方式，事务行动的定义与表示需要足够精炼. 此外，事务行动的定义与表示还需要覆盖现有并发控制协议所提供的行动，以保证我们学习的并发控制协议能够拟合现有算法. 3）如何保证近似拟合得到的并发控制协议的正确性. 例如保证被协调的事务执行结果可串行化.
对于第1个难点，我们希望状态表示方式能够区分出需要不同行动的事务状态. 经过探索，发现使用由事务类型和操作ID组成的元组是一个足够简单并能够精确区分事务执行所需执行的不同操作的表达方式. 例如，在TPC-C负载中，可以通过New-Order事务类型及其第2个操作来表示当前事务执行状态.
对于第2个难点，我们希望行动的定义和表示能够足够细粒度地控制并发事务的交错执行，并且能够对大部分现有并发控制协议进行编码. 经过分析发现，行动定义应包括以下决定：是否需要等待以及等待多久、选取数据的哪个版本来完成读操作、是否将未提交的脏写（dirty write）变得可见、立即对事务执行进行验证还是在提交前再验证等. 最终，将这些可能的行动以类似独热编码（one-hot encoding）的方式构建了行动空间.
至此，我们将学习的并发控制协议表示为由事务状态和行动构成的二维表格形式（见图8），使用遗传算法在不同工作负载下学习适配当前负载的并发控制策略（见图9），并构建了原型系统Polyjuice[18].
![]()
图 8 Polyjuice使用的并发控制策略表格表示方式Figure 8. Concurrency control policy table representation used in Polyjuice![]()
图 9 Polyjuice用遗传算法为特定工作负载训练并发控制策略Figure 9. Polyjuice uses the evolutionary algorithm to train concurrency control policies for specific workloads对于第3个难点，我们使用数据库系统中常见的事务执行验证机制作为机器学习并发控制协议的后备机制，从而保证无论模型产生了怎样的并发控制策略，都只有在符合用户指定事务语义的执行结果时才能提交. 具体而言，我们使用了一个类似于Silo数据库的验证机制[19].
经测试，我们发现Polyjuice能在不同的工作负载下实现高于针对这些负载进行优化的并发控制协议的性能，如图10所示. 仔细观察Polyjuice的事务协调策略，我们发现通过遗传算法学习，Polyjuice能够输出现有并发控制协议无法做到的更高效的事务交错执行方式，如图11所示. 这进一步证明了机器学习方法在为系统软件探索策略空间方面的巨大潜力.
![]()
图 10 不同工作负载下Polyjuice都能优于现有并发控制协议Figure 10. Polyjuice outperforms existing concurrency control protocols under different workloads![]()
图 11 Polyjuice能更高效地交错执行TPC-C负载的事务Figure 11. Polyjuice can interleave transactions more efficiently in the TPC-C workload3. 机器学习方法赋能系统软件的经验与教训
将机器学习方法应用到系统软件的设计与实现中存在诸多挑战. 本节将介绍在实践中应对这些挑战的经验与教训，希望能对未来机器学习方法赋能系统软件起到借鉴作用.
首先，我们认为部署在系统软件中的机器学习模型应该尽可能地简单. 模型执行往往是系统关键路径的一部分，使用简单模型可以有效避免机器学习方法引入过多额外开销. 为了使简单模型有限的近似能力在系统软件中发挥作用，我们需要使用简单的问题表述（problem formulation），从而使简单模型成为可选项. 以机器学习数据索引为例，我们曾尝试使用神经网络模型来替代线性模型， 但神经网络模型不仅收敛过程存在不确定性，而且它们的训练和推断时间相比于线性模型高了1个数量级，无法用于数据索引. 以机器学习并发控制为例，我们曾尝试使用深度强化学习方法来学习并发控制策略. 然而，强化学习智能体（agent）的收敛过程同样具有极大不确定性，并且经常收敛于非最优点，其性能低于遗传算法学得的策略. 因为使用真实数据库系统运行工作负载来获得强化学习所需要的环境反馈开销巨大，难以收集更多训练数据来进一步探索强化学习方法的可行性，而是转而使用遗传算法.
其次，我们认为应用机器学习方法时总是需要设计相应的后备机制. 机器学习模型无法保证完全精确，也难以对其误差范围提供确切保证，而系统软件往往需要提供正确性保证，特别是对查询优化器这类本身解决优化问题的系统组件而言更是如此. 因此，我们认为将不精确的机器学习模型与纠正误差的后备机制相结合是机器学习方法赋能系统软件的一种潜在范式. 以机器学习数据索引为例，为解决模型输出的数据位置误差，使用了指数搜索方法来探寻数据的正确位置. 这一后备机制的开销与模型误差成正比，因此当模型精度足够高时，并不需要为后备机制付出额外开销. 以机器学习并发控制为例，我们复用了Silo中为乐观并发控制（optimistic concurrency control, OCC）设计的验证方法来保证提交事务的正确性. 事务验证机制原本就是许多并发控制协议所必需的一部分，仅对Silo验证机制进行极少修改，从而在保证所学并发控制策略正确性的同时避免引入大量开销.
最后，我们认为系统软件实践者应在引入机器学习方法的同时继续加深对目标系统的理解. 对系统功能进行建模并非易事，它不比模型调优简单，而往往需要我们对系统有了深入理解后才能凝练出合适的学习任务. 因此，当我们发现模型难以达到预期效果时，不妨回过头审视自身对系统的理解以及对问题的表述. 以机器学习数据索引为例，我们通过将数据排序并连续存储以简化所需近似拟合的索引函数，进而使用线性模型完成拟合. 以机器学习并发控制为例，我们将大部分精力耗费在探寻简单并具备足够表达能力的事务状态与行动编码方法，而非尝试不同的模型架构与训练方法. 只有深入理解和分析并发控制协议优化的相关研究，我们才能获得最终有效的编码方式，应用机器学习方法才能有所成效.
4. 国内外相关研究
机器学习方法赋能系统软件是近期新兴的研究方向，国内外研究人员均开展了相关工作. 本节对国内外相关研究进行简要回顾.
自2018年麻省理工学院和谷歌的研究人员提出学习索引结构（learned index structure）[11]以来，机器学习方法赋能系统软件这一研究方向已引起了系统研究领域的广泛关注. 麻省理工学院的研究人员随后在数据查询执行[20-21]和查询优化[22-23] 方面进一步尝试应用机器学习方法，并提出SageDB数据库学术原型，将多种基于机器学习方法的数据库组件结合来实现数据分布、工作负载和硬件环境自适应[24-25]. 在国内方面，上海交通大学的研究人员提出了支持动态负载的高可扩展学习索引结构[12-14]，华中科技大学的研究人员则进一步改进了学习索引结构的可扩展性[26].
学习索引结构的提出进一步启发了机器学习方法在存储系统中的应用. 威斯康星大学和微软的研究人员提出使用学习索引结构优化日志结构合并树（log-structured merge-tree, LSM tree）的查询性能[27]. 在国内方面，上海交通大学的研究人员提出了一种基于学习缓存与传统B+树混合架构的RDMA键值存储系统[16-17]，华中科技大学的研究人员则基于学习索引结构构建了面向分离内存（disaggregated memory）场景下的RDMA键值存储系统[28]. 此外，针对机器学习方法在数据库系统中的应用，中国人民大学的研究人员开展了系统性调研并指出数个重要研究问题与潜在挑战[29].
5. 总结与展望
机器学习方法为系统软件的优化和改进提供了新的思路与手段. 实践表明，机器学习方法在优化关键系统组件方面极具潜力. 然而，应用机器学习方法并非易事，实践者将面临定制学习任务与模型、获取训练数据、处理模型开销和误差等方面的新挑战. 回顾在这一方向上的实践经验，我们发现简单地将现有方法应用到系统组件中的效果往往不尽如人意，我们不仅需要同时具备系统和机器学习知识，还需要不断调整系统设计和机器学习算法. 为了应对这些挑战，我们从模型设计、系统集成和实践者自身知识储备等方面总结了经验与教训.
目前，机器学习方法赋能系统软件仍是一个具有较高门槛的研究方向. 一方面，系统研究本身需要大量工程开发并依赖过往经验积累；另一方面，从系统软件实践者的角度来看，机器学习方法更像黑盒工具，难以明确该如何恰当地应用它们. 为了促进这一方向的研究，我们建议：
1）建立系统研究人员和机器学习专家之间的协作关系，共同探索如何用机器学习方法赋能系统软件.
2）以可组合可重用的思想构建系统原型，以便于降低引入与分析机器学习模型难度，更有利于基于过往研究成果与系统代码开展新的研究.
3）探索面向系统软件的模型优化技术，以获得更加适配系统软件运行限制的模型，包括但不限于缩短训练时间、减小内存占用和保证模型精度等方面.
机器学习方法赋能系统软件的研究方兴未艾. 随着技术的不断进步和应用场景的不断扩展，我们相信机器学习方法在系统软件方面的应用前景将会更加广阔，在实际场景中发挥越来越大的作用.
作者贡献声明：唐楚哲负责文献调研和整理，并撰写前言与第2节和第4节；王肇国负责撰写论文其余部分；陈海波负责确立论文框架、提出指导意见并修改论文.
-
表 1 数据集的基本信息
Table 1 Basic Information of Datasets
数据集 对象数 特征数 决策类 数据类型 Ann （Annealing） 798 38 5 混杂 Arrh （Arrhythmia） 452 279 13 混杂 Autos 205 25 6 混杂 Credit （Credit approval） 690 15 2 混杂 Ecoli 336 7 8 数值 Glass 214 10 6 数值 Heart 270 13 2 混杂 Move （Movement libras） 360 90 15 数值 Park （Parkinsons） 195 22 2 数值 Sick 3772 29 2 混杂 Spam （Spambase） 4601 57 2 数值 Wave （Waveform） 5000 21 3 数值 WDBC （Wisconsin Diagnostic Breast Cancer） 569 31 2 数值 Wine 178 13 3 数值 WPBC （Wisconsin Prognostic Breast Cancer） 198 34 2 数值 
下载: 导出CSV
表 2 不同算法所选特征的平均数
Table 2 Average Number of Features Selected by Different Algorithms
数据集 原始特征数 FIE FRFS FDMAR FFRS DNCFS KFCMI Ann 38 15 1 17 11.7 15.7 11.7 Arrh 279 40 1 142 36.3 122.7 125.3 Autos 25 17 14 20 4.0 10.7 9.7 Credit 15 14 14 14 8.0 8.7 7.3 Ecoli 7 7 7 7 7.0 5.3 6.0 Glass 10 10 9 10 8.7 2.0 3.7 Heart 13 13 11 13 6.0 9.7 7.0 Move 90 69 39 72 66.3 71.7 64.3 Park 22 14 13 20 13.7 4.7 8.0 Sick 29 26 1 26 16.0 11.7 10.0 Spam 57 53 56 57 55.0 52.0 48.7 Wave 21 21 21 21 21.0 18.3 19.3 WDBC 31 22 25 31 22.7 13.0 5.7 Wine 13 13 11 13 11.7 5.0 5.0 WPBC 34 28 20 34 28.3 7.0 6.3 平均值 45.6 24.1 16.2 33.1 21.1 23.9 22.5 注：黑体数值表示没有去除任何冗余特征.
下载: 导出CSV
表 3 基于CART算法的不同算法分类准确率
Table 3 Classification Accuracy of Different Algorithms Based on CART Algorithm
% 数据集 原始数据 FIE FRFS FDMAR FFRS DNCFS KFCMI Ann 92.08±0.33 92.19±0.41 76.19±0.00 92.23±0.51 91.25±0.60 92.63±0.50 92.42±0.50 Arrh 65.15±1.56 64.98±0.79 54.20±0.00 64.31±1.77 53.34±0.93 66.02±1.27 66.06±1.82 Autos 74.00±3.98 75.76±1.83 75.32±1.78 75.90±2.63 51.02±2.58 76.54±1.74 77.90±1.90 Credit 80.43±0.80 81.25±1.25 81.30±1.05 81.14±0.86 69.93±1.36 85.36±0.66 85.43±0.90 Ecoli 80.68±1.53 81.88±1.09 80.45±1.68 80.51±1.52 81.88±1.86 81.73±1.17 81.88±1.36 Glass 98.50±0.43 98.69±0.37 98.50±0.30 98.55±0.41 98.32±0.33 98.83±0.33 98.88±0.39 Heart 76.89±2.38 76.22±1.65 75.26±1.59 76.26±1.68 82.44±1.04 79.11±2.30 81.07±1.12 Move 66.11±2.90 66.69±2.00 67.17±2.62 65.22±1.41 64.19±1.60 66.67±2.36 67.64±2.44 Park 85.59±1.67 86.72±1.99 86.82±2.20 86.10±2.20 88.31±1.51 87.33±1.64 87.79±1.41 Sick 98.83±0.12 98.49±0.11 93.88±0.00 98.79±0.10 98.34±0.08 98.86±0.08 98.87±0.08 Spam 91.80±0.36 91.62±0.49 91.71±0.18 91.83±0.27 91.98±0.27 91.92±0.28 92.16±0.28 Wave 75.23±0.45 75.36±0.38 75.27±0.48 75.11±0.62 75.63±0.49 75.06±0.60 75.60±0.37 WDBC 92.46±0.76 93.06±0.70 92.86±0.65 92.02±0.53 93.30±0.74 93.90±0.79 94.22±0.63 Wine 89.61±1.57 90.51±1.11 91.57±1.91 89.66±1.48 90.90±1.09 93.03±1.22 94.04±0.66 WPBC 66.21±3.25 67.63±2.83 67.58±1.87 68.79±2.18 69.55±2.43 73.08±3.88 73.69±2.23 平均值 82.24±1.47 82.74±1.13 80.54±1.09 82.43±1.21 80..03±1.13 84.00±1.25 84.51±1.07 注：黑体值为最高的分类准确率.
下载: 导出CSV
表 4 基于NB算法的不同算法分类准确率
Table 4 Classification Accuracy of Different Algorithms Based on NB Algorithm
% 数据集 原始数据 FIE FRFS FDMAR FFRS DNCFS KFCMI Ann 75.98±0.26 76.02±0.41 76.19±0.00 76.10±0.12 76.29±0.23 76.22±0.10 76.19±0.31 Arrh 62.83±0.59 66.55±0.93 54.20±0.00 60.69±0.76 62.43±0.62 66.97±0.80 68.14±0.42 Autos 60.20±2.08 65.32±1.67 68.34±0.96 63.22±1.32 43.61±1.28 68.73±1.83 70.83±1.07 Credit 66.74±0.39 67.73±0.46 67.56±0.45 67.65±0.69 72.14±0.34 84.86±0.24 86.26±0.34 Ecoli 84.46±0.61 84.38±0.86 84.85±0.45 84.26±0.68 85.00±0.68 84.76±0.44 84.91±0.37 Glass 90.70±0.87 90.47±0.55 92.20±1.15 90.61±0.64 91.54±0.60 98.55±0.46 98.41±0.45 Heart 79.63±0.78 80.04±0.54 79.63±1.00 79.70±0.46 82.41±0.53 82.22±0.43 82.30±0.55 Move 68.03±1.47 67.25±1.12 64.50±1.29 67.17±1.60 66.58±1.14 68.17±1.23 68.42±1.78 Park 74.56±0.65 78.87±0.90 81.38±0.87 74.41±0.61 82.51±1.20 85.74±0.83 85.95±0.36 Sick 93.75±0.03 93.72±0.05 93.88±0.00 93.71±0.04 93.85±0.04 96.70±0.06 96.78±0.04 Spam 54.21±0.12 53.81±0.13 54.33±0.16 54.36±0.19 54.33±0.17 54.17±0.22 56.04±0.17 Wave 80.71±0.10 80.68±0.08 80.73±0.06 80.69±0.06 80.76±0.06 81.50±0.08 81.57±0.09 WDBC 93.71±0.55 94.07±0.17 92.63±0.32 93.74±0.37 92.29±0.31 95.13±0.22 96.80±0.22 Wine 97.98±0.60 97.70±0.41 97.87±0.24 97.47±0.48 96.74±0.36 98.03±0.30 98.03±0.30 WPBC 65.71±2.29 67.22±1.36 68.18±2.01 66.06±2.10 67.88±1.85 78.99±0.90 78.99±1.07 平均值 76.61±0.76 77.59±0.64 77.10±0.60 76.65±0.67 76.56±0.63 81.38±0.54 81.97±0.50 注：黑体值为最高的分类准确率.
下载: 导出CSV
表 5 基于kNN算法的不同算法分类准确率
Table 5 Classification Accuracy of Different Algorithms Based on kNN Algorithm
% 数据集 原始数据 FIE FRFS FDMAR FFRS DNCFS KFCMI Ann 90.53±0.62 90.78±0.64 76.19±0.00 90.71±0.46 90.24±0.52 91.29±0.36 90.79±0.65 Arrh 54.29±0.66 54.60±0.88 0.66±0.00 52.94±0.84 51.35±0.78 55.44±0.84 56.66±0.65 Autos 74.20±0.90 70.83±1.56 75.37±1.08 72.98±1.15 51.80±1.07 82.93±0.92 82.49±1.44 Credit 80.51±0.54 80.26±0.94 80.67±0.57 80.51±0.49 68.23±0.78 81.35±0.40 81.33±0.67 Ecoli 80.60±0.48 80.89±0.86 80.89±0.52 81.16±0.44 81.28±0.89 80.95±0.61 81.19±0.50 Glass 90.89±0.67 91.31±0.59 91.64±0.60 91.26±0.99 91.12±0.66 98.27±0.44 98.50±0.48 Heart 75.41±0.84 75.74±1.25 78.96±0.94 75.89±0.83 74.04±0.85 79.59±0.79 80.26±1.00 Move 85.97±0.82 86.25±0.77 84.92±0.94 85.97±0.53 86.72±0.58 87.08±0.79 87.00±0.67 Park 95.74±0.59 95.28±0.68 95.08±0.60 95.74±0.73 96.46±0.38 96.87±0.78 97.03±0.47 Sick 96.17±0.08 96.43±0.12 93.88±0.00 96.19±0.14 96.28±0.14 96.69±0.14 96.99±0.12 Spam 90.93±0.09 90.80±0.19 90.84±0.25 90.90±0.09 90.99±0.16 90.69±0.23 91.04±0.14 Wave 77.29±0.24 77.22±0.11 77.34±0.20 77.25±0.20 77.47±0.27 77.12±0.28 77.50±0.17 WDBC 95.40±0.41 95.99±0.26 95.45±0.23 95.76±0.46 95.85±0.24 95.62±0.31 95.98±0.17 Wine 95.11±0.46 94.94±0.00 95.84±0.39 95.28±0.39 96.69±0.32 98.65±0.47 98.88±0.26 WPBC 69.24±0.97 71.52±1.70 73.13±1.54 70.20±1.47 72.88±1.31 74.85±0.92 75.10±1.22 平均值 83.48±0.56 83.52±0.70 79.39±0.52 83.52±0.61 81.43±0.60 85.83±0.55 86.05±0.58 注：黑体值为最高的分类准确率.
下载: 导出CSV
-
[1] Liang Jiye, Wang Feng, Dang Chuangyin, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 26(2): 294−308
[2] An Shuang, Hu Qinghua, Pedrycz W, et al. Data-distribution-aware fuzzy rough set model and its application to robust classification[J]. IEEE Transactions on Cybernetics, 2015, 46(12): 3073−3085
[3] Dai Jianhua, Chen Jiaolong. Feature selection via normative fuzzy information weight with application in biological data classification[J]. Applied Soft Computing, 2020, 92(7): 106299
[4] Sun Lin, Wang Lanying, Ding Weiping, et al. Feature selection using fuzzy neighborhood entropy-based uncertainty measures for fuzzy neighborhood multigranulation rough sets[J]. IEEE Transactions on Fuzzy Systems, 2021, 29(1): 19−33 doi: 10.1109/TFUZZ.2020.2989098
[5] Wang Chongzhong, Huang Yang, Ding Weiping, et al. Attribute reduction with fuzzy rough self-information measures[J]. Information Sciences, 2021, 49(5): 68−86
[6] 姚晟,徐风,赵鹏,等. 基于自适应邻域空间粗糙集模型的直觉模糊熵特征选择[J]. 计算机研究与发展,2018,55(4):802−814 doi: 10.7544/issn1000-1239.2018.20160919 Yao Sheng, Xu Feng, Zhao Peng, et al. Intuitionistic fuzzy entropy Feature selection algorithm based on adaptive neighborhood space rough set model[J]. Journal of Computer Research and Development, 2018, 55(4): 802−814 (in Chinese) doi: 10.7544/issn1000-1239.2018.20160919
[7] Wang Chongzhong, Huang Yang, Shao Mingwen, et al. Feature selection based on neighborhood self-information[J]. IEEE Transactions on Cybernetics, 2020, 50(9): 4031−4042 doi: 10.1109/TCYB.2019.2923430
[8] Dash M, Liu Huan. Consistency-based search in feature selection[J]. Artificial Intelligence, 2003, 151(1/2): 155−176
[9] Hu Qinghua, Xie Zongxia, Yu Daren. Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation[J]. Pattern Recognition, 2007, 40(12): 3509−3521 doi: 10.1016/j.patcog.2007.03.017
[10] Wang Chongzhong, Huang Yang, Shao Mingwen, et al. Uncertainty measures for general fuzzy relations[J]. Fuzzy Sets and Systems, 2019, 360(4): 82−96
[11] Dubois D, Prade H. Rough fuzzy sets and fuzzy rough sets[J]. International Journal of General System, 1990, 17(2/3): 191−209
[12] Mi Jusheng, Zhang Wenxiu. An axiomatic characterization of a fuzzy generalization of rough sets[J]. Information Sciences, 2004, 160(1/4): 235−249
[13] 王金波,吴伟志. 双论域上的直觉模糊粗糙集[J]. 模糊系统与数学,2021,35(6):1−13 Wang Jinbo, Wu Weizhi. Intuitionistic fuzzy rough sets over two universes[J]. Fuzzy Systems and Mathematics, 2021, 35(6): 1−13 (in Chinese)
[14] Yeung D S, Chen Degang, Tsang E C C, et al. On the generalization of fuzzy rough sets[J]. IEEE Transactions on Fuzzy Systems, 2005, 13(3): 343−361 doi: 10.1109/TFUZZ.2004.841734
[15] Jensen R, Shen Qiang. Fuzzy-rough attribute reduction with application to Web categorization[J]. Fuzzy Sets and Systems, 2004, 141(3): 469−485 doi: 10.1016/S0165-0114(03)00021-6
[16] Hu Qinghua, Yu Daren, Xie Zongxia. Information-preserving hybrid data reduction based on fuzzy-rough techniques[J]. Pattern Recognition Letters, 2006, 27(5): 414−423 doi: 10.1016/j.patrec.2005.09.004
[17] Chen Degang, Hu Qinghua, Yang Yongping. Parameterized attribute reduction with Gaussian kernel based fuzzy rough sets[J]. Information Sciences, 2011, 181(23): 5169−5179 doi: 10.1016/j.ins.2011.07.025
[18] Wang Chongzhong, Qi Yali, Shao Mingwen, et al. A fitting model for feature selection with fuzzy rough sets[J]. IEEE Transactions on Fuzzy Systems, 2017, 25(4): 741−753 doi: 10.1109/TFUZZ.2016.2574918
[19] Yager R R. Entropy measures under similarity relations[J]. International Journal of General System, 1992, 20(4): 341−358 doi: 10.1080/03081079208945039
[20] Hu Qinghua, Yu Daren, Xie Zongxia, et al. Fuzzy probabilistic approximation spaces and their information measures[J]. IEEE Transactions on Fuzzy Systems, 2006, 14(2): 191−201 doi: 10.1109/TFUZZ.2005.864086
[21] Qian Yuhua, Liang Jiye, Wu Weizhi, et al. Information granularity in fuzzy binary GrC model[J]. IEEE Transactions on Fuzzy Systems, 2010, 19(2): 253−264
[22] Xu Jiucheng, Wang Yun, Xu Keqiang, et al. Feature genes selection using fuzzy rough uncertainty metric for tumor diagnosis[J]. Computational and Mathematical Methods in Medicine, 2019, 27(1): 1−9
[23] 樊雲瑞,张贤勇,杨霁琳. 模糊邻域粗糙集的决策熵不确定性度量[J]. 计算机工程与设计,2021,42(5):1300−1306 doi: 10.16208/j.issn1000-7024.2021.05.015 Fan Yunrui, Zhang Xianyong, Yang Jilin. Uncertainty measurement of decision-entropies based on fuzzy neighborhood rough sets[J]. Computer Engineering and Design, 2021, 42(5): 1300−1306 (in Chinese) doi: 10.16208/j.issn1000-7024.2021.05.015
[24] Zhang Xiao, Mei Changlin, Chen Degang, et al. Feature selection in mixed data: A method using a novel fuzzy rough set-based information entropy[J]. Pattern Recognition, 2016, 56(8): 1−15
[25] Lin Yaojin, Hu Qinghua, Liu Jinghua, et al. Streaming feature selection for multilabel learning based on fuzzy mutual information[J]. IEEE Transactions on Fuzzy Systems, 2017, 25(6): 1491−1507 doi: 10.1109/TFUZZ.2017.2735947
[26] Zhao Junyang, Zhang Zhili, Han Chongzhao, et al. Complement information entropy for uncertainty measure in fuzzy rough set and its applications[J]. Soft Computing, 2015, 19(7): 1997−2010 doi: 10.1007/s00500-014-1387-5
[27] Wang Chongzhong, Huang Yang, Shao Mingwen, et al. Fuzzy rough set-based attribute reduction using distance measures[J]. Knowledge-Based Systems, 2019, 164(1): 205−212
[28] Hu Qinghua, Zhang Lei, Chen Degang, et al. Gaussian kernel based fuzzy rough sets: Model, uncertainty measures and applications[J]. International Journal of Approximate Reasoning, 2010, 51(4): 453−471 doi: 10.1016/j.ijar.2010.01.004
[29] Hu Qinghua, Yu Daren, Pedrycz W, et al. Kernelized fuzzy rough sets and their applications[J]. IEEE Transactions on Knowledge & Data Engineering, 2010, 23(11): 1649−1667
[30] Hu Qinghua, Zhang Lingjun, Zhou YuCan, et al. Large-scale multimodality attribute reduction with multi-kernel fuzzy rough sets[J]. IEEE Transactions on Fuzzy Systems, 2017, 26(1): 226−238
[31] Yuan Zhong, Chen Hongmei, Yang Xiaoling, et al. Fuzzy complementary entropy using hybrid-kernel function and its unsupervised attribute reduction[J]. Knowledge-Based Systems, 2021, 231(11): 107398
[32] Liang Jiye, Chin K S, Dang Chuangyin, et al. A new method for measuring uncertainty and fuzziness in rough set theory[J]. International Journal of General Systems, 2002, 31(4): 331−342 doi: 10.1080/0308107021000013635
[33] Jensen R, Shen Qiang. New approaches to fuzzy-rough feature selection[J]. IEEE Transactions on Fuzzy Systems, 2009, 17(4): 824−838 doi: 10.1109/TFUZZ.2008.924209
[34] Chen Degang, Zhao Suyun. Local reduction of decision system with fuzzy rough sets[J]. Fuzzy Sets and Systems, 2010, 161(13): 1871−1883 doi: 10.1016/j.fss.2009.12.010
[35] Yang Yanyan Song Shiji, Chen Degang, et al. Discernible neighborhood counting based incremental feature selection for heterogeneous data[J]. International Journal of Machine Learning and Cybernetics, 2019, 11(8): 1115−1127
-
期刊类型引用(3)
1. 王梓宇. 面向AI芯片虚拟化的学习型调度算法RLOD. 计算机时代. 2025(01): 20-25+31 . 
百度学术
2. 蔡华洋，黄兴，刘耿耿. 基于深度强化学习的连续微流控生物芯片控制逻辑布线. 计算机研究与发展. 2025(04): 950-962 . 本站查看
3. 高萌涓，王艺达，孙静怡，桑可佳，王奕涵，徐远超. 学习型操作系统和编译器研究综述. 首都师范大学学报(自然科学版). 2024(06): 49-61 . 百度学术
其他类型引用(1)
计量
- 文章访问数: 118
- HTML全文浏览量: 20
- PDF下载量: 84
- 被引次数: 4
