CN103473255A - A data clustering method, system and data processing equipment - Google Patents

Abstract

The invention is applicable to the field of data processing, and provides a data clustering method, system and data processing equipment. The method comprises the steps of: inputting a data set composed of n objects with block data characteristics that need to be clustered and an expected category number k; selecting k block data objects from the data set as initial class centers; calculating each object The distance to the initial class center; according to the calculated distance, assign each block data object to its nearest center to form k disjoint classes; calculate the center of each class as the new class center; repeat execution The step of distributing each block data object to its nearest center according to the calculated distance to form k disjoint classes; and the step of calculating the center of each class as a new class center until the algorithm Converge to obtain the division result of the data set. The present invention can directly process the data with block characteristics without compressing the block data, avoiding the loss of information, and the obtained clustering result is better than the clustering effect after compressing the block data.

Description

A data clustering method, system and data processing equipment

technical field

The invention belongs to the field of data processing, and in particular relates to a data clustering method, system and data processing equipment.

Background technique

With the rapid development of data automatic generation and collection technology, many fields have produced massive data that record the details of people's behavior, which provides the possibility for behavior pattern mining. These data that describe the behavior of the collected objects have a common feature, that is, the behavior of each object is described by a collection of multiple records. We call the data set that records the behavior characteristics of the object a block of data. For example, a customer's purchase behavior or call behavior is reflected by the customer's purchase details or call details in a certain period of time. Through in-depth mining of block data, it helps us analyze and predict customer behavior. However, current machine learning algorithms cannot directly process block data, and must be converted into standard data for processing, so that the potential behavioral characteristics existing in the data may be ignored.

Contents of the invention

The purpose of the present invention is to provide a data clustering method, system and data processing equipment, aiming to solve the problem that the current machine learning algorithm in the prior art cannot directly process the block data, and it must be converted into standard data for processing. Dealing with the problem that potential behavioral features present in the data may be overlooked.

The present invention is realized like this, a kind of data clustering method, described method comprises the following steps:

Input a data set composed of n objects with block data characteristics that need to be clustered and the expected number of categories k;

Selecting k block data objects as initial class centers from the data set;

Calculate the distance from each object to the initial class center;

According to the calculated distance, assign each block data object to its nearest center, forming k disjoint classes;

Calculate the center of each class as the new class center;

Repeating the step of distributing each block data object to its nearest center according to the calculated distance to form k disjoint classes; and the step of calculating the center of each class as a new class center, Until the algorithm converges, the division result of the data set is obtained.

Another object of the present invention is to provide a data clustering system, said system comprising:

The input module is used to input a data set composed of n objects with block data characteristics that need to be clustered and an expected number of categories k;

A selection module is used to select k block data objects from the data set as initial class centers;

A distance calculation module, used to calculate the distance from each object to the initial class center;

An assignment module, configured to assign each block data object to its nearest center according to the calculated distance, forming k disjoint classes;

The class center calculation module is used to calculate the center of each class as a new class center;

The loop control module is used to control the repeated execution of the steps of allocating objects and calculating the class center until the algorithm converges and obtains the division result of the data set.

Another object of the present invention is to provide a data processing device comprising the above-mentioned data clustering system.

In the present invention, the data set is divided into different categories through an iterative process, so that the criterion function for evaluating the clustering performance can be optimized. First, k (expected number of categories) block data objects are randomly selected from the data set as the initial class center; then, according to the description of the distance between the block data, the distance between each block object in the data set and the initial class center is calculated, and the Each block object is assigned to the nearest center to form k classes; the center of each class is calculated as the new class center by the principle of inclusion and exclusion; the steps of allocating objects and calculating the class center are repeated until the algorithm converges. The embodiment of the present invention can rapidly cluster block data widely existing in the real world, and is an efficient and practical division and clustering method. The embodiment of the present invention can directly process the data with block characteristics without compressing the block data, avoiding the loss of information, and the obtained clustering result is better than the clustering effect after compressing the block data. In addition, the embodiments of the present invention can also handle large-scale data.

Description of drawings

FIG. 1 is a schematic diagram of the implementation flow of a data clustering method provided by an embodiment of the present invention.

Fig. 2 is a graph of clustering results of 34 cities provided by the embodiment of the present invention.

Fig. 3 is a schematic structural diagram of a data clustering system provided by an embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and beneficial effects of the present invention more clear, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

Please refer to Fig. 1, the implementation process of the data clustering method provided by the embodiment of the present invention, which includes the following steps:

In step S101, input a data set composed of n objects with block data characteristics that need to be clustered and an expected number of categories k;

In the embodiment of the present invention, it is assumed that the data set to be clustered is X={x ₁ ,x ₂ ,L,x _n }, where $x_i=\left[\begin{array}{c}{x}_{i,\mathrm{1,1}},x_{i,\mathrm{1,2}},L,x_{i,1,m}\\ x_{i,\mathrm{2,1}},x_{i,\mathrm{2,2}},L,x_{i,2,m}\\ L\\ x_{i,r,1},x_{i,r,2},L,x_{i,r,m}\end{array}\right]$ is the i-th object described by m attributes and r detail records, we call _xi a block data object. k is the desired number of categories.

In step S102, k block data objects are selected from the data set as initial class centers;

In the embodiment of the present invention, the step of selecting k block data objects from the data set X as the initial class centers c ₁ , c ₂ , L, c _k is specifically: randomly select k block objects from the data set X as the initial class center.

In step S103, calculate the distance from each object to the initial class center;

In step S104, according to the calculated distance, each block data object is assigned to its nearest center to form k disjoint classes;

进行度量，其中x,y表示两个块数据对象，A_i,B_i分别表示两个对象在i个属性下的域值，m为描述对象的特征数或属性数。In the embodiment of the present invention, the distance between the objects depends on the difference between the object attribute values, and the distance between the block data objects adopts the formula

Perform measurement, where x, y represent two block data objects, A _i , B _i respectively represent the domain values of the two objects under the i attribute, and m is the number of features or attributes describing the object.

In step S105, calculate the center of each class as the new class center;

In the embodiment of the present invention, at first by calculating the mean value of all object detail numbers in this class as the record number r to be included in the class center of this class; The frequency of occurrence, if the number of domain values is greater than r, select the first r values with the highest frequency as the representative of the dimension, otherwise, repeatedly take the domain values in the order of frequency from high to low until enough r values are taken; Repeat the above steps to get m columns of representatives, which constitute the class center of this class.

In step S106, the steps of steps S104 and S105 are repeatedly executed until the algorithm converges, and the division result of the data set is obtained.

In the embodiment of the present invention, by calculating the distance between the front and rear class centers, if the distance between the two is less than a given threshold, the algorithm ends.

The specific steps implemented in this example are described in detail below in conjunction with the method provided by the embodiment of the present invention as follows:

1) We downloaded the weather data of 34 provincial capital cities (including Hong Kong and Macau) in 2011 from http://www.wunderground.com/. Except for Shanghai, which has 364 days of data, other cities have 365 days of data , so one year's data of each city is a typical block data. For convenience, we selected 16 attributes with no missing values to describe the characteristics of weather data. Since the attribute is a numerical feature, we discretized the numerical data into 30 categorical values using a uniform quantization method.

2) Assuming that the expected number of categories is 2, two cities, Taiyuan and Wuhan, are selected as the initial category centers.

3) Use the defined distance formula to calculate the distance between each city and Taiyuan and Wuhan, and assign each block data object to the nearest center.

4) Compute the class centers in each class.

5) Judging whether the distance between the new class center and the initial class center is less than a given threshold.

6) If less than, end, otherwise go to step 3) until the algorithm converges.

7) The clustering results are shown in Figure 2, where circles and five-pointed stars indicate the two categories, and triangles indicate that the city has no weather data in 2011.

Please refer to FIG. 3 , which shows the structure of the data clustering system provided by the embodiment of the present invention. For ease of description, only parts related to the embodiments of the present invention are shown. The data clustering system includes: an input module 101 , a selection module 102 , a distance calculation module 103 , an allocation module 104 , a class center calculation module 105 , and a cycle control module 106 . The data clustering system may be a software unit, a hardware unit or a combination of software and hardware built into the data processing device.

Input module 101, is used for inputting the data set that needs clustering to form with the n object of block data feature and expected category number k;

In the embodiment of the present invention, it is assumed that the data set to be clustered is X={x ₁ ,x ₂ ,L,x _n }, where $x_i=\left[\begin{array}{c}{x}_{i,\mathrm{1,1}},x_{i,\mathrm{1,2}},L,x_{i,1,m}\\ x_{i,\mathrm{2,1}},x_{i,\mathrm{2,2}},L,x_{i,2,m}\\ L\\ x_{i,r,1},x_{i,r,2},L,x_{i,r,m}\end{array}\right]$ is the i-th object described by m attributes and r detail records, we call _xi a block data object. k is the desired number of categories.

A selection module 102, configured to select k block data objects from the data set as initial class centers;

In the embodiment of the present invention, the selection module 102 is specifically configured to randomly select k block objects from the data set X as initial class centers.

Distance calculation module 103, for calculating the distance from each object to the initial class center;

Assignment module 104, for according to the calculated distance, assign each block data object to its nearest center, form k disjoint classes;

进行度量，其中x,y表示两个块数据对象，A_i,B_i分别表示两个对象在i个属性下的域值，m为描述对象的特征数或属性数。In the embodiment of the present invention, the distance between the objects depends on the difference between the object attribute values, and the distance between the block data objects adopts the formula

Perform measurement, where x, y represent two block data objects, A _i , B _i respectively represent the domain values of the two objects under the i attribute, and m is the number of features or attributes describing the object.

The class center calculation module 105 is used to calculate the center of each class as a new class center;

In the embodiment of the present invention, at first by calculating the mean value of all object detail numbers in this class as the record number r to be included in the class center of this class; The frequency of occurrence, if the number of domain values is greater than r, select the first r values with the highest frequency as the representative of the dimension, otherwise, repeatedly take the domain values in the order of frequency from high to low until enough r values are taken; Repeat the above steps to get m columns of representatives, which constitute the class center of this class.

The loop control module 106 is used to control the repeated execution of the steps of allocating objects and calculating the class center until the algorithm converges and obtains the division result of the data set.

In the embodiment of the present invention, by calculating the distance between the front and rear class centers, if the distance between the two is less than a given threshold, the algorithm ends.

In summary, the embodiment of the present invention divides the data set into different categories through an iterative process, so that the criterion function for evaluating the clustering performance can be optimized. First, k (expected number of categories) block data objects are randomly selected from the data set as the initial class center; then, according to the description of the distance between the block data, the distance between each block object in the data set and the initial class center is calculated, and the Each block object is assigned to the nearest center to form k classes; the center of each class is calculated as the new class center by the principle of inclusion and exclusion; the steps of allocating objects and calculating the class center are repeated until the algorithm converges. The embodiment of the present invention can rapidly cluster block data widely existing in the real world, and is an efficient and practical division and clustering method. The embodiment of the present invention can directly process the data with block characteristics without compressing the block data, avoiding the loss of information, and the obtained clustering result is better than the clustering effect after compressing the block data. In addition, the embodiments of the present invention can also handle large-scale data.

Those of ordinary skill in the art can understand that all or part of the steps in the method of the above-mentioned embodiments can be completed by instructing related hardware through a program, and the program can be stored in a computer-readable storage medium, and the storage Media such as ROM/RAM, magnetic disk, optical disk, etc.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims (8)

1. A data clustering method, characterized in that said method comprises the following steps: Input a data set composed of n objects with block data characteristics that need to be clustered and the expected number of categories k; Selecting k block data objects as initial class centers from the data set; Calculate the distance from each object to the initial class center; According to the calculated distance, assign each block data object to its nearest center, forming k disjoint classes; Calculate the center of each class as the new class center; Repeating the step of distributing each block data object to its nearest center according to the calculated distance to form k disjoint classes; and the step of calculating the center of each class as a new class center, Until the algorithm converges, the division result of the data set is obtained. 2. The method according to claim 1, wherein it is assumed that the data set to be clustered is X={x ₁ , x ₂ , L, x _n }, where $x_i=\left[\begin{array}{c}{x}_{i,\mathrm{1,1}},x_{i,\mathrm{1,2}},L,x_{i,1,m}\\ x_{i,\mathrm{2,1}},x_{i,\mathrm{2,2}},L,x_{i,2,m}\\ L\\ x_{i,r,1},x_{i,r,2},L,x_{i,r,m}\end{array}\right]$ is the i-th object described by m attributes and r detailed records, and x _i is called a block data object; k is the expected number of categories. 3. The method according to claim 1, wherein the step of selecting k block data objects from the data set as the initial class center is specifically: randomly selecting k block objects from the data set X as the initial class center. 4. The method according to claim 1, wherein the distance between the objects depends on the difference between the object attribute values, and the distance between the block data objects adopts the formula

Perform measurement, where x, y represent two block data objects, A _i , B _i respectively represent the domain values of the two objects under the i attribute, and m is the number of features or attributes describing the object. 5. The method according to claim 1, characterized in that, at first by calculating the mean value of all object detailed numbers in the class as the record number r to be included in the class center of the class; The frequency of elements appearing in different objects in this class. If the number of domain values is greater than r, select the first r values with the highest frequency as the representative of this dimension. Otherwise, the domain values are repeatedly selected in the order of frequency from high to low. , until enough r values are taken; repeat the above steps to obtain m columns of representatives, which constitute the class center of this class. 6. A data clustering system, characterized in that the system comprises: The input module is used to input a data set composed of n objects with block data characteristics that need to be clustered and an expected number of categories k; A selection module is used to select k block data objects from the data set as initial class centers; A distance calculation module, used to calculate the distance from each object to the initial class center; An assignment module, configured to assign each block data object to its nearest center according to the calculated distance, forming k disjoint classes; The class center calculation module is used to calculate the center of each class as a new class center; The loop control module is used to control the repeated execution of the steps of allocating objects and calculating the class center until the algorithm converges and obtains the division result of the data set. 7. The system according to claim 6, wherein the selection module is specifically configured to randomly select k block objects from the data set X as initial class centers. 8. A data processing apparatus comprising a system as claimed in any one of claims 6 or 7.

Images