CN112182982B - Multiparty joint modeling method, device, equipment and storage medium - Google Patents

Abstract

The disclosure provides a multiparty joint modeling method based on a distributed system, and relates to the fields of machine learning, safe computing and the like. The multiparty joint modeling method comprises the following steps: intersection is carried out on sample identifications included in each of the plurality of clusters to obtain intersection sample identifications and cluster sample data corresponding to the intersection sample identifications and included in each of the plurality of clusters, wherein the sample identifications and the cluster sample data included in each of the plurality of clusters are distributed and stored in a plurality of clients of the corresponding cluster; respectively carrying out barrel classification on cluster sample data of each cluster in the plurality of clusters to obtain cluster barrel classification data of each cluster in the plurality of clusters; constructing a global information gain histogram based on the sample tag and cluster barrel data of each of the plurality of clusters; and constructing a decision tree model based on the global information gain histogram.

Description

Multi-party joint modeling method, device, equipment and storage medium

Technical field

The present disclosure relates to fields such as machine learning and secure computing, and more specifically, to a multi-party joint modeling method, device, equipment and storage medium.

Background technique

With the development of algorithms and big data, algorithms and computing power are no longer bottlenecks hindering the development of AI. Real and effective data sources in various fields are the most valuable resources. At the same time, there are barriers between data sources that are difficult to break. In most industries, data exists in the form of islands. Due to industry competition, privacy security, complex administrative procedures and other issues, even among different departments of the same company, There are also many obstacles to realizing data integration among different places. In reality, it is almost impossible to integrate data scattered across various places and institutions, or the cost required is huge.

The approaches described in this section are not necessarily those that have been previously envisioned or employed. Unless otherwise indicated, it should not be assumed that any method described in this section is prior art merely by virtue of its inclusion in this section. Similarly, unless otherwise indicated, the issues mentioned in this section should not be considered to be recognized in any prior art.

Contents of the invention

According to one aspect of the present disclosure, a multi-party joint modeling method is provided, including: intersecting sample identifiers included in each cluster in multiple clusters, and obtaining the intersection sample identifier and the identifier included in each cluster in the multiple clusters. Cluster sample data corresponding to the intersection sample ID, where the sample ID and cluster sample data included in each cluster in the multiple clusters are distributed and stored in multiple clients of the corresponding cluster; for each of the multiple clusters The cluster sample data of the cluster are bucketed separately to obtain the cluster bucket data of each cluster in multiple clusters; based on the sample label and the cluster bucket data of each cluster in the multiple clusters, a global information gain histogram is constructed , where the sample label is the true value of each sample, and the sample label is saved in a specific cluster among multiple clusters; and based on the global information gain histogram, a decision tree model is constructed.

According to another aspect of the present disclosure, a multi-party joint prediction method based on a distributed system is also provided, including: inputting prediction samples into a decision tree model; for each sub-decision tree of the decision tree model, obtaining the cluster to which the root node belongs ; Communicate with the cluster to obtain the characteristics of the root node; send the characteristic data of the characteristics of the root node of the prediction sample to the cluster to which the node belongs, and obtain the cluster to which the child node belongs; iterate the above process to obtain each of the sub-decision tree pairs The predicted value of the predicted sample; and the predicted value of the predicted sample is summed by each sub-decision tree to obtain the predicted value of the predicted sample.

According to an aspect of the present disclosure, a multi-party joint modeling device based on a distributed system is provided, including: an intersection module configured to intersect data included in the plurality of clusters, so that the plurality of Each of the clusters obtains corresponding cluster sample data; the bucketing module is configured to bucket the cluster sample data of each of the plurality of clusters to obtain a cluster score of each of the plurality of clusters. bucket data; a first building module configured to construct a global information gain histogram based on sample labels and the plurality of cluster bucket data; and a second building module configured to construct a global information gain histogram based on the global information gain histogram , build a decision tree model.

According to another aspect of the present disclosure, an electronic device is also provided, including: a processor; and a memory storing a program. The program includes instructions, and when executed by the processor, the instructions cause the processor to perform the multi-party joint construction according to the above. modular method and/or a multi-party joint prediction method according to the above.

According to another aspect of the present disclosure, a computer-readable storage medium storing a program is also provided. The program includes instructions, and when the instructions are executed by a processor of an electronic device, the instructions cause the electronic device to perform the multi-party joint modeling according to the above. method and/or based on the multi-party joint prediction method described above.

According to another aspect of the present disclosure, a computer program product is provided, including a computer program, wherein the computer program, when executed by a processor, implements the multi-party joint modeling method as described above and/or the multi-party joint modeling method as described above. Joint forecasting method.

The technical solution of the present disclosure implements a multi-party joint modeling method based on distributed systems by bucketing distributed data and constructing an information gain histogram for distributed data, thereby improving the speed of multi-party joint modeling and enabling data processing Complete modeling in large-volume scenarios.

Description of drawings

The drawings illustrate exemplary embodiments and constitute a part of the specification, and together with the written description, serve to explain exemplary implementations of the embodiments. The embodiments shown are for illustrative purposes only and do not limit the scope of the claims. Throughout the drawings, the same reference numbers refer to similar, but not necessarily identical, elements.

1-2 are flowcharts illustrating a multi-party joint modeling method according to an exemplary embodiment;

Figure 3 is a block diagram illustrating a distributed system according to an exemplary embodiment;

4 is a flowchart illustrating separately bucketing cluster sample data for each cluster in a plurality of clusters according to an exemplary embodiment;

Figure 5 is a schematic diagram illustrating a bucketing process according to an exemplary embodiment;

6 is a flowchart illustrating generation of at least one data bucket based on feature data of a current feature according to an exemplary embodiment;

7 is a flowchart illustrating construction of a global information gain histogram according to an exemplary embodiment;

8 is a flowchart illustrating construction of a first information gain histogram according to an exemplary embodiment;

Figure 9 is a flowchart illustrating obtaining a first information gain sub-histogram or a first candidate split gain of features of a node to be split according to an exemplary embodiment;

10 is a flowchart illustrating construction of a first information gain sub-histogram according to an exemplary embodiment;

Figure 11 is a flowchart illustrating a multi-party joint prediction method according to an exemplary embodiment;

Figure 12 is a block diagram illustrating a multi-party joint modeling device according to an exemplary embodiment;

13 is a structural block diagram illustrating an exemplary computing device applicable to exemplary embodiments.

Detailed ways

In this disclosure, unless otherwise stated, the use of the terms “first”, “second”, etc. to describe various elements is not intended to limit the positional relationship, timing relationship, or importance relationship of these elements. Such terms are only used for Distinguish one element from another. In some examples, the first element and the second element may refer to the same instance of the element, and in some cases, based on contextual description, they may refer to different instances.

The terminology used in the description of the various described examples in this disclosure is for the purpose of describing the particular examples only and is not intended to be limiting. Unless the context clearly indicates otherwise, if the number of elements is not specifically limited, the element may be one or more. Furthermore, the term "and/or" as used in this disclosure encompasses any and all possible combinations of the listed items.

In related technologies, the existing multi-party joint modeling method is slow. Especially in scenarios with large amounts of data, multi-party joint modeling cannot be performed due to factors such as device performance and storage capacity, which makes it very difficult to implement in practical applications. big limitations.

In order to solve the above technical problems, the present disclosure provides a multi-party joint modeling method based on a distributed system: intersect the sample identifiers between multiple clusters to obtain the cluster sample data of each cluster; Perform bucketing to obtain cluster bucketed data; build a global information gain histogram based on sample labels and cluster bucketed data of each cluster; build a decision tree model based on the global information gain histogram. As a result, by bucketing distributed data and constructing information gain histograms for distributed data, a multi-party joint modeling method based on distributed systems is realized, thereby improving the speed of multi-party joint modeling and being able to handle large amounts of data. Complete modeling under the scenario.

The multi-party joint modeling method of the present disclosure will be further described below with reference to the accompanying drawings.

FIG. 1 is a flowchart illustrating a multi-party joint modeling method based on a distributed system according to an exemplary embodiment of the present disclosure. As shown in Figure 1, the multi-party joint modeling method may include: step S101, intersect the sample identifiers included in each cluster in the multiple clusters, and obtain the intersection sample identifier and the intersection of the sample identifiers included in each cluster in the multiple clusters. Cluster sample data corresponding to the sample identifier; Step S102, bucket the cluster sample data of each cluster in the multiple clusters to obtain cluster bucket data of each cluster in the multiple clusters; Step S103, based on the sample Tags and cluster bucket data of each cluster in multiple clusters are used to construct a global information gain histogram; and step S104 is to construct a decision tree model based on the global information gain histogram. Therefore, by establishing a distributed system, distributing and storing the cluster's data in multiple clients of the cluster, and using the clients to preliminary bucket the distributed data and construct information gain sub-histograms, multi-party joint modeling can be greatly improved. The speed enables the model to support rapid multi-party joint modeling in richer scenarios.

According to some embodiments, a distributed system includes multiple clusters, each cluster including a server and multiple clients. In an exemplary embodiment, as shown in Figure 3, distributed system 3000 includes cluster 3100, cluster 3200 and cluster 3300. Each cluster includes one server and three clients. For example, cluster 3100 includes server 3110 and clients. 3101. Cluster 3200 includes server 3210 and client 3201. Cluster 3300 includes server 3310 and client 3301. The main functions of the server can include coordinating multiple clients in the cluster, instructing clients to complete tasks such as bucketing and building histograms, integrating information uploaded by clients, sending information to clients, completing some computing functions, and cooperating with other clients. The servers in the cluster communicate, etc. In an exemplary embodiment, inter-cluster communications may be encrypted using Paillier ciphertext. The main functions of the client can include storing data, receiving instructions from the server to complete tasks such as bucketing and building histograms, uploading information to the server, etc. Communication within the cluster can occur without privacy requirements. In an exemplary embodiment, the client communicates only with servers of its own cluster.

Each cluster may include a number of original sample data distributed across multiple clients in the cluster, and the sample data includes sample identifiers. Intersect all sample identifiers included in each cluster to obtain the common sample identifier. Each cluster selects the samples that coincide with the common sample identifier among the original sample data in the cluster as the cluster sample data of the cluster.

In an exemplary embodiment, step S101 may include: the server of each cluster summarizes all sample identifiers in the cluster; implements the intersection of sample identifiers between clusters based on the OT security protocol, and each cluster obtains the same common sample identifier; The server of each cluster sends the common sample identifier to multiple clients in the cluster, instructing the client to intersect the common sample identifier with the sample identifier of the original sample data included in the client to obtain the client sample data of each client. The cluster sample data may include, for example, sample data stored in multiple clients corresponding to multiple clients.

According to some embodiments, both the cluster sample data and the client sample data may include a sample identifier and at least one feature. As shown in Figure 4, step S102 is to bucket the cluster sample data of each cluster in multiple clusters. Obtaining the cluster bucket data of each cluster in multiple clusters may include: step S10201, for each cluster in multiple clusters, traverse at least one feature of the cluster sample data of the cluster; step S10202, based on the current features Feature data, generate at least one data bucket; and step S10203, integrate the data buckets corresponding to all features to obtain cluster bucket data of the cluster. Therefore, by bucketing the cluster sample data, the number of split points and their corresponding information gains that need to be calculated can be reduced, thereby greatly improving the speed of modeling; at the same time, because bucketing will erase the characteristics of all samples in the bucket The data can therefore also serve as the basis for multi-party joint modeling under privacy requirements.

Bucketing is the process of discretizing feature data based on feature information. According to some embodiments, the data bucket may include at least one of a sample identifier, a bucket value, an associated client, and an associated characteristic. In an exemplary embodiment, as shown in Figure 5, data 501 includes sample identifications 1-15 and characteristic data of a selected characteristic. The bucketing process may include, for example: sorting the feature data of the selected features to generate sorted feature data 502; and dividing the feature data into several data buckets 5001 based on preset bucketing rules to obtain bucketed data 503. The client to which each data bucket belongs may include the client where each characteristic data assigned to the same data bucket is located. The characteristics of each data bucket may be the characteristics based on the bucketing process, and the sample identifier of each data bucket. It can include the sample identifier corresponding to each feature data assigned to the same data bucket. The value of each data bucket can be, for example, the average, median, minimum value, and maximum of all the feature data assigned to the same data bucket. Values or values obtained through other calculation methods are not limited here. In an exemplary embodiment, as shown in Figure 5, the value of each data bucket 5001 may be the median of all feature data classified into the same data bucket.

According to some embodiments, the data bucket to be merged may include at least one of a sample identifier, a bucket value, an associated client, and an associated feature. As shown in Figure 6, step S10202: Generate at least one data based on the feature data of the current feature. The bucket may include: step S602, determining whether the feature data of the current feature is distributed on the same client; step S603, responding to the feature data of the current feature being distributed on multiple clients, indicating that each of the multiple clients is responsible for their respective The feature data of the current feature included in the client sample data is divided into buckets, generating at least one data bucket to be merged of the current feature, and uploading at least one data bucket to be merged to the servers corresponding to multiple clients; and step S604, receiving the Merge at least one data bucket to be merged uploaded by multiple clients to generate at least one data bucket. Therefore, when the feature data of the current feature is distributed among multiple clients, each client is instructed to pre-bucket the sample data included in the client, and then the server divides some of the buckets into buckets with the same or similar values. Merging into the same bucket realizes bucketing of distributed data when the feature data of the current feature is distributed on multiple clients. Compared with transmitting all the feature data of the current features of multiple clients to the server, and having the server sort and bucket all the feature data, the above method can significantly speed up the bucketing efficiency, thus greatly improving the modeling speed.

According to some embodiments, step S604: Merge at least one data bucket to be merged received from multiple clients. Generating at least one data bucket may include, for example: merging all data buckets of the current feature to be merged according to the bucket value. Sorting; merge one or more data buckets to be merged with the same or similar values in consecutive buckets into one data bucket. The sample labels included in the merged data bucket can be the merged one or more data buckets to be merged. All tags included. The client to which the merged data bucket belongs may include the clients to which one or more merged data buckets belong. The characteristics of the merged data bucket may be the current characteristics. The value of the merged data bucket For example, it can be the average, median, minimum value, maximum value of the merged values of one or more data buckets to be merged, or a value obtained through other calculation methods, which is not limited here.

According to some embodiments, as shown in Figure 6, step S10202, generating at least one data bucket based on the feature data of the current feature may include: step S605, sending each data bucket in the merged at least one data bucket to the The client to which the data bucket belongs. The client bucket data of the client includes at least one merged data bucket.

According to some embodiments, as shown in Figure 6, step S10202, generating at least one data bucket based on the characteristic data of the current characteristic may include: step S606, responding to the characteristic data of the current characteristic being distributed on the same client, indicating that the same client The client buckets the feature data of the current feature, generates at least one data bucket, and uploads at least one data bucket to the server corresponding to the same client. Steps S601 and S607 in Figure 6 are respectively similar to steps S10201 and S10203 in Figure 4 . After executing steps S605 and S606, step S607 can be executed. Therefore, when all the feature data of the current feature is distributed on the same client, the bucketing result of the client is directly used as the final result, which can reduce the workload caused by bucketing by the server and thereby improve modeling. speed.

The above technical solution instructs the client to bucket its client sample data to generate data buckets or data buckets to be merged, and then the server merges the data buckets to be merged and combines them with other data buckets to obtain cluster bucket data and each client The client-side bucketing data realizes fast bucketing of distributed data, which can greatly improve the modeling speed and enable the model to support richer scenarios.

According to some embodiments, the multiple clusters include a first cluster and at least one second cluster. As shown in Figure 2, the multi-party joint modeling method may also include: step S202, generating a public key and a private key for the server of the first cluster. Right; and step S203, sending the public key and modeling parameters to the server of each second cluster in at least one second cluster. Steps S201 and S204 in Figure 2 are similar to steps S101 and S102 in Figure 1 . Therefore, by using homomorphic encryption, the encrypted information obtained by the second cluster using the encrypted data can be decrypted by the first cluster and the result obtained will be the same as the unencrypted calculation result, which can be used as a data set under privacy requirements. The basis of multi-party joint modeling.

Modeling parameters may include, for example, the maximum number of iterations, learning rate, stop splitting conditions, model convergence conditions, etc. Modeling parameters are public to every cluster participating in the modeling and do not need to be encrypted.

According to some embodiments, the cluster sample data of the first cluster also includes sample labels. As shown in Figure 7, step S103 is to construct a global information gain histogram based on the sample labels and the cluster bucket data of each cluster in the plurality of clusters. It includes: step S10301, obtaining the predicted value of each sample corresponding to each sample identifier of the cluster bucket data of the first cluster by the current model; step S10302, calculating the first-order gradient data and second-order gradient data based on the predicted value and sample label. degree data; and step S10303, construct a global information gain histogram based on the first-order gradient data, the second-order gradient data and the cluster bucket data of each cluster in the multiple clusters. Therefore, by calculating the first-order gradient data and second-order gradient data, combined with the cluster characteristic data of each cluster, a global information gain histogram can be constructed, so that the optimal split point can be subsequently determined based on the global information gain histogram to construct decisions. Tree. At the same time, using the information gain histogram can reduce the number of split points and their split thresholds that need to be calculated, and can accelerate the histogram difference, thereby improving the modeling speed.

According to some embodiments, the current model includes one or more sub-decision trees. The decision tree model constructed by this disclosure can be, for example, a gradient boosting decision tree model, an XGBoost model, a LightGBM model, or other models, which are not limited here. Each leaf node of the current model includes at least one sample identifier, indicating the sample identifier assigned to this node. The structure of one or more sub-decision trees included in the current model, the clusters to which all nodes belong, and the sample identifiers included in all leaf nodes can be disclosed to all clusters. The calculation method of the sample prediction value can be to sum the prediction value of each sub-decision tree for the sample to obtain the model's prediction value for the sample.

The first-order gradient data and the second-order gradient data can be used to find the first-order gradient and the second-order gradient of the objective function set by the model, and bring the predicted value and sample label of the sample into the first-order gradient and the second-order gradient, thereby obtaining the sample's First-order gradient data and second-order gradient data.

The information gain histogram may include multiple histogram buckets that correspond one-to-one to the data buckets, and each histogram bucket may be used to represent the information gain of the corresponding data bucket. Each histogram bucket includes the first-order gradient sum, the second-order gradient sum of all samples in the corresponding data bucket, and the number of samples included in the data bucket.

According to some embodiments, as shown in Figure 2, step S10303, building a global information gain histogram based on the first-order gradient data, the second-order gradient data and the cluster bucket data of each cluster in the plurality of clusters includes: step S207. The first-order gradient data and the second-order gradient data are encrypted and sent to the server of each second cluster in at least one second cluster; step S208, obtain at least one node to be split of the current model, and the node to be split includes at least one sample identifier. ; Step S209, construct a first information gain histogram based on the first-order gradient data, the second-order gradient data, the cluster bucket data of the first cluster and at least one node to be split; Step S211, receive each node from at least one second cluster At least one ciphertext information gain histogram of a server; step S212, decrypt at least one ciphertext information gain histogram to obtain at least one second information gain histogram corresponding to at least one ciphertext information gain histogram; And step S213, combine the first information gain histogram and at least one second information gain histogram to obtain a global information gain histogram. Steps S205 to S206 in Figure 2 are respectively similar to steps S10301 to S10302 in Figure 7 . Thus, by sending the encrypted gradient to at least one second cluster, receiving and decrypting the ciphertext information gain histogram sent from at least one second cluster, the two parties can obtain the other party's gradient data and sample data without Corresponding at least one second information gain histogram is obtained. Combining the first information gain histogram of the first cluster and at least one second information gain histogram, a global information gain histogram is constructed under privacy requirements.

The node to be split may be, for example, some of the leaf nodes of the last sub-decision tree that meet the conditions for allowing splitting. The conditions for allowing splitting may be, for example, that the number of sample identifiers included in a leaf node is less than a preset value, the depth of a leaf node is less than a preset depth, etc., which are not limited here. As a leaf node, the node to be split can include multiple sample identifiers, indicating the samples assigned to this node by the model.

According to some embodiments, as shown in Figure 8, step S209, building the first information gain histogram based on the first-order gradient data, the second-order gradient data, the cluster bucket data of the first cluster and at least one node to be split includes: steps S20901. For each node to be split in at least one node to be split, traverse at least one feature of the cluster bucket data of the first cluster; Step S20902. Based on the feature data of the node to be split and the current feature, obtain the node to be split. The first information gain sub-histogram or the first candidate split gain of the current feature; and step S20903, the first information gain of each feature in at least one feature of the cluster bucket data of the first cluster of each node to be split The sub-histograms or first candidate split gains are combined to obtain the first information gain histogram. Therefore, by constructing the first information gain sub-histogram or the first candidate split gain for each node to be split and the characteristics of each first cluster, the first information gain histogram can be obtained, and the global information gain histogram can subsequently be obtained. to build a decision tree.

According to some embodiments, as shown in Figure 9, step S20902: Based on the feature data of the node to be split and the current feature, obtain the first information gain sub-histogram or the first candidate split gain of the current feature of the node to be split: step S902 , determine whether the feature data of the current feature is distributed on the same client; step S903. In response to the feature data of the current feature being distributed on multiple clients, instruct each of the multiple clients to base on the first-level gradient data, the second-level gradient data, and the second-level gradient data. The step gradient data, the client's client bucket data and the node to be split construct a first information gain sub-histogram to be merged, and upload the first information gain sub-histogram to be merged to the servers corresponding to multiple clients; and steps S904. Combine multiple first information gain sub-histograms to be merged received from multiple clients to construct a first information gain sub-histogram. Therefore, when the feature data of the current feature is distributed among multiple clients, by instructing each client to generate the first information gain sub-histogram to be merged, and then the server merges the sub-histograms to be merged, it is realized based on the current When the feature data of the current feature of the first cluster of the node to be split is distributed among multiple clients, a first information gain sub-histogram is constructed for the current node to be split and the current feature. Compared with directly constructing the first information gain sub-histogram by the server of the first cluster, the above method enables multiple clients to construct the sub-histogram in parallel, thus improving the modeling speed.

According to some embodiments, the first information gain sub-histogram includes at least one histogram bucket, and the at least one histogram bucket corresponds one-to-one to all data buckets whose features are characteristics, and the first information gain sub-histogram to be merged includes at least one to be merged. Merging histogram buckets, at least one histogram bucket to be merged corresponds one-to-one with all data buckets whose features are features, and both the histogram buckets and the histogram buckets to be merged include at least one of the first-order gradient sum and the second-order gradient sum. , as shown in Figure 10, step S904, merge the multiple first information gain sub-histograms to be merged received from multiple clients, and constructing the first information gain sub-histogram includes: step S90401, combine the received Merge at least one histogram bucket to be merged in multiple first information gain sub-histograms uploaded by multiple clients to generate at least one histogram bucket; and step S90402, build the first histogram bucket based on at least one histogram bucket. Information gain sub-histogram. Therefore, by merging the histogram buckets to be merged corresponding to the same data bucket into one histogram bucket, the first information gain sub-histogram can be constructed, realizing the distributed construction of the first information gain sub-histogram, thereby enabling subsequent Combined with the first information gain sub-histograms of other features, a first information gain histogram is obtained.

Both the histogram bucket and the histogram bucket to be merged may include the first-order gradient sum, the second-order gradient sum, and the intersection of the sample identifier included in the histogram bucket or the data bucket corresponding to the histogram bucket to be merged and the sample identifier included in the current node to be split. The number of sample identifiers for the part.

According to some embodiments, step S90401 is to merge at least one histogram bucket to be merged among the first information gain sub-histograms to be merged received from multiple clients. Generating at least one histogram bucket may include: Merge one or more histogram buckets to be merged corresponding to the data bucket of each current feature to obtain a histogram bucket corresponding to the above data bucket. The first-order gradient sum of the histogram bucket may be the sum of the first-order gradient sums of one or more histogram buckets to be merged, and the second-order gradient sum of the histogram bucket may be the sum of the first-order gradients of the merged one or more histogram buckets to be merged. The sum of the second-order gradient sums of the merged histogram buckets, and the number of sample identifiers of the histogram bucket may be the sum of the number of sample identifiers of one or more merged histogram buckets to be merged.

According to some embodiments, as shown in Figure 9, step S20902, based on the feature data of the node to be split and the current feature, obtaining the first information gain sub-histogram or the first candidate split gain of the current feature of the node to be split may include: Step S905: In response to all feature data of the current feature being distributed on the same client, instruct the same client to construct the first information gain sub-system based on the first-order gradient data, the second-order gradient data, the client bucket data of the same client and the node to be split. histogram, calculate the first candidate split gain based on the first information gain sub-histogram, and upload the first candidate split gain to the server of the first cluster. Steps S901 and S906 in FIG. 9 are respectively similar to steps S20901 and S20903 in FIG. 8 . After executing steps S904 and S905, step S906 can be executed. Therefore, when all feature data of the current feature is distributed on the same client, the first information gain sub-histogram of the current feature of the current node to be split is directly constructed, and the first candidate split is calculated based on the first information gain sub-histogram. Gain, thereby reducing the workload caused by building histograms on the server, thereby increasing modeling speed.

The first candidate splitting gain may be the maximum gain of the current feature of the current node to be split, which can be obtained by calculating the splitting gain corresponding to each histogram bucket of the first information gain sub-histogram and selecting the maximum value among them. The splitting gain corresponding to the histogram bucket can be calculated as follows: under the current node to be split and the current feature, obtain the sum of first-order gradient data, the sum of second-order gradient data and the sum of the number of sample identifiers for all histogram buckets. The sum has been obtained during the previous split gain calculation process and is called the parent node information gain original data; calculate the above three sums of the histogram buckets corresponding to all data buckets that are smaller than the value of the data bucket corresponding to the histogram bucket, which is called The original information gain data of the left child node; based on the original information gain data of the parent node and the original information gain data of the left child node, the original information gain data of the right child node can be obtained by making a difference; for the three nodes, the information is calculated based on the original information gain data. Gain; and, use the information gain of the left child node plus the information gain of the right child node minus the information gain of the parent node to obtain the split gain. The calculation method of the information gain can be, for example, the square of the sum of the first-order gradients divided by the sum of the second-order gradients and the harmonic parameter, the square of the sum of the first-order gradients divided by the sum of the number of sample identifiers, or other calculation methods. Here Not limited.

The above technical solution instructs the client to construct the first information gain sub-histogram to be merged or directly calculate the first candidate split gain, and then the server merges the first information gain sub-histogram to be merged, and combines it with the first candidate split gain to obtain the first split gain. An information gain histogram enables the rapid construction of the first information gain histogram, thereby improving the modeling speed and enabling the model to support richer scenarios.

According to some embodiments, as shown in Figure 2, step S10303, building a global information gain histogram based on the first-order gradient data, the second-order gradient data and the cluster bucket data of each cluster in the plurality of clusters may include: step S210 , construct a ciphertext information gain histogram based on the ciphertext first-order gradient data, the ciphertext second-order gradient data, the cluster bucket data of the second cluster and at least one node to be split. In an exemplary embodiment, a method similar to the above steps S901 to S906 may be adopted. For example, the first-order ciphertext gradient data and the second-order ciphertext gradient data may be used respectively to replace the first-order gradient data and the second-order gradient data to obtain the corresponding The ciphertext information gain histogram.

According to some embodiments, as shown in Figure 2, step S104, building a decision tree model based on the global information gain histogram includes: step S214, determining the optimal split point based on the global new information gain histogram; step S215, indicating the optimal The client where the split point is located splits the optimal split point; step S216, iterates the splitting process until the terminating splitting condition is reached, and generates a sub-decision tree; and step S217, iterates the sub-decision tree generation process until the terminating iteration condition is reached. , get the decision tree model. From this, by determining and splitting the optimal split point, new leaf nodes are obtained, and by repeating the above steps, the decision tree model is obtained.

According to some embodiments, step S215, instructing the client to split the optimal split point where the optimal split point is located includes: instructing the client to calculate the split threshold based on the optimal split point and the client's client bucket data to obtain the split leaf node. Include the sample identification and upload the leaf nodes to the server; and synchronize the cluster and leaf nodes of the node where the optimal split point is located to multiple clusters except this cluster. Therefore, by splitting the optimal split point, a new leaf node is obtained, and the new leaf node of the cluster to which the node where the optimal split point belongs is synchronized to each cluster to realize the sharing of models between clusters.

The optimal split point can be the histogram bucket with the largest split gain among all nodes to be split and all features. The split threshold can be calculated based on the following method: sort the feature data corresponding to the intersection of the sample identifier of the data bucket corresponding to the optimal split point and the sample identifier of the node to be split corresponding to the optimal split point; The average of the characteristic data of two adjacent samples is used as the split threshold to calculate the split gain; the split threshold with the largest split gain is selected as the split threshold of the optimal split point. The cluster to which each node belongs is public, and the split threshold is saved in the cluster to which it belongs. Therefore, in the prediction phase, the corresponding cluster can be found through the cluster to which the node included in the multi-party shared model belongs, and then the data is sent to the cluster. Get the next node until the final predicted value is obtained.

According to another aspect of the present disclosure, a multi-party joint prediction method based on a distributed system is also provided. As shown in Figure 11, the multi-party joint prediction method may include: step S1101, input the prediction sample into the decision tree model; step S1102, for For each sub-decision tree of the decision tree model, obtain the cluster to which the root node belongs; Step S1103, communicate with the cluster to which it belongs, and obtain the characteristics of the root node; Step S1104, send the characteristic data of the characteristics of the root node of the predicted sample to the cluster to which it belongs. Cluster, obtain the cluster to which the child node belongs; step S1105, iterate the above process to obtain the predicted value of each sub-decision tree for the prediction sample; and step S1106, sum the predicted value of each sub-decision tree for the prediction sample to obtain the prediction The predicted value of the sample. Therefore, by continuously communicating with the cluster to which the current node of the current sub-decision tree belongs and returning to the next node, the predicted value of each sub-decision tree for the sample can be calculated, thereby obtaining the predicted value of the sample by the model. Since the decision tree model is shared by multiple clusters and the split threshold is only saved in the cluster to which the node belongs, the complete content of the model is not public to any cluster. Therefore, it is necessary to combine the information saved in the cluster for each cluster to implement sample analysis. Prediction, realizing multi-party joint modeling that supports privacy scenarios.

According to another aspect of the present disclosure, a multi-party joint modeling device is also provided. As shown in Figure 12, the multi-party joint modeling device 1200 may include: an intersection module 1201, configured to intersect the sample identifiers included in each cluster in multiple clusters, and obtain the intersection sample identifier and the sample identifiers in the multiple clusters. Each cluster includes cluster sample data corresponding to the intersection sample identifier; the bucketing module 1202 is configured to bucket the cluster sample data of each of the multiple clusters to obtain the cluster score of each of the multiple clusters. bucket data; the first building module 1203 is configured to construct a global information gain histogram based on sample labels and multiple cluster bucket data; and the second building module 1204 is configured to construct a global information gain histogram based on the global information gain histogram. Decision tree model.

According to another aspect of the present disclosure, there is also provided an electronic device, which may include: a processor; and a memory storing a program, the program including instructions that, when executed by the processor, cause the processor to execute According to the above-mentioned multi-party joint modeling method.

According to another aspect of the present disclosure, there is also provided a computer-readable storage medium storing a program, the program including instructions that, when executed by a processor of an electronic device, cause the electronic device to execute the method according to the above-mentioned methods. Joint modeling approach.

Referring to FIG. 13 , a computing device 13000 will now be described, which is an example of a hardware device (electronic device) to which aspects of the present disclosure may be applied. Computing device 13000 may be any machine configured to perform processing and/or calculations, and may be, but is not limited to, a workstation, a server, a desktop computer, a laptop, a tablet, a personal digital assistant, a robot, a smartphone, a vehicle-mounted computer, or any combination thereof. The above-mentioned multi-party joint modeling method may be implemented in whole or at least in part by the computing device 13000 or a similar device or system.

Computing device 13000 may include elements coupled to or in communication with bus 13002 (perhaps via one or more interfaces). For example, computing device 13000 may include a bus 13002, one or more processors 13004, one or more input devices 13006, and one or more output devices 13008. The one or more processors 13004 may be any type of processor and may include, but are not limited to, one or more general purpose processors and/or one or more special purpose processors (eg, special processing chips). Input device 13006 may be any type of device capable of inputting information to computing device 13000 and may include, but is not limited to, a mouse, a keyboard, a touch screen, a microphone, and/or a remote control. Output device 13008 may be any type of device capable of presenting information and may include, but is not limited to, a display, speakers, video/audio output terminal, vibrator, and/or printer. Computing device 13000 may also include or be connected to non-transitory storage device 13010 , which may be any storage device that is non-transitory and that enables data storage, and may include, but is not limited to, a disk drive , optical storage device, solid state memory, floppy disk, flexible disk, hard disk, magnetic tape or any other magnetic media, optical disk or any other optical media, ROM (read only memory), RAM (random access memory), cache memory and/or Any other memory chip or cartridge, and/or any other medium from which a computer can read data, instructions and/or code. Non-transitory storage device 13010 may be detached from the interface. The non-transitory storage device 13010 may have data/programs (including instructions)/code for implementing the above methods and steps. Computing device 13000 may also include a communications device 13012. Communication device 13012 may be any type of device or system that enables communication with external devices and/or with a network, and may include, but is not limited to, a modem, a network card, an infrared communication device, a wireless communication device, and/or a chipset, such as Bluetooth™ equipment, 1302.11 equipment, WiFi equipment, WiMax equipment, cellular communications equipment and/or the like.

Computing device 13000 may also include working memory 13014, which may be any type of working memory that may store programs (including instructions) and/or data useful for the operation of processor 13004, and may include, but is not limited to, random access memory and /or read-only memory device.

Software elements (programs) may be located in working memory 13014, including, but not limited to, operating system 13016, one or more applications 13018, drivers, and/or other data and code. Instructions for performing the above methods and steps may be included in one or more application programs 13018, and the above multi-party joint modeling method may be implemented by reading and executing instructions of the one or more application programs 13018 by the processor 13004 . More specifically, in the above-mentioned multi-party joint modeling method, steps S101 to S104 can be implemented, for example, by the processor 13004 executing the application program 13018 having the instructions of steps S101 to S104. In addition, other steps in the above-mentioned multi-party joint modeling method may be implemented, for example, by the processor 13004 executing an application program 13018 having instructions for executing corresponding steps. The executable code or source code of the instructions of the software element (program) may be stored in a non-transitory computer-readable storage medium (such as the storage device 13010 described above), and when executed, may be stored in the working memory 13014 (possibly compiled and/or installation). Executable code or source code for the instructions of the software element (program) may also be downloaded from a remote location.

It should also be understood that variations may be made depending on specific requirements. For example, custom hardware may also be used, and/or particular elements may be implemented in hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. For example, some or all of the disclosed methods and apparatus may be implemented on hardware (e.g., including field programmable gate arrays) in assembly language or a hardware programming language (such as VERILOG, VHDL, C++) by using logic and algorithms in accordance with the present disclosure. Programmable logic circuits (FPGA) and/or programmable logic array (PLA)) are implemented by programming.

It should also be understood that the aforementioned methods can be implemented through a server-client model. For example, a client can receive user-entered data and send that data to a server. The client can also receive data input by the user, perform part of the processing in the aforementioned methods, and send the processed data to the server. The server can receive data from the client, execute the foregoing method or another part of the foregoing method, and return the execution result to the client. The client can receive the execution result of the method from the server and can present it to the user through an output device, for example.

It should also be understood that components of computing device 13000 may be distributed over a network. For example, one processor may be used to perform some processing while other processing may be performed by another processor remote from the one processor. Other components of computing system 13000 may be similarly distributed. As such, computing device 13000 may be interpreted as a distributed computing system that performs processing at multiple locations.

Although the embodiments or examples of the present disclosure have been described with reference to the accompanying drawings, it should be understood that the above-mentioned methods, systems and devices are only exemplary embodiments or examples, and the scope of the present invention is not limited by these embodiments or examples. It is limited only by the granted claims and their equivalent scope. Various elements in the embodiments or examples may be omitted or replaced by equivalent elements thereof. Furthermore, the steps may be performed in a different order than described in this disclosure. Further, various elements in the embodiments or examples may be combined in various ways. Importantly, as technology evolves, many elements described herein may be replaced by equivalent elements appearing after this disclosure.

Claims (19)

1. A multi-party joint modeling method based on a distributed system, wherein the distributed system comprises a plurality of clusters, each cluster of the plurality of clusters comprising a server and a plurality of clients, the method comprising:

intersection is carried out on sample identifications included in each of the plurality of clusters to obtain an intersection sample identification and cluster sample data corresponding to the intersection sample identification, wherein the sample identifications and the cluster sample data included in each of the plurality of clusters are distributed and stored in a plurality of clients of the corresponding cluster, the cluster sample data comprises client sample data stored in the corresponding plurality of clients, and the cluster sample data and the client sample data comprise sample identifications and at least one feature;

respectively barrelling cluster sample data of each cluster in the plurality of clusters to obtain cluster barrelled data of each cluster in the plurality of clusters, wherein the method comprises the following steps:

traversing, for each of the plurality of clusters, the at least one feature of the cluster sample data of that cluster;

Generating at least one data bucket based on the feature data of the current feature; and

integrating the data buckets corresponding to all the features to obtain cluster sub-bucket data of the cluster, wherein the cluster sub-bucket data of the cluster comprises at least one feature of cluster sample data of the cluster and one or more data buckets corresponding to each feature of the at least one feature of the cluster sample data of the cluster;

constructing a global information gain histogram based on a sample tag and cluster barrel data of each of the plurality of clusters, wherein the sample tag is a true value of each sample and the sample tag is stored in a particular cluster of the plurality of clusters; and

and constructing a decision tree model based on the global information gain histogram.

2. The multi-party joint modeling method of claim 1, wherein the generating at least one data bucket based on the feature data of the current feature comprises:

judging whether the characteristic data of the current characteristic are distributed on the same client;

responding to the characteristic data of the current characteristic to be distributed on a plurality of clients, indicating each client in the plurality of clients to divide the characteristic data of the current characteristic included in the sample data of the respective client into barrels, generating at least one data barrel to be combined of the current characteristic, and uploading the at least one data barrel to be combined to a server corresponding to the plurality of clients; and

And merging the at least one to-be-merged data bucket uploaded by the plurality of clients to generate the at least one data bucket, wherein each data bucket in the at least one data bucket is formed by merging one or more to-be-merged data buckets with the same or similar values, the sample identification of each data bucket in the at least one data bucket comprises all sample identifications of the one or more to-be-merged data buckets, and the client of each data bucket in the at least one data bucket comprises the client of the one or more to-be-merged data buckets.

3. The multi-party joint modeling method of claim 2, wherein generating at least one data bucket based on the feature data of the current feature further comprises:

and sending each data bucket in the at least one data bucket to the client of the data bucket, wherein the client sub-bucket data of the client comprises the at least one data bucket.

4. The multi-party joint modeling method of claim 3, wherein generating at least one data bucket based on the feature data of the current feature further comprises:

And responding to the characteristic data of the current characteristic to be distributed on the same client, indicating the same client to sub-tank the characteristic data of the current characteristic, generating at least one data tank, and uploading the at least one data tank to a server corresponding to the same client, wherein the client sub-tank data of the same client comprises the at least one data tank.

5. The multi-party joint modeling method of claim 4, wherein the plurality of clusters includes a first cluster and at least one second cluster, the cluster sample data of the first cluster further including the sample tag,

wherein constructing a global information gain histogram based on the sample tags and the cluster barrel data for each of the plurality of clusters comprises:

obtaining a predicted value of a current model on each sample corresponding to each sample identifier of cluster sub-bucket data of the first cluster;

calculating first-order gradient data and second-order gradient data based on the predicted value and the sample tag; and

the global information gain histogram is constructed based on the first order gradient data, the second order gradient data, and cluster bucket data for each of the plurality of clusters.

6. The multi-party joint modeling method of claim 5, wherein the constructing the global information gain histogram based on the first order gradient data, the second order gradient data, and cluster bucket data for each of the plurality of clusters comprises:

encrypting the first-order gradient data and the second-order gradient data and then sending the encrypted first-order gradient data and the encrypted second-order gradient data to a server of each second cluster in the at least one second cluster;

acquiring at least one node to be split of the current model, wherein the node to be split comprises at least one sample identifier;

constructing a first information gain histogram based on the first-order gradient data, the second-order gradient data, cluster bucket data of the first cluster and the at least one node to be split;

receiving at least one ciphertext information gain histogram from a server of each of the at least one second cluster;

decrypting the at least one ciphertext information gain histogram to obtain at least one second information gain histogram corresponding to the at least one ciphertext information gain histogram one by one; and

and combining the first information gain histogram and the at least one second information gain histogram to obtain the global information gain histogram.

7. The multi-party joint modeling method of claim 6, wherein the constructing a first information gain histogram based on the first order gradient data, the second order gradient data, cluster bucket data of the first cluster, and the at least one node to be split comprises:

traversing at least one feature of cluster sub-bucket data of the first cluster for each of the at least one node to be split;

based on the feature data of the node to be split and the current feature, obtaining a first information gain sub-histogram or a first candidate splitting gain of the current feature of the node to be split; and

and merging the first information gain sub-histogram or the first candidate splitting gain of each feature in at least one feature of the cluster barrel data of the first cluster of each node to be split to obtain the first information gain histogram.

8. The multiparty joint modeling method according to claim 7, wherein said deriving a first information gain sub-histogram or a first candidate split gain for the current feature of the node to be split based on the feature data for the node to be split and the current feature comprises:

Judging whether feature data of the current feature are distributed on the same client;

responding to the characteristic data of the current characteristic to be distributed on a plurality of clients, indicating each client in the plurality of clients to construct a first information gain sub-histogram to be combined based on the first-order gradient data, the second-order gradient data, the client barrel data of the client and the node to be split, and uploading the first information gain sub-histogram to be combined to a server corresponding to the plurality of clients; and

and merging the received first information gain sub-histograms to be merged, which are uploaded by the clients, and constructing the first information gain sub-histograms.

9. The multi-party joint modeling method of claim 8, wherein the first information gain sub-histogram includes at least one histogram bin that corresponds one-to-one to all data bins belonging to the feature, the first information gain sub-histogram to be combined includes at least one histogram bin to be combined that corresponds one-to-one to all data bins belonging to the feature, the histogram bin and the histogram bin to be combined each include at least one of a first order gradient and a second order gradient and,

The merging the received multiple to-be-merged first information gain sub-histograms uploaded by the multiple clients, and constructing the first information gain sub-histogram includes:

combining at least one to-be-combined histogram bucket in the plurality of to-be-combined first information gain sub-histograms uploaded by the plurality of clients to generate at least one histogram bucket, wherein each histogram bucket in the at least one histogram bucket is formed by combining one or a plurality of to-be-combined histogram buckets corresponding to the same data bucket from different to-be-combined first information gain sub-histograms, the first-order gradient sum of each histogram bucket in the at least one histogram bucket is the sum of the first-order gradient sums of the one or more to-be-combined histogram buckets, and the second-order gradient sum of each histogram bucket in the at least one histogram bucket is the sum of the second-order gradient sums of the one or more to-be-combined histogram buckets; and

the first information gain sub-histogram is constructed based on the at least one histogram bin.

10. The multi-party joint modeling method of claim 9, wherein the obtaining a first information gain sub-histogram or a first candidate split gain for the current feature of the node to be split based on the feature data for the node to be split and the current feature further comprises:

And responding to the fact that all feature data of the current feature are distributed on the same client, indicating the same client to construct the first information gain sub-histogram based on the first-order gradient data, the second-order gradient data, the client barrel data of the same client and the node to be split, calculating the first candidate split gain based on the first information gain sub-histogram, and uploading the first candidate split gain to a server of the first cluster.

11. The multiparty joint modeling method according to claim 6, wherein said ciphertext information gain histogram is constructed based on ciphertext first order gradient data, ciphertext second order gradient data, cluster bucket data of said second cluster, and said at least one node to be split.

12. The multi-party joint modeling method of claim 5, wherein the current model includes one or more sub-decision trees, each of the at least one node to be split being a part of a leaf node of a last sub-decision tree of the current model.

13. The multi-party joint modeling method of claim 12, wherein the constructing a decision tree model based on the global information gain histogram includes:

Determining an optimal splitting point based on the global new information gain histogram;

indicating a client where the optimal splitting point is located to split the optimal splitting point;

iterating the splitting process until the splitting termination condition is reached, and generating the sub-decision tree; and

and iterating the sub-decision tree generation process until reaching the iteration termination condition to obtain the decision tree model.

14. The multi-party joint modeling method of claim 13, wherein the current model includes a structure of one or more sub-decision trees, the clusters to which all nodes belong are disclosed for the plurality of clusters,

wherein the indicating the client where the optimal splitting point is located to split the optimal splitting point includes:

the client is instructed to calculate a splitting threshold based on the optimal splitting point and the client barrel splitting data of the client, a sample identifier included in the split leaf node is obtained, and the leaf node is uploaded to a server; and

synchronizing the cluster to which the node of the optimal splitting point belongs and the leaf nodes to the clusters except the cluster.

15. A multi-party joint prediction method based on a decision tree model built according to the method of any one of claims 1-14, comprising:

Inputting a prediction sample into the decision tree model;

aiming at each sub-decision tree of the decision tree model, acquiring a cluster to which a root node belongs;

communicating with the affiliated cluster to acquire the characteristics of the root node;

the feature data of the features of the root node of the prediction sample are sent to the affiliated cluster, and the affiliated cluster of the child node is obtained;

iterating the process to obtain a predicted value of each sub-decision tree on the predicted sample; and

and summing the predicted values of the predicted samples by each sub-decision tree to obtain the predicted values of the predicted samples.

16. A multi-party joint modeling apparatus based on a distributed system, wherein the distributed system comprises a plurality of clusters, each cluster of the plurality of clusters comprising a server and a plurality of clients, the apparatus comprising:

an intersection module configured to intersect a sample identifier included in each of the plurality of clusters to obtain an intersection sample identifier and cluster sample data corresponding to the intersection sample identifier included in each of the plurality of clusters, where the sample identifier and the cluster sample data included in each of the plurality of clusters are distributed and stored in a plurality of clients of the corresponding cluster, and the cluster sample data includes client sample data stored in the corresponding plurality of clients, and the cluster sample data and the client sample data each include a sample identifier and at least one feature;

The barreling module is configured to respectively barrel the cluster sample data of each of the plurality of clusters to obtain cluster barreled data of each of the plurality of clusters, and comprises the following steps:

traversing, for each of the plurality of clusters, the at least one feature of the cluster sample data of that cluster;

generating at least one data bucket based on the feature data of the current feature; and

integrating the data buckets corresponding to all the features to obtain cluster sub-bucket data of the cluster, wherein the cluster sub-bucket data of the cluster comprises at least one feature of cluster sample data of the cluster and one or more data buckets corresponding to each feature of the at least one feature of the cluster sample data of the cluster;

a first construction module configured to construct a global information gain histogram based on a sample tag and the plurality of cluster barrel data, wherein the sample tag is a true value for each sample and the sample tag is stored in a particular cluster of the plurality of clusters; and

and a second construction module configured to construct a decision tree model based on the global information gain histogram.

17. An electronic device, comprising:

a processor; and

a memory storing a program comprising instructions that when executed by the processor cause the processor to perform the method of any one of claims 1-15.

18. A computer readable storage medium storing a program, the program comprising instructions which, when executed by a processor of an electronic device, cause the electronic device to perform the method of any one of claims 1-15.

19. A computer program product comprising a computer program, wherein the computer program, when executed by a processor, implements the method of any of claims 1-15.