具有复制鲁棒性的高效数据交易估值框架

doi:10.3778/j.issn.1673-9418.2412075

摘要/Abstract

摘要： 随着数据交易市场的兴起，数据价值评估成为关键技术问题。尽管数据夏普利值是一种公平的数据价值度量方法，但其高昂的计算成本和对数据复制攻击缺乏抵御能力，严重限制了在实际数据交易场景中的应用。提出了一种高效且具备复制鲁棒性的数据交易估值框架。针对数据夏普利值计算效率低下的问题，优化了数据集合效用计算后的更新策略，提出了一种高效的数据夏普利值近似算法OA-Shapley（one for all Shapley）。该算法通过单次效用计算更新所有数据点的夏普利值，显著提高了计算效率，并在理论上保证了算法的无偏性和均方误差。针对数据复制攻击问题，从理论上推导出严格冗员性是复制鲁棒性的充分条件，并基于此提出了CL+Shapley（Cluster+Shapley）数据估值框架。该框架通过聚类预处理实现严格冗员性，能够有效抵御数据复制攻击，并且与具体的数据夏普利算法解耦，具有广泛的适用性。实验结果表明，OA-Shapley算法在去除高（低）价值数据点实验中，AUC指标优于基线算法12.4%（3.5%），无效数据检出量增加9%~32%。CL+Shapley框架在复制攻击实验中展现出优异的复制鲁棒性。

关键词: 数据交易, 数据市场, 数据夏普利值, 复制鲁棒性, 聚类算法

Abstract: With the emergence of data trading markets, data valuation has become a key technological challenge. Although data Shapley value has been proven to be a fair method for measuring data value, its high computational cost and vulnerability to data replication attacks severely limit its application in real-world data trading scenarios. To address these issues, this paper proposes an efficient and replication-robust framework for data valuation. To improve the computational efficiency of data Shapley value, this paper optimizes the update strategy after utility calculation of data sets, and introduces an efficient approximation algorithm, OA-Shapley (one for all Shapley). This algorithm updates the Shapley values of all data points through a single utility calculation, significantly enhancing computational efficiency while theoretically guaranteeing the unbiasedness and mean squared error of the algorithm. To tackle the problem of data replication attacks, this paper theoretically derives that strict redundancy is a sufficient condition for replication robustness, and proposes the CL+Shapley (Cluster+Shapley) framework. This framework achieves strict redundancy through clustering preprocessing, effectively defending against data replication attacks and decoupling from specific data Shapley algorithms, thus ensuring wide applicability. Experimental results show that the OA-Shapley algorithm outperforms baseline algorithms by 12.4% (3.5%) in AUC when removing high (low) value data points, and increases the detection of invalid data by 9%~32%. The CL+Shapley framework also demonstrates excellent robustness against replication attacks.

Key words: data trading, data market, data Shapley value, replication robustness, clustering algorithm

陈思远, 陈辰, 袁野, 李博扬. 具有复制鲁棒性的高效数据交易估值框架[J]. 计算机科学与探索, 2025, 19(9): 2532-2547.

CHEN Siyuan, CHEN Chen, YUAN Ye, LI Boyang. Efficient Data Trading Valuation Framework with Replication Robustness[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(9): 2532-2547.

参考文献

[1] VAN BASSHUYSEN P. Radical markets: uprooting capitalism and democracy for a just society[J]. Review of Political Economy, 2019, 31(1): 137-141.
[2] COOK R D. Detection of influential observation in linear regression[J]. Technometrics, 1977, 19(1): 15-18.
[3] KOH P W, LIANG P. Understanding black-box predictions via influence functions[C]//Proceedings of the 34th International Conference on Machine Learning, 2017: 1885-1894.
[4] DASGUPTA A, DRINEAS P, HARB B, et al. Sampling algorithms and coresets for regression[J]. SIAM Journal on Computing, 2009, 38(5): 2060-2078.
[5] SHAPLEY L S. A value for n-person games[M]//Contributions to the theory of games (AM-28). Princeton: Princeton University Press, 1953: 307-318.
[6] GHORBANI A, ZOU J. Data Shapley: equitable valuation of data for machine learning[C]//Proceedings of the 36th International Conference on Machine Learning, 2019: 2242-2251.
[7] ROTH A E. The Shapley value: essays in honor of Lloyd S. Shapley[M]. Cambridge: Cambridge University Press, 1988.
[8] DUBEY P. On the uniqueness of the Shapley value[J]. International Journal of Game Theory, 1975, 4(3): 131-139.
[9] JIA R, DAO D, WANG B, et al. Towards efficient data valuation based on the Shapley value[C]//Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019: 1167-1176.
[10] HAN D, WOOLDRIDGE M, ROGERS A, et al. Replication-robust payoff-allocation for machine learning data markets[EB/OL]. [2024-11-19]. https://arxiv.org/abs/2006.14583.
[11] ROZEMBERCZKI B, WATSON L, BAYER P, et al. The Shapley value in machine learning[EB/OL]. [2024-11-22]. https://arxiv.org/abs/2202.05594.
[12] COHEN S B, RUPPIN E, DROR G. Feature selection based on the Shapley value[C]//Proceedings of the 19th International Joint Conference on Artificial Intelligence, 2005: 665-670.
[13] WANG J, WIENS J, LUNDBERG S. Shapley flow: a graph-based approach to interpreting model predictions[C]//Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021: 721-729.
[14] FUMAGALLI F, MUSCHALIK M, KOLPACZKI P, et al. SHAP-IQ: unified approximation of any-order Shapley interactions[C]//Advances in Neural Information Processing Systems 36, 2023.
[15] MUSCHALIK M, BANIECKI H, FUMAGALLI F, et al. shapiq: Shapley interactions for machine learning[EB/OL]. [2024-12-18]. http://arxiv.org/abs/2410.01649.
[16] MUSCHALIK M, FUMAGALLI F, HAMMER B, et al. Beyond TreeSHAP: efficient computation of any-order Shapley interactions for tree ensembles[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2024, 38(13): 14388-14396.
[17] JIA R, DAO D, WANG B, et al. Efficient task-specific data valuation for nearest neighbor algorithms[EB/OL]. [2024-11-28]. https://arxiv.org/abs/1908.08619.
[18] TANG S Y, GHORBANI A, YAMASHITA R, et al. Data valuation for medical imaging using Shapley value and application to a large-scale chest X-ray dataset[J]. Scientific Reports, 2021, 11: 8366.
[19] WU Z, XU X, SIM R H L, et al. Data valuation in federated learning[M]//Federated learning. Amsterdam: Elsevier, 2024: 281-296.
[20] KWON Y, ZOU J. Beta Shapley: a unified and noise-reduced data valuation framework for machine learning[EB/OL]. [2024-11-30]. https://arxiv.org/abs/2110.14049, 2021.
[21] TIAN Y J, DING Y R, FU S J, et al. Data boundary and data pricing based on the Shapley value[J]. IEEE Access, 2022, 10: 14288-14300.
[22] XU X, LAM T, FOO C S, et al. Model Shapley: equitable model valuation with black-box access[C]//Advances in Neural Information Processing Systems 36, 2023.
[23] AGARWAL A, DAHLEH M, SARKAR T. A marketplace for data: an algorithmic solution[C]//Proceedings of the 2019 ACM Conference on Economics and Computation. New York: ACM, 2019: 701-726.
[24] GHORBANI A, KIM M, ZOU J. A distributional framework for data valuation[C]//Proceedings of the 37th International Conference on Machine Learning, 2020: 3535-3544.
[25] XU X, WU Z, FOO C S, et al. Validation free and replication robust volume-based data valuation[C]//Advances in Neural Information Processing Systems 34, 2021.
[26] KOLPACZKI P, BENGS V, MUSCHALIK M, et al. Approximating the Shapley value without marginal contributions[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2024, 38(12): 13246-13255.
[27] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial data-bases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, 1996: 226-231.
[28] ARYA S, MOUNT D M. Approximate nearest neighbor queries in fixed dimensions[C]//Proceedings of the 4th Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993: 271-280.
[29] OMOHUNDRO S M. Five balltree construction algorithms[EB/OL]. [2024-12-15]. http://www.icsi.berkeley.edu/icsi/publication_details.
[30] DONG E S, DU H R, GARDNER L. An interactive web-based dashboard to track COVID-19 in real time[J]. The Lancet Infectious Diseases, 2020, 20(5): 533-534.
[31] ALMEIDA T A, HIDALGO J M G, YAMAKAMI A. Contributions to the study of SMS spam filtering: new collection and results[C]//Proceedings of the 11th ACM Symposium on Document Engineering. New York: ACM, 2011: 259-262.
[32] DENG L. The MNIST database of handwritten digit images for machine learning research[J]. IEEE Signal Processing Magazine, 2012, 29(6): 141-142.
[33] WOLBERG W O M. Breast cancer Wisconsin (diagnostic)[DS/OL]. UCI Machine Learning Repository, 1993. [2024-12-08]. https://archive.ics.uci.edu/dataset/17.
[34] SIM R H L, ZHANG Y, CHAN M C, et al. Collaborative machine learning with incentive-aware model rewards[C]//Proceedings of the 37th International Conference on Machine Learning, 2020: 8927-8936.
[35] BRODERSEN K H, ONG C S, STEPHAN K E, et al. The balanced accuracy and its posterior distribution[C]//Proceedings of the 20th International Conference on Pattern Recognition. Washington: IEEE Computer Society, 2010: 3121-3124.