CN112131569B - Risk user prediction method based on graph network random walk - Google Patents

Abstract

The invention relates to a risk user prediction method based on graph network random walk, which includes the following steps: 1) obtaining graph networked data as an original data set; 2) preprocessing the original data set and constructing a graph network; 3 ) Use the clustering algorithm based on random walk to obtain the probability of the node corresponding to the preprocessed data, that is, the user's risk score; 4) Integrate the user node probability obtained by the clustering algorithm and output the final risk user prediction result. Compared with the existing technology, the present invention has the advantages of better scalability, no need for feature engineering, and good effects.

Description

A risk user prediction method based on graph network random walk

Technical field

The present invention relates to the field of data mining technology, and in particular to a risk user prediction method based on graph network random walk.

Background technique

With the advancement of information technology, the scale of data is getting larger and larger, and the data network formed by the interaction between data is becoming more and more complex. These situations have brought great challenges to related data mining work on graph networks. Predicting the needs of risk users often requires a large amount of complex data screening and mining work. Some companies use professionals to perform data analysis, but this brings extremely high labor costs.

Although some algorithm models on existing stand-alone platforms have achieved effective results, they have scalability problems and low processing capabilities in the face of massive data. Therefore, a risk user prediction method based on graph network random walks is needed. It effectively circumvents this problem, enabling it to eliminate the need for professionals to analyze all data one by one, and also better supports the horizontal expansion of the system to solve the problems caused by massive data.

Contents of the invention

The purpose of the present invention is to provide a risk user prediction method based on graph network random walk in order to overcome the above-mentioned defects in the prior art.

The object of the present invention can be achieved through the following technical solutions:

A risk user prediction method based on graph network random walk, including the following steps:

1) Obtain graph network data as the original data set;

2) Preprocess the original data set and construct a graph network;

3) Obtain the probability corresponding to the node through the clustering algorithm based on random walk for the preprocessed data, that is, the user's risk score;

4) Integrate the user node probabilities obtained by the clustering algorithm and output the final risk user prediction results.

The data sets in the form of graph networks include public competition data sets, university public data sets, and enterprise public data sets. The public competition data sets include data sets public by Kaggle and KDD competition websites. The university's public data sets are public data sets on the Stanford University open source data set website, and the enterprise public data sets include those of Microsoft and Yahoo.

Described step 2) specifically includes the following steps:

21) Obtain feature data from the original data and filter out noise data, that is, edge data with too low weight;

22) Use relationship prediction models to supplement possible missing data;

23) Unify the coding of node numbers in the graph network;

24) Normalize the weights of edges in graph networks.

In step 21), the type of feature data includes graph node features of the data, edge weights, direction features, and risk nodes selected as initial nodes for subsequent random walks.

The graph node feature is the user's label data, which represents the user's risk performance score. Its value is 0 or 1, corresponding to risk or no risk. The edges represent the relationship between users, including call relationships and concerns. Relationships and social friend relationships, the weight of which represents the closeness of the relationship between users.

In step 22), supplementing possible missing data specifically includes:

For data: linear interpolation supplement using linear models;

For categorical features: select the feature value with the most occurrences of the category as the missing value to supplement.

In the described step 3), the rules of random walk are specifically:

All directed edges in the graph network are treated as undirected edges. If there are multiple edges between nodes, they are merged into one edge. After the merge, the weight of the edge is the average of the multiple edges;

Select a known risk user as the initial seed node of the random walk, and select the next node of the walk in equal proportion according to the edge weight. When all nodes in the graph network appear in the random walk path, the probability After stabilization, the random walk is stopped, and the access probability corresponding to the node is used as the user's risk score;

For random walk objects, each random walk step has a probability of b to randomly move from the current node to a neighbor node of the current node, and at the same time, there is a probability of 1-b to return directly from the current node to the original seed node. ,Specifically:

r ^t+1 =b*r ^t +(1-b)*r ⁰

Among them, r ^t represents the probability that node r is visited in the graph network at time t, and r ⁰ represents the probability that the initial seed node is visited.

The value of probability is 0.9.

In the process of random walk, in order to reduce the computational complexity, the access probability threshold δ=0.0001 is set. When the random walk reaches a node and the access probability of the node is not 0 and less than δ, the random walk returns the most The starting seed node.

In step 4), when the risk score of the user to be predicted exceeds the set risk score threshold, the user to be predicted is determined to be a risky user.

Compared with the prior art, the present invention has the following advantages:

1. The present invention can avoid the extremely high labor costs caused by existing manual risk prediction users.

2. The present invention can process graph network data, and can better utilize the correlation information between samples than the general feature processing method.

3. The present invention has strong scalability and can well support distributed computing systems.

4. The present invention has a wide range of applications and has commercial significance. It can not only process public data sets, but can also be extended to the processing of internal business data of enterprises.

Description of drawings

Figure 1 is a flow chart of preprocessing and training of the present invention.

Figure 2 is a flow chart of the present invention.

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

Example

In order to explain the purpose, technical solutions and key points of the present invention more clearly and in detail, the present invention will be further elaborated in detail. It should be understood that the implementation methods described here are only used to explain the specific methods of the present invention, but do not limit the present invention. Persons skilled in the art can implement and promote the method according to the principles explained in the present invention, and can generalize the present invention to similar application scenarios by making simple modifications according to the structured data set that needs to be processed.

As shown in Figures 1 and 2, the present invention first preprocesses the original data, and then uses a random walk algorithm on the preprocessed data. After the random walk, a risk score of all nodes in the graph can be obtained, and finally When using the model, you only need to query the risk score of the corresponding user through query. Therefore, the present invention specifically includes three stages: data preprocessing stage, random walk stage and using model, specifically:

1) Data preprocessing stage: Obtain the graph network data set as the original data set, and preprocess the original data, then there are:

First, collect the required graph network data. These data are composed of users as nodes in the graph network, relationships between users, such as social friend relationships, and call relationships as edges. The data labels are the user's risk performance, such as financial Whether there are loan defaults in the scenario, etc. For node data, its characteristics are first processed. Most of the characteristic data are provided by the data set itself, which generally consists of the user's gender, age, historical behavior and other information. For the noise in these characteristic data The data filtering method is to use linear regression or decision tree model to simply fit the corresponding feature data, and then eliminate the data that is too far from the fitting curve in the data;

Linear regression model formula: f(x)＝W ^T X+b

The error function used for training is:

Among them, x _i and y _i are the feature attribute values corresponding to the sample and the label of the sample, w and b are the model parameters corresponding to the linear model.

Then for edge data, edge data often represents the relationship between users, and the edge weight represents the closeness of the relationship between users. In the noise filtering process, edges with too low weights need to be filtered out. Then for the edges with missing weights, the edge weight prediction model needs to be applied to supplement the data set. Specifically, you can use the graph network edge weight prediction model proposed by Srijan Kumar in the article "Edge Weight Prediction in Weighted Signed Networks" in 2016. . Finally, the value predicted by the prediction model is used as the weight value corresponding to the missing weight edge. Similarly, edges with too low predicted weights are also filtered out.

2) Random walk stage:

In the random walk stage, a walk rule first needs to be defined. In the experimental system, the walk rule customized by the present invention selects the next node of the walk in equal proportion according to the edge weight. All directed edges in the system are treated as undirected edges. If there are multiple edges between nodes, they are merged into one edge, and the weight of the edge is the average of the multiple edges. In addition, for a random walk object, in each random walk step, there will be a 0.9 probability of randomly moving from its current node to a neighbor node of that node, and a 0.1 probability of returning directly from the current node. To the initial seed node, specifically, the iteration formula is as follows:

r ^t+1 =0.9*r ^t +0.1*r ⁰

Among them, r ^t represents the probability of the node in the graph being visited at time t, and r ⁰ represents the probability of the initial node being visited, that is, the value corresponding to the seed node is 1, and the values corresponding to the other nodes are 0.

At the same time, in order to reduce the computational complexity of the system, it is necessary to set a δ = 0.0001. When the random walk reaches a node and the access probability of the node is not 0 but less than δ, the random walk will return to the seed node. The above is the walking rule of the random walk stage.

After defining the rules, you only need to start from the pre-selected seed nodes - that is, the nodes with risk labels in practice and continuously simulate the random walk path according to the pre-defined random walk rules. When the probability of the nodes in the entire graph appearing in the random walk path stabilizes, stop the simulation and use this probability as the risk score of the corresponding node. A higher risk score means that the user has a higher probability of becoming a new risky user.

3) Using the model stage:

The data that needs to be queried is input into the system, and the system matches the corresponding node from the graph network, and then outputs the node, that is, the risk score of the corresponding sample that needs to be queried as the output result.

This invention uses a graph network data mining algorithm based on random walks, which overcomes the inability of traditional structured data processing methods to solve the problem of graph network features. It also optimizes the problem of poor performance of neural networks on category feature data and reduces manpower. Cost, can provide help for better processing of networked data.

Those skilled in the art can easily understand the above process. The above process is only a specific example of the present invention. In actual industrial production, those skilled in the art can modify, Improve some details to make specific operations more suitable for actual application scenarios.

Claims (9)

1. A risk user prediction method based on graph network random walk, which is characterized by including the following steps: 1) Obtain graph network data as the original data set; 2) Preprocess the original data set and construct a graph network; 3) Obtain the probability corresponding to the node through the clustering algorithm based on random walk for the preprocessed data, that is, the user's risk score; 4) Integrate the user node probabilities obtained by the clustering algorithm and output the final risk user prediction results; In the described step 3), the rules of random walk are specifically: All directed edges in the graph network are treated as undirected edges. If there are multiple edges between nodes, they are merged into one edge. After the merge, the weight of the edge is the average of the multiple edges; The edge represents the relationship between users, including call relationship, follow relationship and social friend relationship, and its weight represents the closeness of the relationship between users; Select a known risk user as the initial seed node of the random walk, and select the next node of the walk in equal proportion according to the edge weight. When all nodes in the graph network appear in the random walk path, the probability After stabilization, the random walk is stopped, and the access probability corresponding to the node is used as the user's risk score; For random walk objects, each random walk step has a probability of b to randomly move from the current node to a neighbor node of the current node, and at the same time, there is a probability of 1-b to return directly from the current node to the original seed node. ,Specifically: r ^t+1 =b*r ^t +(1-b)*r ⁰ Among them, r ^t represents the probability that node r is visited in the graph network at time t, and r ⁰ represents the probability that the initial seed node is visited. 2. A risk user prediction method based on graph network random walk according to claim 1, characterized in that the data set containing the graph network form includes a public competition data set, a university public data set and Data sets disclosed by enterprises, the said public competition data sets include data sets made public by Kaggle and KDD competition websites, said data sets made public by universities are data sets made public on the open source data set website of Stanford University, said Data sets publicly disclosed by enterprises include those disclosed by Microsoft and Yahoo! 3. A risk user prediction method based on graph network random walk according to claim 1, characterized in that the step 2) specifically includes the following steps: 21) Obtain feature data from the original data and filter out noise data, that is, edge data with too low weight; 22) Use relationship prediction models to supplement possible missing data; 23) Unify the coding of node numbers in the graph network; 24) Normalize the weights of edges in graph networks. 4. A risk user prediction method based on graph network random walk according to claim 3, characterized in that in the step 21), the type of characteristic data includes graph node characteristics of the data, edge weights, Directional features and risk nodes selected as initial nodes for subsequent random walks. 5. A risk user prediction method based on a random walk on a graph network according to claim 4, characterized in that the graph node feature is the user's label data, which represents the user's risk performance score, and its value It is 0 or 1, corresponding to there or no risk. 6. A risk user prediction method based on graph network random walk according to claim 3, characterized in that in step 22), supplementing possible missing data specifically includes: For data: linear interpolation supplement using linear models; For categorical features: select the feature value with the most occurrences of the category as the missing value to supplement. 7. A risk user prediction method based on graph network random walk according to claim 1, characterized in that the probability value is 0.9. 8. A risk user prediction method based on graph network random walk according to claim 1, characterized in that, in the process of random walk, in order to reduce the computational complexity, the access probability threshold δ=0.0001 is set, when When the random walk reaches a node and the access probability of the node is not 0 and less than δ, the random walk returns to the original seed node. 9. A risk user prediction method based on graph network random walk according to claim 8, characterized in that in step 4), when the risk score of the user to be predicted exceeds the set risk score threshold , then the user to be predicted is judged to be a risky user.