FORM 2
THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003
COMPLETE SPECIFICATION (See section 10, rule 13)
1. Title of the invention: DATA CLASSIFICATION
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor,
SERVICES LIMITED Nariman Point, Mumbai,
Maharashtra 400021, India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
[0001] The present subject matter relates, in general, to data classification and, particularly, but not exclusively, to data classification using parallel processing techniques.
BACKGROUND
[0002] Data classification involves organizing data into groups or clusters. Typically, data with similar attributes are classified into one group. Based on the size of data to be classified, a suitable data classification approach may be implemented. For instance, for classification of large datasets, such as Big Data, parallel processing techniques may be implemented.
BRIEF DESCRIPTION OF DRAWINGS
[0003] The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components.
[0004] Figure 1 illustrates a network environment for data classification, in accordance with an implementation of the present subject matter; and
[0005] Figure 2 illustrates a method for data classification in accordance with an implementation of the present subject matter.
DETAILED DESCRIPTION
[0006] For classifying datasets comprising large volume of data, such as Big Data, parallel processing techniques, such as MapReduce, may be implemented. In such parallel processing techniques, data to be classified is processed in parallel across a plurality of computing devices, for example, laptops, desktop computers,

mainframe computers, notebooks, and smart phones. Parallel processing of the data reduces the computational time associated with the classification of the data.
[0007] In a first stage of a known parallel processing technique, a plurality of data points of a dataset which is to be classified amongst a plurality of clusters is distributed among the computing devices. Each computing device is assigned a subset of data points which are to be classified. In accordance with said technique, each computing device generates cluster data for each of the data points assigned to it. The cluster data may include a centroid of the cluster into which the data point is classified and a set of field values associated with the data point.
[0008] In a second stage of the technique, based on corresponding cluster data, the data points are classified into groups. For instance, data points pertaining to same cluster may be classified into one group. Thus, for each cluster a corresponding group comprising the data points classified into that cluster is obtained.
[0009] Further, in the second stage, in order to improve the accuracy of classification, either a new centroid for each of the clusters is determined or the current centroid of each of the clusters is corrected, based on the corresponding groups. For either of the operations, each of the groups may be assigned to a computing device. In certain cases, for instance, where the number of computing device is limited, more than one group may be assigned to a single computing device.
[0010] Once the groups are assigned to corresponding computing devices, each computing device collates the cluster data associated with the each of the data points present in the group assigned to it. Once the data is collated, the computing device then either generates a new centroid based on the collated result or corrects the current centroid using the collated result.
[0011] As mentioned above, datasets comprising data of the order of Big Data is classified using such techniques. Thus, as may be understood, each group may include enormous volume of data points. Collation of cluster data at such large scale

may prove to be a time consuming task. Additionally, computing devices having limited storage space and computational capacity may not be able to successfully store and process such large volume of data. Thus, such computing devices may not be able to participate in the classification. Thus, scalability of the aforementioned approach is reduced. Further, in a case where more than one groups are assigned to a single computing devices, classification of the groups may prove to be a time consuming task. Further, once the new centroid is determined or the current centroid is corrected, the data points are then again classified and the process may be repeated again for improving the accuracy. In such a case, for aforementioned constraints, the classification of data may prove to be a cumbersome and time consuming task.
[0012] The present subject matter describes a system and a method for data classification. According to an implementation, a computing device, assigned with the task of classifying a subset of data points of a data set into a plurality of clusters, is to maintain a set of variables for each of the clusters. Each variable in the set of variables corresponds to a field of the dataset.
[0013] In operation, the computing device may assign a data point of the dataset to a cluster from the plurality of clusters based on a centroid associated with the cluster. On assigning the data point to the cluster, the computing device may update the set of variables associated with the cluster.
[0014] In an implementation, for each variable in the set of variables, the computing device may ascertain a field value associated with the field corresponding to the variable. The computing device may analyse the set of field values associated with the data point for ascertaining the field value.
[0015] Continuing with the above implementation, the computing device may update a current value of the variable based on the field value to obtain an updated value of the variable. In an example, the updated value may be obtained by adding the current value and the field value. In another example, the updated value may be

obtained by implementing a mathematical logic using the current value and the field value. For instance, a median based on the current value and the field value may be determined. The median may then be ascertained as the updated value of the variable. The computing device updates the rest of the variables in the set of variables in a similar manner. Thus for each data point assigned to the cluster, the computing device updates the set of variables associated with the cluster in a similar manner. As may be gathered, the computing device updates the set of variables corresponding to other clusters in a similar manner.
[0016] In an example, a tuple corresponding to the cluster may be generated. The tuple may include the updated value of each of the variables. The tuple further includes an identifier, for example, a cluster name or a cluster number, associated with the cluster. In an implementation, the tuple may be generated periodically. In another implementation, the tuple may be generated once all the data points from the subset are assigned amongst the clusters.
[0017] Based on the tuple, a new centroid for the cluster may be determined. In an implementation, the new centroid may be generated by the same computing device which generates the tuple. In another implementation, the new centroid may be generated by another computing device. In said implementation, the computing device which generated the tuple transmits the tuple to the other computing device.
[0018] As will be clear from the foregoing description, the number of tuples which are to be collated is significantly less than the size of cluster data which is collated in the second stage of processing. As a result, computation time associated with determination of the new centroid is reduced. Further, as the size of the data to be collated is reduced, computing devices having less processing and less memory storage may also be deployed for performing the computation. The reduced size of the data also facilitates faster exchange of the data amongst the computing devices. Thus, the overall computational time associated with classification of data points is reduced.

[0019] These and other advantages of the present subject matter would be described in greater detail in conjunction with the following figures. While aspects of described systems and methods can be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following device(s).
[0020] Figure 1 illustrates a network environment 100 for data classification. The network environment 100 includes a plurality of computing devices 102-1, 102-2, 102-3, …., and 102-N, hereinafter collectively referred to as computing devices 102 and individually referred to as the computing device 102. Examples of the computing device 102 may include, but are not limited to, a server, a laptop, a desktop computer, a mainframe computer, a smart phone, and the like.
[0021] In an example, the network environment 100 may be a computing network implementing parallel processing for classifying a plurality of data points of a dataset into a plurality of clusters (not shown in the figure). Each data point of the dataset may represent a set of field values corresponding to one or more fields of the dataset. For instance, for a customer dataset including fields, such as name, age, occupation, and salary, a data point of the dataset may represent a field value of each of the fields.. For classifying the data points, the data points may be distributed amongst the computing devices 102 in a manner such that each of the computing devices 102 is assigned a pool of data points. The pool of data points may be interchangeably referred to as a subset of data points. The pool of data points may include one or more data points from the plurality of data points. Each computing device 102 may then classify the subset of data points assigned to it.
[0022] The computing devices 102 may communicate with each other through a communication network 104, according to an embodiment of the present subject matter. The communication network 104 may be a wireless network, or a combination of wired and wireless network. The communication network 104 can be a collection of individual networks, interconnected with each other and functioning as

a single large network (e.g., the internet or an intranet). Examples of such individual networks include, but are not limited to, 3rd Generation Partnership Project (3GPP), Long Term Evolution (LTE), and the like. Further, depending on the technology, the communication network 104 includes various network entities, such as gateways, routers; however, such details have been omitted for ease of understanding.
[0023] In an implementation, the computing device 102 may include one or more processor(s) 106, interface(s) 108, and a memory 110 coupled to the processor(s) 106. The processor(s) 106 can be a single processing unit or a number of units, all of which could include multiple computing units. The processor(s) 106 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) 106 is configured to fetch and execute computer-readable instructions and data stored in the memory 110.
[0024] The interface(s) 108 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, a display unit, an external memory, and a printer. Further, the interface(s) 108 may enable the computing device 102 to communicate with other devices, such as web servers and external databases. The interface(s) 108 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the interface(s) 108 include one or more ports for connecting a number of computing systems with one another or to a network.
[0025] The memory 110 may include any non-transitory computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable

programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In one implementation, the computing device 102 also includes module(s) 112 and data 114.
[0026] The module(s) 112, amongst other things, include routines, programs, objects, components, data structures, etc., which perform particular tasks or implement data types. The module(s) 112 may also be implemented as, signal processor(s), state machine(s), logic circuitries, and/or any other device or component that manipulate signals based on operational instructions.
[0027] Further, the module(s) 112 can be implemented in hardware, instructions executed by a processing unit, or by a combination thereof. The processing unit can comprise a computer, a processor, such as the processor 106, a state machine, a logic array or any other suitable devices capable of processing instructions. The processing unit can be a general-purpose processor which executes instructions to cause the general-purpose processor to perform the required tasks or, the processing unit can be dedicated to perform the required functions.
[0028] In another aspect of the present subject matter, the module(s) 112 may be machine-readable instructions (software) which, when executed by a processor/processing unit, perform any of the described functionalities. The machine-readable instructions may be stored on an electronic memory device, hard disk, optical disk or other machine-readable storage medium or non-transitory medium. In one implementation, the machine-readable instructions can be also be downloaded to the storage medium via a network connection.
[0029] In one implementation, the module(s) 112 further includes a classification module 116 and other module(s) 118. The other modules 118 may include programs or coded instructions that supplement applications and functions of the computing device 102.

[0030] The data 114 serves, amongst other things, as a repository for storing data processed, received, and generated by one or more of the module(s) 112. The data 114 includes classification data 120 and other data 122. The other data 122 includes data generated as a result of the execution of one or more modules in the module(s) 112. In an example, the classification data 120 may include the set of field values associated with each of the plurality of data points.
[0031] In an example, the computing device 102-1 may be assigned a subset of data points, pertaining to the plurality of data points, which is to be classified amongst the plurality of clusters. In operation, the classification module 116 may assign a data point of the subset and in turn, the dataset, to a cluster from the plurality of clusters based on a centroid associated with the cluster. For identifying the cluster to which the data point is to be assigned, the classification module 116 may compute a distance, for example, Euclidean distance, between the data point and a centroid of each of the clusters. The classification module 116 may then select a cluster whose distance to the data point is shortest. Subsequently, the classification module 116 assigns the data point to the cluster.
[0032] Each of the clusters has a set of variables associated with it where each variable in the set of variable corresponds to a field of the dataset. In an example, for each of the set of variables, the classification module 116 may ascertain a field value associated with the field corresponding to the variable from the set of field values associated with the data point. For ascertaining the field value, the classification module 116 may access the classification data 120. As mentioned above, the classification data 120 stores the set of field values associated with each of the data points. The classification module 116 may retrieve the set of field values associated with the data point from the classification data 120. Subsequently, the classification module 116 may analyse the set of field values to identify the field corresponding to the variable for ascertaining the field value. On ascertaining the field value, the classification module 116 may update a current value of the variable based on the

field value to obtain an update value of the variable. In an example, the classification module 116 may add the field value to the current value of the variable to obtain the updated value. For instance, say, a variable corresponds to a field ‘age’ and has a current value 45 based on previously assigned data points. For a new data point assigned to the cluster, say a field value 20 is ascertained. Thus, in an example, the field value 20 may be added to the current value 45 to obtain the updated value, i.e., 64. In another example, a predetermined mathematical logic, for example, median or mode, may be implemented using the current value and the field value to obtain the updated value.
[0033] In an example, each of the cluster may also have at least one statistical variable associated with it. In an example, the classification module may increment the statistical variable by one for each data point classified in the cluster. Thus, the statistical variable may indicate the number of data points classified in the cluster.
[0034] Thus, the classification module 116 may determine an updated value of each of the set of variables associated with the cluster based on the set of field values associated with the data point assigned to the cluster. In an example, the classification module 116 may generate a tuple corresponding to the cluster. The cluster may include the update value of each of the variables and an identifier associated with the cluster. Examples of the identifier may include, but are not limited to, a cluster name and a cluster number. In an implementation, the classification module 116 may generate the tuple periodically. For instance, the classification module may generate the tuple, say, after every 50 data points assigned to the cluster. In another implementation, the classification module 116 may generate the tuple based on the data points assigned to the cluster.
[0035] In an implementation, the classification module 116 may transmit the tuple to another computing device, say, 102-2, over the communication network 104 for generation of a new centroid for the cluster. The computing device 102-2, may compute the new centroid using the tuple and one or more other tuples corresponding

to the cluster. In an example, the other tuples may be generated by one or more of the computing devices 102. In another example, the other tuples may be generated by one or more modules 112 (not shown in the figure), similar to the classification module 116, of the computing device 102-1. Once the tuples corresponding to the cluster are generated, the computing device 102-1 may transmit the tuples to the computing device 102-2.
[0036] In another implementation, the computing device 102-1 may generate the new centroid for the cluster based on the tuple. In said implementation, the computing device 102-1 may generate the new centroid based on the tuple and one or more other tuples corresponding to the cluster. The other tuples, in one example, may be generated by one or more of the computing devices 102 present in the network environment 100. In another example, the other tuples may be generated by one or more modules 112 (not shown in the figure), similar to the classification module 116, of the computing device 102-1..
[0037] Figure 2 illustrates a method 200 for data classification, according to an embodiment of the present subject matter. The order in which the method 200 is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method or any alternative methods. Additionally, individual blocks may be deleted from the method without departing from the spirit and scope of the subject matter described herein. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof.
[0038] The method 200 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The method may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a

communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
[0039] In an implementation, one or more of the method described herein may be implemented at least in part as instructions embodied in a non-transitory computer-readable medium and executable by one or more computing devices. In general, a processor, for example, a microprocessor, receives instructions from a non-transitory computer-readable medium, for example, a memory, and executes those instructions, thereby performing one or more method, including one or more of the method described herein. Such instructions may be stored and/or transmitted using any of a variety of known computer-readable media.
[0040] Referring to Figure 2, at block 202, a data point of a dataset is assigned to a cluster from a plurality of cluster. The data point represents a set of field values corresponding to one or more fields of the dataset. Further, a set of variables is associated with each of the plurality of clusters is maintained by a computing device performing the assigning of data points. Each variable in the set of variable corresponds to a field of the dataset. The set of variables associated with a cluster may also be referred to as cluster variables. In an example, the data point may be assigned based on a centroid of the cluster. In said example, Euclidean distance between the data point and a centroid of each of the clusters is computed. Subsequently, the data point is assigned to a cluster whose corresponding Euclidean distance to the data point is the shortest. In an implementation, the classification module 116 may assign the data point to the cluster.
[0041] At block 204, for each of the set of variables, a field value associated with the field corresponding to the variable is ascertained from the set of field values associated with the data point. In an example, the set of field values associated with the data point may be obtained from a data source. The data source may include the set of field values associated with each of the one or more data points of the dataset.

Once the set of field values is obtained, the set may be analysed for identifying the field corresponding to the variable. In an example, the classification module 116 may ascertain the field value.
[0042] At block 206, a current value of the variable is updated based on the field value. In an example, the current value of the variable may be updated by adding the field value to the current value of the variable. In another example, the current value may be updated using known mathematical logics, such as median, mode, and the like. On updation, an updated value of the variable is obtained. In an example, the classification module 116 may update the current value.
[0043] In an example, a tuple corresponding to the cluster may be generated. The tuple may include the updated value corresponding to each of the set of variables. The tuple may further include an identifier, such as a cluster number or a cluster name, associated with the cluster. In an implementation, the tuple may be generated periodically. In another implementation, the tuple may be generated when all the data points are assigned amongst the clusters. In said implementation, the updated value of each of the set of variables may represent a sum total of field values associated with the field corresponding to the variable determined based on the data points assigned to the cluster.
[0044] In an implementation, the computing device may generate a new centroid for the cluster based on the tuple and one or more tuples associated with the cluster in a manner as described above in Figure 1 description.. In another implementation, as described above in Figure 1 description, the computing device may transmit the tuple to another computing device for generating the new centroid..
Although implementations for methods and systems for data classification are described, it is to be understood that the present subject matter is not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as implementations for data classification.

I/We claim:
1. A computing device (102) comprising:
a processor (106); and
a classification module (116) coupled to the processor (106) to,
assign a data point of a dataset, to a cluster from a plurality of clusters based on a centroid associated with the cluster, wherein the data point represents a set of field values corresponding to one or more fields of the dataset, and wherein a set of variables is associated with each of the plurality of clusters, wherein each variable in the set of variables corresponds to a field of the dataset;
ascertain, for each of the set of variables, a field value associated with the field corresponding to the variable from the set of field values associated with the data point; and
update a current value of the variable based on the field value to obtain an updated value of the variable for generation of a new centroid for the cluster.
2. The computing device (102) as claimed in claim 1, wherein the classification module (116) further is to generate periodically, a tuple corresponding to the cluster, where the cluster comprises the updated value of each of the set of variables and an identifier associated with the cluster.
3. The computing device (102) as claimed in claim 1, wherein the classification module (116) further is to generate a tuple corresponding to the cluster, wherein the tuple comprises the updated value corresponding to each of the set of variables and an identifier associated with the cluster,

wherein the updated value is based on each of one or more data points of the dataset assigned to the cluster.
4. The computing device (102) as claimed in claim 2 or 3, wherein the classification module (116) further is to transmit the tuple to another computing device (102) over a communication network (104) for generation of the new centroid for the cluster.
5. The computing device (102) as claimed in claim 2 or 3, wherein the classification module (116) is to determine a new centroid for the cluster based on the tuple and one or more tuples corresponding to the cluster.
6. The computing device (102) as claimed in claim 1, wherein at least one statistical variable is associated with the cluster, wherein the at least one statistical variables indicates a number of the one or more data points assigned to the cluster.
7. A method for execution on a computing device (102), the method comprising:
assigning a data point of a dataset, to a cluster from a plurality of clusters based on a centroid associated with the cluster, wherein the data point represents a set of field values corresponding to one or more fields of the dataset, and wherein a set of variables is associated with each of the plurality of clusters, and wherein each variable in the set of variables corresponds to a field of the dataset;
ascertaining, for each of the set of variables, a field value associated with the field corresponding to the variable from the set of field values associated with the data point; and

updating a current value of the variable based on the field value to obtain an updated value of the variable for generation of a new centroid for the cluster.
8. The method as claimed in claim 7, wherein the method further comprises generating periodically, a tuple corresponding to the cluster, wherein the tuple comprises the updated value of each variable in the set of variables and an identifier associated with the cluster.
9. The method as claimed in claim 7, wherein the method further comprises generating a tuple corresponding to the cluster, wherein the tuple comprises the updated value of each variable in the set of variables and an identifier associated with the cluster, wherein the updated value is based on one or more data points of the dataset assigned to the cluster.
10. The method as claimed in claim 8 or 9, wherein the method further comprises determining, by the computing device (102), the new centroid for the cluster based on the tuple and one or more tuples corresponding to the cluster.
11. The method as claimed in claim 8 or 9, wherein the method further comprises transmitting the tuple to another computing device (102) for generating the new centroid for the cluster, wherein the other computing device (102) is communicatively coupled to the computing device (102) through a communication network (104).
12. The method as claimed in claim 11, wherein the method further comprises:
receiving, by the other computing device (102), the tuple from the computing device (102); and

determining the new centroid for the cluster based on the tuple and one or more tuples corresponding to the cluster.
13. The method as claimed in claim 7, wherein at least one statistical variable is associated with the cluster, wherein the at least one statistical variables indicates a number of the one or more data points assigned to the cluster.
14. A non-transitory computer-readable medium having embodied thereon a computer program for executing a method comprising:
assigning a data point of a dataset, to a cluster from a plurality of clusters based on a centroid associated with the cluster, wherein the data point represents a set of field values corresponding to one or more fields of the dataset, and wherein a set of variables is associated with each of the plurality of clusters, and wherein each variable in the set of variables corresponds to a field of the dataset;
ascertaining, for each of the set of variables, a field value associated with the field corresponding to the variable from the set of field values associated with the data point; and
updating a current value of the variable based on the field value to obtain an updated value of the variable for generation of a new centroid for the cluster.