WO2024260345A1 - High-entropy knn clustering method and device based on random traversal, and medium - Google Patents

Abstract

The present application relates to the field of electric digital data processing, and discloses a high-entropy KNN clustering method and device based on random traversal, and a medium. The method comprises: acquiring a sample set needing to be clustered; on the basis of a random traversal mode and category labels of other specified samples that have been classified before, classifying the specified samples; for the remaining samples to be classified other than prior samples in the sample set, selecting K prior samples closest to the samples to be classified as comparison samples; and on the basis of the mode of similarity difference and determined category labels of the comparison samples, obtaining category labels of the samples to be classified. The high-entropy effect of the prior samples is ensured. On the basis of the mode of similarity difference, the requirements of inter-category homogeneity and intra-category dissimilarity are effectively met, the high-entropy clustering process of all samples is implemented, and the requirements for high-entropy clustering are met.

Description

A high entropy KNN clustering method, device and medium based on random traversal

This application claims the priority of the Chinese patent application filed with the China Patent Office on June 19, 2023, with application number 202310720618.4 and invention name “A high entropy KNN clustering method, device and medium based on random traversal”, the entire contents of which are incorporated by reference in this application.

Technical Field

The present application relates to the field of electronic digital data processing, and in particular to a high entropy KNN clustering method, device and medium based on random traversal.

Background Art

K-Nearest Neighbor (KNN) is a supervised learning algorithm that can determine the state of a sample based on the states of its K nearest neighbors and is often used for sample classification. Generally speaking, the KNN algorithm can present the characteristics of being very different between classes and homogeneous within classes, that is, it can achieve the effect of high entropy between classes and low entropy within classes.

However, with the development of technology, some application requirements have emerged, such as homogeneity between classes and heterogeneity within classes. For example, when classifying multiple types of products or multiple types of data, it is only necessary to ensure that each type of product or data in each category meets a certain proportion. In this case, during the classification process, it is necessary to ensure the effect of low entropy between classes and high entropy within classes, which is difficult to achieve through the traditional KNN algorithm.

Summary of the invention

In order to solve the above problems, this application proposes a high entropy KNN clustering method based on random traversal, including:

Obtain a sample set that needs to be clustered, and select a number of specified samples from the sample set;

Based on the random traversal method, each designated sample is selected in turn from the plurality of designated samples, and for the designated sample, the designated sample is classified according to the category labels of other designated samples that have been classified previously. The designated sample is classified and the classified designated sample is used as the prior sample;

For the remaining samples to be classified except the priori samples in the sample set, K priori samples closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value;

Based on the different similarities and the determined category labels of the comparison samples, the category labels of the samples to be classified are obtained until all the samples to be classified are classified.

On the other hand, the present application also proposes a high entropy KNN clustering device based on random traversal, including:

at least one processor; and,

a memory communicatively coupled to the at least one processor;

The memory stores instructions that can be executed by the at least one processor, and the instructions are executed by the at least one processor so that the at least one processor can execute, for example, the above-mentioned high entropy KNN clustering method based on random traversal.

On the other hand, the present application also proposes a non-volatile computer storage medium storing computer executable instructions, wherein the computer executable instructions are configured as: the above-mentioned high entropy KNN clustering method based on random traversal.

The high entropy KNN clustering method based on random traversal proposed in this application can bring the following beneficial effects:

The prior samples obtained in the random traversal process can be used to ensure the high entropy effect of the prior samples based on the principle of distance in the random traversal process. Based on the method of different similarities, the requirements of homogeneity between classes and differences within classes are effectively met, and the high entropy clustering process of all samples is realized, which meets the needs of high entropy clustering.

BRIEF DESCRIPTION OF THE DRAWINGS

The drawings described herein are used to provide a further understanding of the present application and constitute a part of the present application. The illustrative embodiments of the present application and their descriptions are used to explain the present application and do not constitute an improper limitation on the present application. In the drawings:

FIG1 is a schematic diagram of a high entropy KNN clustering method based on random traversal in an embodiment of the present application;

FIG2 is a schematic diagram of classification of prior samples in a scenario in an embodiment of the present application;

FIG3 is a schematic diagram of the results of a traditional KNN clustering algorithm in an embodiment of the present application;

FIG4 is a schematic diagram of classification in different similarity modes in an embodiment of the present application;

FIG5 is a schematic diagram of classification results in different similarities according to an embodiment of the present application;

FIG6 is a schematic diagram of a high entropy KNN clustering device based on random traversal in an embodiment of the present application.

DETAILED DESCRIPTION

In order to make the purpose, technical solution and advantages of the present application clearer, the technical solution of the present application will be clearly and completely described below in combination with the specific embodiments of the present application and the corresponding drawings. Obviously, the described embodiments are only part of the embodiments of the present application, not all of the embodiments. Based on the embodiments in the present application, all other embodiments obtained by ordinary technicians in this field without making creative work are within the scope of protection of the present application.

The technical solutions provided by various embodiments of the present application are described in detail below in conjunction with the accompanying drawings.

As shown in FIG1 , the embodiment of the present application provides a high entropy KNN clustering method based on random traversal, including:

S101: Obtain a sample set that needs to be clustered, and select a number of specified samples from the sample set.

Different from the traditional KNN clustering, the purpose of high entropy KNN clustering in this paper is different. In the pre-acquired data set, several data are selected, which can be product data, image data, audio data, etc.

Several data are used as sample sets to cluster the sample sets. At this time, the purpose of clustering is no longer to gather data of the same or similar categories into one cluster, but to make the data of different categories meet the preset ratio in the clusters of the clustering results. For example, taking product data as an example, in each cluster finally obtained, the ratio of product quality meets the preset ratio, and the ratio of excellent products, good products, and poor products meets the ratio of 5:3:2, which can achieve the preset purpose.

In the sample set, a number of designated samples are selected. The designated samples are samples with identifiable characteristics (also called significant characteristics). For example, taking product data as an example, if the quality of some products is very good, or they have very obvious defects, they can be considered to have identifiable characteristics. Or, when recognizing image data, if the designated object is obviously present in the image, or if the designated object is obviously absent, it is considered to have identifiable characteristics. Have identifiable characteristics. Usually the number of samples selected is small compared to the sample set.

S102: Based on a random traversal method, each designated sample is selected in turn from the plurality of designated samples, and for the designated sample, the designated sample is classified according to the category labels of other designated samples that have been classified before, and the designated sample that has been classified is used as a priori sample.

Random traversal means that among all the specified samples, one specified sample is selected each time by random selection. After the category label of the specified sample is determined, the next specified sample is selected by random selection for classification until all the specified samples are traversed and the classification is completed.

Specifically, for the selected designated sample, determine the sample number of other designated samples that have been classified previously. Of course, if the sample number is 0 at this time, it means that the designated sample is the first sample, then a category label is randomly selected from all category labels as the category label of the designated sample. Here, it is assumed that the category label of the designated sample is defined as A, and the category to which it belongs is called category A.

If the number of samples is an integer multiple of the number of categories to be divided (the number of categories to be divided is the number of categories of the category label. For the convenience of explanation in this article, two categories are taken as an example), then the sum of the distances between the specified sample and the other specified samples corresponding to each category label is determined, and the category label corresponding to the highest sum of distances is used as the category label of the specified sample. Taking the number of categories of two categories as an example, when the number of samples is an even number, it is an integer multiple, and when the number of samples is an odd number, it is a non-integer multiple.

When the number of samples is not an integer multiple of the number of categories to be divided, the category label with the least number is selected from all the category labels corresponding to other specified samples as the category label of the specified sample.

Still taking the number of categories of two categories as an example, when it is classified into the second designated sample (as shown in Figure 2, in Figure 2, numbers 1 to 6 correspond to the first to sixth designated samples respectively, the icon of the hollow square represents category A, and the icon containing a cross in the square represents category B, and these six designated samples are used as examples for explanation), at this time only the first designated sample is classified into category A, and the category includes two categories, A and B. At this time, the number corresponding to category A is 1, and the number corresponding to category B is 0, then the second designated sample is classified into category B, and its category label is B.

When the third designated sample is classified, the distances to the first and second designated samples are calculated. If the distance to the second designated sample is large, it is classified into Class B according to the principle of distance. Otherwise, it is classified into Class A. Assuming that the third designated sample is classified into Class B, the number of samples corresponding to Class A and Class B is 1 and 2 respectively.

For the fourth designated sample, the sample with the largest number of samples is assigned according to the classification of the first three designated samples. The category with fewer items is classified as Class A.

For the fifth designated sample, since each category contains multiple designated samples before it, it is necessary to calculate the distance between it and the aforementioned four designated samples. The sum of the distances between it and the first and fourth designated samples of category A is D _A = d ₁ + d ₄ , and the sum of the distances between it and the second and third designated samples of category B is D _B = d ₂ + d ₃ , where D _A and D _B represent the sum of the distances between the fifth designated sample and other designated samples corresponding to categories A and B, respectively, and d ₁ to d ₄ are the distances between the fifth designated sample and the first to fourth designated samples, respectively. Then, D _A and D _B are compared. Assuming that D _A > D _B , the fifth designated sample is still classified into category A according to the principle of distance.

For the sixth designated sample, according to the classification of the first five designated samples, it is classified into the category with the least number of samples, which is Class B.

In addition, in some cases, when the number of categories reaches three or more, when the number of samples is not an integer multiple of the number of categories to be divided, the category label with the least number may contain multiple category labels, which are equal in number and the least in number. At this time, you can randomly select them as the category label with the least number this time, or calculate the distance and distance between the current specified sample and the specified samples under these category labels, and according to the principle of distance, select the category label with the higher distance and distance as the category label of the current specified sample.

S103: For the remaining samples to be classified except the priori samples in the sample set, select K priori samples closest to the samples to be classified as comparison samples; K is a preset positive integer value.

The K value should not be too large or too small. Generally speaking, it is related to the sample size of the sample set. At this time, determine the sample size corresponding to the sample set, and determine the corresponding K value and the number of selected samples in the classification process according to the sample size. The ratio of the K value to the sample size is a positive integer within [0.03, 0.09], and the K value is an odd number. When the sample size is 100, the K value can be 3, 5, 7, or 9.

The number of prior samples is at least K+1, and the number of prior samples in each category is the same. For example, when there are two categories, M=2, N=1, and the number of prior samples is at least K+1. K is often an odd number, so K+1 is an even number, which meets the requirement of the same number in each category. When there are more categories, K+1 may not be able to meet the requirement of the same number. In this case, the number of prior samples can be increased until the requirement is met.

S104: Based on the different similarities and the category labels of the comparison samples determined in the initial classification, the category labels of the samples to be classified are obtained until all the samples to be classified are classified.

As shown in Figure 3, according to the traditional KNN clustering algorithm, when clustering is still performed in the same similarity manner, the final result is still very different between classes and homogeneous within classes. At this time, the class is still in a low entropy state, which does not meet the requirements of this article.

Based on this, the method of similarity difference is adopted to determine the category labels that appear in the corresponding comparison samples for each sample to be classified, as well as the number of occurrences of each category label. Among all the category labels, the category label with the least number of occurrences is selected as the category label of the sample to be classified.

As shown in Figure 4, in addition to the A category represented by the hollow square icon and the B category represented by the cross icon in the square, there are also undetermined categories represented by the solid square icon. In Figure 4, taking K=5 as an example, the 5 comparison samples corresponding to the 7th sample (that is, the sample to be classified currently being confirmed) are the 1st to 3rd samples, and the 5th to 6th samples. After confirmation, the 1st and 5th samples belong to the A category, corresponding to 2 in number, and the 2nd, 3rd and 6th samples belong to the B category, corresponding to 3 in number. The A category has fewer comparison samples, so according to the principle of different similarities, the 7th sample is classified into the A category.

At this point, the final effect can be shown in Figure 5, achieving the effect of homogeneity between classes and great differences within classes. At this time, the class is in a high entropy state, which meets the requirements.

The prior samples obtained in the random traversal process can be used to ensure the high entropy effect of the prior samples based on the principle of distance in the random traversal process. Based on the method of different similarities, the requirements of homogeneity between classes and differences within classes are effectively met, and the high entropy clustering process of all samples is realized, which meets the needs of high entropy clustering.

In one embodiment, it is described above that the closest sample needs to be selected as a comparison sample. When calculating the distance between samples, the number of dimensions contained in each sample in the sample set is determined, and the distance between the sample to be classified and all other prior samples is calculated based on the number of dimensions, so as to select the K prior samples with the closest distance as comparison samples.

The number of dimensions usually includes one-dimensional to three-dimensional data. For example, text data contains one-dimensional data of text, 2D plane images contain two-dimensional data of pixels on the x-axis and y-axis, and product data contains three-dimensional data of appearance, function, and price.

When the samples in the sample set are one-dimensional, the samples to be classified and the prior samples are obtained by d _i = | _xi - _x1 | Here, d _i is the distance between the sample to be classified and the i-th prior sample, _xi is the coordinate of the i-th prior sample, and _x1 is the coordinate of the sample to be classified.

When the samples in the sample set are two-dimensional, The distance between the sample to be classified and the prior sample is obtained, where d _i is the distance between the sample to be classified and the i-th prior sample, (x _i , y _i ) is the coordinate of the i-th prior sample, and (x ₁ , y ₁ ) is the coordinate of the sample to be classified;

When the samples in the sample set are three-dimensional, The distance between the sample to be classified and the prior sample is obtained, where _di is the distance between the sample to be classified and the i-th prior sample, ( _xi , _yi , _zi ) is the coordinate of the i-th prior sample, and ( _x1 , _y1 , _z1 ) is the coordinate of the sample to be classified.

Of course, the distance between each specified sample can also be obtained through this distance calculation method, and the number of dimensions can also include more dimensions. In this case, a similar formula can be derived to calculate the distance between samples.

As shown in FIG6 , the present application also proposes a high entropy KNN clustering device based on random traversal, including:

at least one processor; and,

a memory communicatively coupled to the at least one processor;

The memory stores instructions that can be executed by the at least one processor, and the instructions are executed by the at least one processor so that the at least one processor can execute the high entropy KNN clustering method based on random traversal as described in any of the above embodiments.

The present application also proposes a non-volatile computer storage medium storing computer executable instructions, wherein the computer executable instructions are configured to be: the high entropy KNN clustering method based on random traversal described in any of the above embodiments.

Each embodiment in this application is described in a progressive manner, and the same or similar parts between the embodiments can be referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, for the device and medium embodiments, since they are basically similar to the method embodiments, the description is relatively simple, and the relevant parts can be referred to the partial description of the method embodiments.

The devices and media provided in the embodiments of the present application correspond one-to-one to the methods. Therefore, the devices and media also have similar beneficial technical effects as the corresponding methods. Since the beneficial technical effects of the methods have been described in detail above, the beneficial technical effects of the devices and media will not be repeated here.

It should be understood by those skilled in the art that the embodiments of the present application may be provided as methods, systems, or computers. Computer program product. Therefore, the present application may take the form of a complete hardware embodiment, a complete software embodiment, or an embodiment combining software and hardware. Moreover, the present application may take the form of a computer program product implemented on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) containing computer-usable program code.

The present application is described with reference to the flowchart and/or block diagram of the method, device (system) and computer program product according to the embodiment of the present application. It should be understood that each process and/or box in the flowchart and/or block diagram, and the combination of the process and/or box in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions can be provided to a processor of a general-purpose computer, a special-purpose computer, an embedded processor or other programmable data processing device to produce a machine, so that the instructions executed by the processor of the computer or other programmable data processing device produce a device for realizing the function specified in one process or multiple processes in the flowchart and/or one box or multiple boxes in the block diagram.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing device to work in a specific manner, so that the instructions stored in the computer-readable memory produce a manufactured product including an instruction device that implements the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions may also be loaded onto a computer or other programmable data processing device so that a series of operational steps are executed on the computer or other programmable device to produce a computer-implemented process, whereby the instructions executed on the computer or other programmable device provide steps for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

In a typical configuration, a computing device includes one or more processors (CPU), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in a computer-readable medium, in the form of random access memory (RAM) and/or non-volatile memory, such as read-only memory (ROM) or flash memory (flash RAM). Memory is an example of a computer-readable medium.

Computer-readable media include permanent and non-permanent, removable and non-removable media that can be used to store information by any method or technology. The information can be computer-readable instructions, data structures, program modules or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read-only memory (ROM), electrically erasable programmable EEPROM, flash memory or other memory technology, CD-ROM, DVD or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices or any other non-transmission media that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media does not include transitory media such as modulated data signals and carrier waves.

It should also be noted that the terms "include", "comprises" or any other variations thereof are intended to cover non-exclusive inclusion, so that a process, method, commodity or device including a series of elements includes not only those elements, but also other elements not explicitly listed, or also includes elements inherent to such process, method, commodity or device. In the absence of more restrictions, the elements defined by the sentence "comprises a ..." do not exclude the existence of other identical elements in the process, method, commodity or device including the elements.

The above is only an embodiment of the present application and is not intended to limit the present application. For those skilled in the art, the present application may have various changes and variations. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present application should be included in the scope of the claims of the present application.

Claims (8)

A high entropy KNN clustering method based on random traversal, including: A sample set to be clustered is obtained, and several designated samples are selected from the sample set; wherein several data are selected from the pre-acquired data set and the several data are used as the sample set; the several data are product data; the designated samples are samples with identifiable characteristics, and the identifiable characteristics include excellent product quality and defective products; Based on the random traversal method, each designated sample is selected in turn from the plurality of designated samples, and for the designated sample, the designated sample is classified according to the category labels of other designated samples that have been classified before, and the designated sample that has been classified is used as a priori sample; wherein, for the designated sample, the sample number of other designated samples that have been classified before is determined, and if the sample number is 0, a category label is randomly selected from all category labels as the category label of the designated sample; For the remaining samples to be classified except the priori samples in the sample set, K priori samples closest to the samples to be classified are selected as comparison samples; K is a preset positive integer value; Based on the different similarities and the determined category labels of the comparison samples, the category labels of the samples to be classified are obtained until all samples to be classified are classified so that in the clusters of the clustering results, data of different categories meet the preset proportions. The method according to claim 1, wherein obtaining the category label of the sample to be classified based on the manner in which the similarities are different and the category label determined for the comparison sample comprises: Determine the category labels that appear in the comparison sample, and the number of occurrences of each category label that appears; Among all the category labels, the category label with the least number of occurrences is selected as the category label of the sample to be classified. The method according to claim 1, wherein the number of the prior samples is at least K+1, and the number of prior samples included in each category is the same. The method according to claim 3, wherein, for the designated sample, classifying the designated sample according to the category labels of other designated samples that have been previously classified comprises: For the designated sample, determine the sample quantity of other designated samples that have been classified previously; If the number of samples is an integer multiple of the number of categories to be divided, the sum of distances between the designated sample and other designated samples corresponding to each category label is determined, and the category label corresponding to the highest distance sum is used as the category label of the designated sample; Otherwise, among all the category labels corresponding to the other specified samples, the category label with the least number is selected as the category label of the specified sample. The method according to claim 1, wherein selecting K prior samples closest to the sample to be classified as comparison samples comprises: Calculate the distance between the sample to be classified and all other prior samples according to the number of dimensions contained in each sample in the sample set; Select the K prior samples closest to each other as comparison samples. The method according to claim 5, wherein calculating the distance between the sample to be classified and all other prior samples comprises: When the samples in the sample set are one-dimensional, the distance between the sample to be classified and the priori sample is obtained by d _i =| _xi - _x1 |, wherein d _i is the distance between the sample to be classified and the i-th priori sample, _xi is the coordinate of the i-th priori sample, and _x1 is the coordinate of the sample to be classified; When the samples in the sample set are two-dimensional, Obtaining the distance between the sample to be classified and the priori sample, wherein d _i is the distance between the sample to be classified and the i-th priori sample, (x _i , y _i ) is the coordinate of the i-th priori sample, and (x ₁ , y ₁ ) is the coordinate of the sample to be classified; When the samples in the sample set are three-dimensional, The distance between the sample to be classified and the priori sample is obtained, wherein d _i is the distance between the sample to be classified and the i-th priori sample, (xi _{, yi} , z _i ) is the coordinate of the i-th priori sample, and ( _x1 , _y1 , _z1 ) is the coordinate of the sample to be classified. A high entropy KNN clustering device based on random traversal, comprising: at least one processor; and, a memory communicatively coupled to the at least one processor; The memory stores instructions executable by the at least one processor, and the instructions are executed by the at least one processor so that the at least one processor can perform the following steps: The method according to any one of claims 1 to 6. A non-volatile computer storage medium storing computer executable instructions, wherein the computer executable instructions are configured as: the method described in any one of claims 1 to 6.