JP2014164618A - Frequent pattern extraction device, frequent pattern extraction method, and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To extract a versatile workflow when a plurality of users cooperatively work by operating a plurality of files.SOLUTION: A frequent pattern extraction device comprises: a center cluster extraction unit 3273 which extracts a center file cluster that becomes a center of a workflow; a subordinate cluster identification unit 3275 which identifies subordinate file clusters included in the same workflow as the center file cluster; a sequence extraction unit 3276 which extracts a set of operation sequences related to the center file cluster and the subordinate file clusters for each user on the basis of operation histories concerning files of the center file cluster and files of the subordinate file cluster; and a frequent pattern extraction unit 3277 which extracts a frequent pattern as a workflow on the basis of the set of operation sequences extracted by the sequence extraction unit 3276.

Description

  The present invention relates to a frequent pattern extraction device and a frequent pattern extraction method for extracting a time-series frequent pattern from an operation history of each user for each item in a plurality of items, and a program for causing a computer to execute the frequent pattern extraction method About.

  Conventionally, many methods have been proposed in which a user's item operation history is analyzed, a characteristic frequent pattern is extracted, and the extracted pattern is used to improve the user's operation efficiency. For example, after viewing the page A after analyzing the web access log and extracting the pattern such as carefully viewing the page F, the user who viewed the page A can see the page F next. There are techniques to recommend.

  There has also been proposed a method of extracting a work flow (workflow) by analyzing a file operation history of a user in an office.

  For example, Patent Document 1 below proposes a method for estimating a work procedure using a history including image information regarding processing performed by an image processing apparatus such as a printer or a copier. A characteristic feature of this method is that form determination is performed based on the similarity of the feature amounts of document images, and the logs of a large number of accumulated document images are classified into sets for the same type of form template. As a result, “Form A forms are scanned after Nakamura (section member) prints and stamps, then Suzuki (section manager) copies after the seal, and finally Tanaka (section manager scans after the seal”. Such a workflow can be extracted.

  Further, for example, Patent Document 2 below proposes a method for generating a workflow including a branch from a history of operations on a document in an office. In this method, operation history records are arranged in chronological order as nodes in the form of a tree, and nodes that have some common attributes (file name, operator, operation type, etc.) are combined. By doing so, workflows that include branches and connections are extracted.

JP 2009-224958 A JP 2010-191709 A

Agrawal, R. and Srikant, R., "Fast Algorithms for Mining Association Rules", Proceedings of the 20th VLDB Conference, 1994, p487-499 J. Pei, J. Han, B. Mortazavi-Asl, Q. Checn, U. Dayal, and M.C. Hsu, "PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth", Proceedings of ICDE, 2001, p215-224 Jian Pei, Haixun Wang, Jian Liu, Ke Wang, Jianyong Wang, and Philip S. Yu, "Discovering Frequent Closed Partial Orders from Strings", IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 18, NO. 11, NOVEMBER 2006, p1467-1481

  However, the conventional method described above has the following two problems.

  First, the first problem is that only a workflow limited to a single document (single item) can be extracted. In both Patent Document 1 and Patent Document 2, by summarizing the operation history for each single document, it is estimated what kind of user will perform what operation on that document in what order. ing. However, in many office workflows, a plurality of users (a plurality of items) are handled in cooperation with a plurality of users, and such a workflow cannot be extracted by the above-described conventional method.

  The second problem is that a workflow in which a plurality of users work in parallel cannot be extracted. For example, after Mr. A works, Mr. B and Mr. C can work independently and in parallel, and after both Mr. B and Mr. C work are completed, Mr. D can start working. It is a simple workflow. In Patent Document 2, a workflow including branching and joining can be handled, but the branching and joining referred to here is different from the branching and joining in the parallel work that we say. In Patent Document 2, branching is an IF-THEN rule. For example, in a workflow for creating a request for quotation, the workflow is such that the person in charge of the request, which is the next flow, is switched according to the type of the estimated article. . In other words, the actual work flow is one way, and it is not the work flow that multiple users say we perform independently and in parallel, and such a workflow cannot be extracted.

  That is, in the above-described conventional method, only a limited workflow can be extracted when a plurality of users cooperate with each other to operate a plurality of items because of the two problems described above.

  The present invention has been made in view of the problems caused by the above-described conventional method, and a mechanism for realizing a more versatile workflow extraction when a plurality of users cooperate and operate a plurality of items. The purpose is to provide.

The frequent pattern extraction device of the present invention is a frequent pattern extraction device that extracts a time-series frequent pattern from each user's operation history for each item in a plurality of items, and the similarity between the items in the plurality of items is determined. Based on, a clustering means for clustering the plurality of items into a plurality of item clusters, a center cluster extraction means for extracting a center item cluster that is the center of the frequent pattern from the plurality of item clusters, and the plurality of the plurality of items. Based on an operation history of an item belonging to the central item cluster and an item belonging to the subordinate item cluster, a subordinate cluster specifying means for specifying a subordinate item cluster included in the same frequent pattern as the central item cluster from among the item clusters A sequence extracting means for extracting a set of operation sequences of the central item cluster and the subordinate item cluster for each user, and a frequent pattern for extracting the frequent pattern based on the set of operation sequences extracted by the sequence extracting means Extraction means.
Further, the present invention includes a frequent pattern extraction method by the above-described frequent pattern extraction apparatus and a program for causing a computer to execute the frequent pattern extraction method.

  According to the present invention, when a plurality of users collaborate to operate a plurality of items and perform work, a more general workflow extraction including a pattern in which the users work independently and in parallel is performed. Can be realized. This makes it possible to improve work efficiency, such as navigating user item operations, using this workflow.

It is a schematic diagram which shows an example of the apparatus structure of the frequent pattern extraction system which concerns on embodiment of this invention. It is a block diagram which shows an example of an internal structure of each apparatus shown in FIG. It is a block diagram which shows an example of a function structure of the file management system constructed | assembled in the file management server shown in FIG. It is a figure which shows embodiment of this invention and shows an example of the file operation information stored as a file operation history in the operation history database shown in FIG. 4 is a flowchart illustrating an example of a processing procedure of workflow extraction processing by the workflow extraction unit illustrated in FIG. 3 according to the embodiment of this invention. 4 is a flowchart illustrating an example of a processing procedure of workflow extraction processing by the workflow extraction unit illustrated in FIG. 3 according to the embodiment of this invention. It is a figure which shows embodiment of this invention and shows an example of the workflow made into the extraction object by the workflow extraction part shown in FIG. It is a figure which shows embodiment of this invention and shows an example of the file operation information stored as a file operation history in the operation history database shown in FIG. It is a figure which shows embodiment of this invention and shows an example of the similarity between files by the copy relationship of a file. It is a figure which shows embodiment of this invention and shows an example which carried out the hierarchical clustering of the file in the file operation information shown in FIG. FIG. 9 is a diagram illustrating an example in which a user's file operations are mapped in time series for each file in the file operation information illustrated in FIG. 8 according to the embodiment of this invention. FIG. 9 is a diagram illustrating an example in which user file operations are mapped in time series for each file cluster in the file operation information illustrated in FIG. 8 according to the embodiment of this invention. FIG. 9 is a diagram illustrating an example in which a user's file operation is mapped in time series for each file belonging to FC1 and FC2 in the file operation information illustrated in FIG. 8 according to the embodiment of the present invention. It is a figure which shows embodiment of this invention and shows an example of a file operation sequence and a file cluster operation sequence. It is a figure for demonstrating embodiment of this invention and explaining sequential pattern mining. It is a figure which shows embodiment of this invention and shows an example of the workflow extracted in step S604 of FIG.

  Hereinafter, embodiments (embodiments) for carrying out the present invention will be described with reference to the drawings.

  In the embodiment of the present invention, the item is a file having a folder (or directory) structure. In this embodiment, a file is targeted as an item. However, the present invention is not limited to this.

FIG. 1 is a schematic diagram illustrating an example of a device configuration of a frequent pattern extraction system according to an embodiment of the present invention.
The frequent pattern extraction system is realized as a client-server model. Specifically, the frequent pattern extraction system according to the present embodiment includes a network 101, a terminal A102, a terminal B103, a terminal C104, and a file management server 105 as shown in FIG.

  The terminal A102, the terminal B103, the terminal C104, and the file management server 105 are connected via the network 101, and exchange various types of information with each other. The user performs file operations such as file registration, browsing, and deletion using dedicated client tools on the terminals A102, B103, and C104, respectively.

FIG. 2 is a block diagram illustrating an example of an internal configuration of each apparatus illustrated in FIG.
1 includes a control unit 201, a bus 202, a memory unit 203, a large-scale storage unit 204, a display unit 205, an input unit 206, an output unit 207, and a network connection unit 208, as shown in FIG. It is comprised.

  The control unit 201 includes, for example, a CPU and the like, and comprehensively controls operations in the device.

  The bus 202 connects the control unit 201, the memory unit 203, the large-scale storage unit 204, the display unit 205, the input unit 206, the output unit 207, and the network connection unit 208 so that they can communicate with each other. The control unit 201 controls the operation of the device in an integrated manner by controlling each unit (203 to 208) of the device via the bus 202.

  The memory unit 203 is an electronic storage device composed of, for example, a RAM or a ROM. The control unit 201 operates in accordance with programs and data stored in the memory unit 203 and controls each unit of the device connected via the bus 202.

  The large-scale storage unit 204 is a storage device configured by, for example, a hard disk or an optical disk.

  A display unit 205 is a display device that displays a document, an image, and the like to a user who uses the system.

  The input unit 206 is, for example, a pointing device such as a mouse, a stick, or a pad for inputting an instruction or the like linked to the display content of the display unit 205. In addition, you may use the apparatus which serves as the display part 205 and the input part 206, such as a display with a touchscreen function.

  The output unit 207 is, for example, a printer device that outputs electronic data to paper.

  The network connection unit 208 is a network interface for taking in electronic data from the outside of the apparatus or transmitting electronic data to the outside of the apparatus.

  2 may be configured as a single general-purpose computer such as a PC, or may be constructed in an electronic device such as an MFP. Alternatively, a plurality of computers and servers connected to each other and a set of peripheral devices such as a display and a PDA may be used.

  FIG. 3 is a block diagram showing an example of a functional configuration of the file management system 320 constructed in the file management server 105 shown in FIG. In FIG. 3, the user terminal 310 corresponds to the terminal A102, the terminal B103, or the terminal C104, and a client tool is constructed. The file management server 105 in which the file management system 320 is constructed is a frequent pattern extraction apparatus according to an embodiment of the present invention (frequent pattern extraction that extracts a time-series frequent pattern from each user's operation history for each item in a plurality of items. Device).

  The file management system 320 includes an operation acquisition unit 321, a file management unit 322, a database 323, an operation history management unit 324, an operation history database 325, an information transmission unit 326, and a workflow extraction unit 327.

  In the present embodiment, the workflow extraction unit 327 having the workflow extraction function is configured in the file management system 320, but the present invention is not limited to this form. For example, the file management function and the workflow extraction function may be individually constructed, or the workflow extraction function may be implemented by being incorporated in another system different from the file management system 320. In the present embodiment, the file management system 320 is implemented in the client server model. However, the present invention is not limited to this mode, and can be implemented by, for example, a single client.

Here, an example of a correspondence relationship between the components (321 to 327) illustrated in FIG. 3 and the components illustrated in FIG. 2 will be described.
For example, the operation acquisition unit 321 and the information transmission unit 326 illustrated in FIG. 3 are configured from the programs stored in the control unit 201 and the memory unit 203 illustrated in FIG. 2 and the network connection unit 208.
Further, for example, the file management unit 322, the operation history management unit 324, and the workflow extraction unit 327 illustrated in FIG. 3 are configured from the programs stored in the control unit 201 and the memory unit 203 illustrated in FIG.
For example, the large-scale storage unit 204 illustrated in FIG. 2 includes a database 323 and an operation history database 325.

  The operation acquisition unit 321 acquires file operation information input from a client tool on the user terminal 310. Then, the operation acquisition unit 321 transmits the acquired file operation information to the file management unit 322 and the operation history management unit 324.

  The file management unit 322 receives the file operation information transmitted from the operation acquisition unit 321 and performs a predetermined file operation process in cooperation with the database 323 based on the file operation information. The file operation mentioned here refers to, for example, new file registration, open, copy, delete, and operation on a folder, and the processing content is the same as that of a general file management system. Information on the processing result is sent to the user terminal 310 through the information transmission unit 326 and displayed on the client tool on the user terminal 310.

  The database 323 stores information on files and folders managed by the file management system 320, user information of users who use the file management system 320, and the like. The user information includes not only individual user information such as a user name and a user ID, but also information related to a user group such as a group to which the user belongs and a list of users belonging to the group.

  The operation history management unit 324 receives the file operation information transmitted from the operation acquisition unit 321 and stores the file operation information as a file operation history in the operation history database 325 for management.

  The operation history database 325 stores file operation information from the operation history management unit 324 as a file operation history.

FIG. 4 is a diagram illustrating an example of file operation information stored as a file operation history in the operation history database 325 illustrated in FIG. 3 according to the embodiment of this invention.
In FIG. 4, a log ID 401 is a code for uniquely identifying file operation information. Time 402 represents time information when the file operation was performed. The user ID 403 is a code for identifying the user who performed the file operation. The file ID 404 is a code for identifying the operation target file. The operation event 405 represents the type of the file operation event that has been executed. The file operation information shown in FIG. 4 is an example, and the present invention is not limited to this. In the following, operations on files may be omitted for the sake of simplicity, but in reality, files and their operations are treated as a set, and when file operations match, both the file and its operations match. Pointing.

Here, it returns to description of FIG. 3 again.
The information transmission unit 326 transmits information from the file management unit 322 to the user terminal 310.

  The workflow extraction unit 327 performs processing for extracting a workflow. The workflow mentioned here refers to the flow of work for achieving a certain purpose, and can be represented by a graph structure in which a user and a file operation are nodes.

FIG. 7 is a diagram illustrating an example of a workflow to be extracted by the workflow extraction unit 327 illustrated in FIG. 3 according to the embodiment of this invention.
In FIG. 7, a node 701 represents that the user A performs an operation on a file included in FC1 (File Cluster 1). Here, FC1 (708) is a file cluster to which File1 and File6 belong as shown in FIG. As described above, each node of the workflow is expressed as an operation on the file cluster rather than a file operation because the file handled in each workflow is often different. For example, in the case of a workflow for creating an estimate, the estimate file to be created for each customer is different. Therefore, in order to represent as one workflow, it is necessary to handle the estimate file for each customer as a group. That is, in FC1 (708), File1 and File6 each represent an estimate for another customer, and FC1 (708) represents a set of these estimates. Replacing such a file as a file cluster is called file abstraction.

  In FIG. 7, a branch 702 represents a branch of work, and indicates that the work of the node 703 and the node 704 can be performed independently and in parallel after the work of the node 701 is completed. That is, in the example of FIG. 7, after the user A performs an operation on the FC1, the user B and the user C perform an operation on the FC1 in parallel. At this time, the operation of the user B and the operation of the user C are not in order, and either may perform the operation first, or these operations may be performed simultaneously.

  In FIG. 7, a connection 705 represents a connection of work. There are synchronous and asynchronous in the coupling 705. Synchronous means that the work after the combination can be performed only when all the work before the combination is completed. Asynchronous is when the part of the work before the combination is completed. The work after the combination can be performed. For example, in the example of FIG. 7, assuming that the coupling 705 is synchronous, the user D can perform an operation on the FC 2 at the node 706 when both the operations on the FC 1 by the user B and the user C are completed.

  In FIG. 7, a node 706 represents that the user D performs an operation on a file belonging to FC2 (File Cluster 2). Here, FC2 (709) is a file cluster to which File2 and File8 belong, as shown in FIG.

  In FIG. 7, a node 707 represents that the user E performs an operation on a file belonging to FC1.

  As described above, the workflow according to the embodiment of the present invention includes a branching / joining pattern in which a plurality of users operate a plurality of items, and each user performs an operation in parallel independently. It is.

Here, it returns to description of FIG. 3 again.
As shown in FIG. 3, the workflow extraction unit 327 includes a similarity calculation unit 3271, a clustering unit 3272, a central cluster extraction unit 3273, a co-occurrence probability calculation unit 3274, a dependent cluster specification unit 3275, a sequence extraction unit 3276, and a frequent appearance. A pattern extraction unit 3277 is included.

Next, a workflow extraction process (frequent pattern extraction process) by the workflow extraction unit 327 will be described.
5 and 6 are flowcharts showing an embodiment of the present invention and showing an example of a processing procedure of workflow extraction processing by the workflow extraction unit 327 shown in FIG. The process of this flowchart is performed by the control unit 201 illustrated in FIG. 2 executing a program stored in the memory unit 203. More specifically, the processing of this flowchart is performed by each component (3271 to 3277) of the workflow extraction unit 327 shown in FIG.

5 and 6 will be described using the example of the file operation information shown in FIG. At this time, file operations are omitted for the sake of simplicity.
FIG. 8 is a diagram illustrating an example of file operation information stored as a file operation history in the operation history database 325 illustrated in FIG. 3 according to the embodiment of this invention. FIG. 8 shows file operation information for log ID, time, user ID, and file ID.
FIG. 11 shows an embodiment of the present invention, and is a diagram showing an example in which the user's file operations are mapped in time series for each file in the file operation information shown in FIG. In FIG. 11, for example, an event 1101 indicates that the user A has performed an operation on the file 1 (File 1). Thereafter, it can be seen that file 1 is being operated by user B at event 1102.

First, the flowchart of FIG. 5 will be described.
In step S501, the similarity calculation unit 3271 of the workflow extraction unit 327 calculates the similarity between all the files in the database 323 in order to abstract the files. Here, the similarity between files is not based on the similarity of words contained in a document that is commonly used in general. It is good to use the index to consider. For example, the following can be used as such an index.
・ File derivation ・ File structure information (XML structure)
-File co-occurrence frequency information-File attribute information The degree of similarity of each index may be used alone or in combination as necessary, and is not limited to these. A method for calculating the similarity between files in each index will be described in detail below.

First, the similarity between files based on the “file derivation relationship” will be described.
For example, when there is a template and there are a file A and a file B created by copying the template, it is considered that there is a high possibility that the file A and the file B are used for the same purpose work. From such an idea, the degree of similarity between files can be defined using the derivation relationship of files. In a simple method, for example, when a file having a copy relationship is represented by a tree structure as shown in FIG. 7, the similarity with itself is set to 1, and the degree of similarity is multiplied by the attenuation coefficient every time the user moves away from the user. Similarity with other files can be obtained.
FIG. 9 is a diagram illustrating an embodiment of the present invention and an example of similarity between files based on a file copy relationship. In the case of the copy relationship shown in FIG. 9A, the similarity between files when the attenuation coefficient is 0.9 is as shown in FIG. 9B. For example, since FileAAA is a file created by copying FileAA by copying FileA, the similarity between FileA and FileAAA is 1 × 0.9 × 0.9 = 0.81.

Next, the similarity between files based on “file structure information (XML structure)” will be described.
In recent years, many document files have been changed from the original format to the XML format. The XML format is characterized in that the document content is tagged and it is easy to process the document structure and content separately. Therefore, it is possible to easily find a document having a similar document structure regardless of the document contents between the document files. For example, the file A and the file B created from the same template have different document contents, but the document structure inherited from the same template is similar, so the similarity based on the document structure is an effective index.

Next, the similarity between files based on “file co-occurrence frequency information” will be described.
For example, if FileA is likely to be used with FileB and FileC, and another FileX is also likely to be used with FileB and FileC, FileA and FileX will be used in the same purpose task. It can be presumed that the person who is done is similar. From this concept, the degree of similarity between files can be defined using file co-occurrence frequency information. As a simple method of calculating the similarity, the number of co-occurrence files that are common between two files may be divided by the average number of co-occurrence files of the respective files. The common co-occurrence file does not indicate only the same file but may include a similar file.

Next, the similarity between files based on “file attribute information” will be described.
Effective information for calculating the similarity between files includes a file name and a path name. For work with the same purpose, there is a commonality in file names, and some parts are different. As an example of this, for example, in the minutes of a meeting, the difference in file names is the date, or if the investigation is something, the difference in file names is the user name. In this way, what has commonality in file names may be considered as having high similarity between files. For example, the similarity based on the file names of fileA and fileB can be defined as sim (fileA, fileB) as shown in the following equation (1).

In equation (1), len (fileA) represents the length of the file name of fileA, and min (len (fileA), len (fileB)) represents the length of the file name of fileA and the length of the file name of fileB. Of the shorter of the two. In the equation (1), LCS (fileA, fileB) represents the longest common subsequence (LCS) of the file name of fileA and the file name of fileB. Here, the subsequence is a sequence obtained by extracting some elements of the sequence. A common partial sequence of the two sequences is referred to as a common partial sequence. The longest common subsequence is called the longest common subsequence (LCS).
As another example of the similarity based on the file name, a numerical value called an edit distance, which indicates how much two character strings are different in information theory, can be used. Specifically, it is given as the minimum number of procedures required to transform one character string into another character string by inserting, deleting, or replacing characters.

  Although the four indexes have been described above, one of them may be used as the similarity between files, or a plurality of arbitrary indexes may be combined. In addition, the index mentioned here is only an example, and any other index may be used as long as the similarity is high when the usage purpose of the file in the work is similar.

Here, it returns to description of FIG. 5 again.
When the process of step S501 ends, the process proceeds to step S502.
In step S502, the clustering unit 3272 of the workflow extraction unit 327 performs clustering of files using the similarity between files (between items) in a plurality of files obtained by the calculation processing in step S501. I do. That is, here, a process of clustering a plurality of files (a plurality of items) stored in the database 323 into a plurality of file clusters (a plurality of item clusters) is performed. Here, the clustering method is roughly classified into two types, a hierarchical type and a non-hierarchical type. Here, a hierarchical clustering method that does not require a predetermined number of clusters is used. Typical techniques for hierarchical clustering include the shortest distance method, the longest distance method, the group average method, and the Ward method. Any method may be used in this embodiment. In this step, as a result, a group of files that are used in a similar manner is output as a file cluster. Note that a file cluster is a group of one or more files, and even a file having no similar file is a single file cluster.

  FIG. 10 is a diagram illustrating an example of hierarchical clustering of files in the file operation information illustrated in FIG. 8 according to the embodiment of this invention. In the example shown in FIG. 10, FC1 is a file cluster to which file 1 and file 6 belong, FC4 is a file cluster to which only file 4 belongs, FC5 is a file cluster to which only file 5 belongs, FC2 is a file cluster to which file 2 and file 8 belong , FC3 is a file cluster to which file 3 and file 7 belong.

  Subsequently, in step S503, the central cluster extraction unit 3273 of the workflow extraction unit 327 extracts a central file cluster (central item cluster) that is the center of the workflow from the plurality of file clusters obtained in step S502. I do. Here, the file that is the center of the workflow is a file that is operated by multiple users in the workflow, or a file that is the final product of the workflow, and a file cluster that contains many such files. Extract as a central file cluster. For example, the central cluster extraction unit 3273 uses at least one of the usage information of each file (the number of users who use each file and the usage method of each file (for example, use as the final product of the workflow described above)). A central file cluster is extracted on the basis of (including information).

Here, a case where a central file cluster is extracted based on the number of users using each file will be described.
In this case, first, the number of users who have performed file operations such as editing is extracted for each file, and the number of users of the files included therein is averaged for each file cluster. Then, a file cluster whose average value is equal to or greater than a prescribed value is extracted as a central file cluster that is the center of the workflow. For example, in the example shown in FIG. 8, FC1 is operated by four users in both file 1 and file 6 included therein, and the average number of users is four. For example, if the predetermined value is three, FC1 is extracted as a central file cluster that is the center of the workflow. In this case, in the example shown in FIG. 8, only FC1 is extracted as the central file cluster, but the present embodiment is not limited to this. In the present embodiment, all file clusters that are equal to or greater than the specified value are extraction targets as the central file cluster.

  When the process of step S503 ends, the process in the flowchart shown in FIG. 5 ends.

  Next, a workflow (frequent pattern) is extracted by the flowchart shown in FIG. 6 for each central file cluster extracted in step S503 in FIG.

  First, in step S601, the co-occurrence probability calculation unit 3274 of the workflow extraction unit 327 performs a process of calculating the co-occurrence probability between the central file cluster (central item cluster) and other file clusters (other item clusters). . Usually, the co-occurrence probability of A and B is A∩B / A∪B, but here A is fixed to the central file cluster, B is the other file cluster, and A∩B / B is Let the co-occurrence probability of the central file cluster and other file clusters. There are various conditions regarding whether or not two file clusters co-occur. For example, two hours before and after the time when the file cluster operation is performed may be set as the operation time for the file cluster, and the two file clusters may co-occur when there is an overlap in the operation time. Alternatively, a session may be created by dividing a file operation history every fixed time, for example, every 3 hours, and file clusters included in the session may co-occur. Here, 2 hours and 3 hours given as examples are parameters and can be arbitrarily determined.

Here, a calculation example of the co-occurrence probability between the central file cluster FC1 and other file clusters excluding the central file cluster will be described using the file operation information shown in FIG.
FIG. 12 shows an embodiment of the present invention, and is a diagram showing an example in which user file operations are mapped in time series for each file cluster in the file operation information shown in FIG.
The event 1201 and the event 1202 are operations on another file originally performed by the user A, but can be considered as coaxial events by abstracting the file. By doing so, the ease of finding the co-occurrence of the file as the same work is improved. Here, if the file cluster co-occurrence is overlapped in the time zone of 2 hours before and after the operation time, there are two operations of events 1211 and 1212 in FC2, and both co-occur with the operation of FC1. Therefore, the co-occurrence probability is 2/2 = 1.0. Similarly, in FC5, there are four operations of events 1221, 1222, 1223, and 1224, and only two of events 1221 and 1224 co-occur with FC1, so the co-occurrence probability is 2/4. = 0.5. Similarly, the co-occurrence probabilities for FC3 and FC4 are calculated as 0.5 and 0.3, respectively.

Here, it returns to description of FIG. 6 again.
When the process of step S601 ends, the process proceeds to step S602.
In step S602, the dependent cluster specifying unit 3275 of the workflow extracting unit 327 uses the co-occurrence probability obtained by the calculation processing in step S601 to determine the dependent file cluster belonging to the same workflow as the central file cluster (central item cluster). A process of specifying (subordinate item cluster) is performed. For example, a file cluster having a co-occurrence probability equal to or higher than a predetermined value may be simply used. In the example of the file operation information shown in FIG. 8, if the predetermined value is 0.7 (they are handled together with a probability of about 70%), the dependent file belonging to the same workflow as the central file cluster FC1 is FC2. Identified as a cluster. In FIG. 12, at first glance, FC5 seems to be easily handled together with FC1, but since FC5 appears as a whole, it is not specially easy to handle with FC1.

  Subsequently, in step S603, the sequence extraction unit 3276 of the workflow extraction unit 327 performs a process of extracting a set of file cluster operation sequences, which are item cluster operation sequences, as workflow candidates. Here, the file cluster operation sequence that is a candidate for the workflow is extracted for each file included in the central fill cluster that is the center of the workflow. In this step, the operation centered on the file is extracted as a file operation sequence, and then the file is replaced with a file cluster to obtain a file cluster operation sequence.

Here, specific processing will be described using the example of the file operation information shown in FIG.
First, the operation history of files included in FC1 that is the central file cluster that is the center of the workflow and FC2 that is the dependent file cluster belonging to the workflow is taken out.

FIG. 13 shows an embodiment of the present invention, and shows an example in which the file operations of the user are mapped in time series for the files belonging to FC1 and FC2 for the file operation information shown in FIG.
In FIG. 13, file 1 and file 6 belong to FC1, and file 2 and file 8 belong to FC2. Then, for each file belonging to the central file cluster FC1, a file operation sequence including a file co-occurring with the file is extracted. Here, it is assumed that the file co-occurrence is overlapped in the time zone of two hours before and after the operation time, similarly to the file cluster co-occurrence. Of course, 2 hours is an arbitrary parameter, and the definition of co-occurrence is not limited to this.

FIG. 14 is a diagram illustrating an example of a file operation sequence and a file cluster operation sequence according to the embodiment of this invention.
Here, FIG. 14A is an example of a file operation sequence extracted by the extraction process described above. In FIG. 14A, the sequence 1 is extracted according to the co-occurrence relationship with the file 1, and the sequence 2 is extracted according to the co-occurrence relationship with the file 6. Next, by abstracting the extracted file operation sequence file into a file cluster again, the file cluster operation sequence shown in FIG. 14B is obtained. Each of the file cluster operation sequences represents a certain work flow. By collecting work flows having similar purposes, a workflow that is a typical pattern of the work can be extracted.

Here, it returns to description of FIG. 6 again.
When the process of step S603 ends, the process proceeds to step S604.
In step S604, the frequent pattern extraction unit 3277 of the workflow extraction unit 327 performs processing for extracting a workflow from the set of file cluster operation sequences extracted by the extraction processing in step S604 (processing for extracting frequent patterns). Do).

Details of the process in step S604 will be described below.
The set of file cluster operation sequences extracted by the processing so far is a set of work flows having similar purposes. The workflow to be extracted here is extracted as “Closed Partial Orders” that frequently appear as a set of the extracted file cluster operation sequences. “Closed Partial Orders” is obtained by summarizing frequent partial sequence data sets extracted from a set of sequence data by a technique called sequential pattern mining.

Sequential pattern mining is a process defined as follows.
Let I = {i ₁ , i ₂ ,..., I _n } be an item set. A non-empty subset of set I is called an element. An item that appears more than ξ times in the set I when a certain threshold value ξ> 0 is given is called a frequent item. The sequence of elements is called a sequence. Further, for the sequence α = (a ₁ , a ₂ ,..., _An ) and the sequence β = (b ₁ , b ₂ ,..., B _n ), a ₁ ⊆b _j1 , a ₂ ⊆b _j2 ,. , A _n ⊆b _jn , when there is an integer 1 <j1 <j2 <... <Jn <m, α is called a subsequence of β and is expressed as α⊆β. S = {(sid ₁ , s ₁ ), (sid ₂ , s ₂ ),..., (Sid _n , s _n )}, which is a set of sequence id sid and tuple (sid, s) of sequence s Call it. Further, the support in the sequence database S of the sequence α is defined as the number of tuples including the sequence α among all the sequences in S. A sequence included in (sid, s) more than a threshold ξ (referred to as a minimum support value) is called a sequential pattern in a sequential database. Sequential pattern mining is to find all sequential patterns in S given the sequence database S and the minimum support value ξ. Typical sequential pattern mining techniques include the Priori algorithm shown in Non-Patent Document 1 and the PrefixSpan shown in Non-Patent Document 2.

FIG. 15 shows an embodiment of the present invention and is a diagram for explaining sequential pattern mining.
For example, when a sequence database as shown in FIG. 15A is given, four sequential patterns are extracted as shown in FIG. 15B by applying sequential pattern mining. However, this is a fragmented original pattern that can be read from the sequence database. The original pattern that can be read from the sequence database is as shown in FIG. 15C. Item B is followed by item C after item A, followed by item D, and finally item E and item. F appears. The pattern as shown in FIG. 15C is called “Closed Partial Orders”, and several methods for extracting “Closed Partial Orders” have already been proposed. For example, there is a method shown in Non-Patent Document 3 above.

  FIG. 16 is a diagram illustrating an example of the workflow extracted in step S604 in FIG. 6 according to the embodiment of this invention. Specifically, FIG. 16 shows “Closed Partial Orders” extracted from the set of file cluster operation sequences shown in FIG. 14B extracted in step S603 of FIG. This “Closed Partial Orders” is a workflow that is a typical operation pattern extracted from a set of workflows with similar purposes. FIG. 16 shows nodes 1601 to 1605. Then, the workflow shown in FIG. 7 is finally extracted from the file operation information shown in FIG. 8 by the processing of the workflow extraction unit 327.

  When the process of step S604 ends, the process in the flowchart shown in FIG. 6 ends.

In the embodiment of the present invention, a set of operation sequences is extracted based on operation histories in a file belonging to the central file cluster and a file belonging to the dependent file cluster, and a frequent pattern serving as a workflow is extracted based on the set of operation sequences. ing.
According to such a configuration, when a plurality of users collaborate and operate a plurality of files to perform a work, a more general workflow extraction including a pattern in which the users work independently in parallel is performed. Can be realized. This makes it possible to improve work efficiency, such as navigating user item operations, using this workflow. For example, it can be widely used, such as visualizing a workflow for use in reviewing work, as a reference for building a workflow system, and for recommending files for navigating user file operations.

(Other embodiments)
The present invention can also be realized by executing the following processing.
That is, software (program) that realizes the functions of the above-described embodiments is supplied to a system or apparatus via a network or various storage media, and a computer (or CPU, MPU, etc.) of the system or apparatus reads the program. It is a process to be executed.
This program and a computer-readable recording medium storing the program are included in the present invention.

  Note that the above-described embodiments of the present invention are merely examples of implementation in practicing the present invention, and the technical scope of the present invention should not be construed as being limited thereto. It is. That is, the present invention can be implemented in various forms without departing from the technical idea or the main features thereof.

310 user terminal, 320 file management system, 321 operation acquisition unit, 322 file management unit, 323 database, 324 operation history management unit, 325 operation history database, 326 information transmission unit, 327 workflow extraction unit, 3271 similarity calculation unit, 3272 Clustering unit, 3273 Central cluster extracting unit, 3274 Co-occurrence probability calculating unit, 3275 Dependent cluster specifying unit, 3276 Sequence extracting unit, 3277 Frequent pattern extracting unit

Claims (8)

A frequent pattern extraction device that extracts a time-series frequent pattern from each user's operation history for each item in a plurality of items,
Clustering means for clustering the plurality of items into a plurality of item clusters based on the similarity between the items in the plurality of items;
A central cluster extraction means for extracting a central item cluster that is the center of the frequent pattern from the plurality of item clusters;
A subordinate cluster specifying means for specifying a subordinate item cluster included in the same frequent pattern as the central item cluster from the plurality of item clusters;
Sequence extraction means for extracting a set of operation sequences of the central item cluster and the dependent item cluster for each user based on an operation history of an item belonging to the central item cluster and an item belonging to the dependent item cluster;
A frequent pattern extraction device comprising: a frequent pattern extraction unit that extracts the frequent pattern based on a set of operation sequences extracted by the sequence extraction unit.   The frequent pattern extraction according to claim 1, wherein the central cluster extraction unit extracts the central item cluster from the plurality of item clusters based on usage information of each item in the plurality of items. apparatus.   3. The frequent pattern extraction apparatus according to claim 2, wherein the usage information includes at least one information of a number of users who use each item and a usage method of each item. A co-occurrence probability calculating means for calculating a co-occurrence probability of the central item cluster and other item clusters excluding the central item cluster of the plurality of item clusters;
The frequent pattern according to any one of claims 1 to 3, wherein the subordinate cluster specifying unit specifies the subordinate item cluster based on the co-occurrence probability calculated by the co-occurrence probability calculating unit. Extraction device.   5. The set of operation sequences according to claim 1, wherein the sequence extraction unit extracts a set of the operation sequences using a co-occurrence relationship between an item belonging to the central item cluster and an item belonging to the subordinate item cluster. The frequent pattern extraction apparatus of any one of Claims.   The frequent pattern extraction unit extracts, as the frequent pattern, a pattern obtained by summarizing a frequent partial series data set extracted by sequential pattern mining from the set of operation sequences extracted by the sequence extraction unit. The frequent pattern extraction device according to any one of claims 1 to 5, wherein: A frequent pattern extraction method by a frequent pattern extraction device that extracts a time-series frequent pattern from each user's operation history for each item in a plurality of items,
A clustering step of clustering the plurality of items into a plurality of item clusters based on the similarity between the items in the plurality of items;
A center cluster extraction step of extracting a center item cluster that is the center of the frequent pattern from the plurality of item clusters;
A subordinate cluster specifying step of specifying a subordinate item cluster included in the same frequent pattern as the central item cluster from the plurality of item clusters;
A sequence extraction step of extracting a set of operation sequences of the central item cluster and the dependent item cluster in each user based on an operation history of an item belonging to the central item cluster and an item belonging to the dependent item cluster;
A frequent pattern extraction method comprising: a frequent pattern extraction step for extracting the frequent pattern based on a set of operation sequences extracted in the sequence extraction step. A program for causing a computer to execute a frequent pattern extraction method by a frequent pattern extraction device that extracts a time-series frequent pattern from an operation history of each user for each item in a plurality of items,
A clustering step of clustering the plurality of items into a plurality of item clusters based on the similarity between the items in the plurality of items;
A center cluster extraction step of extracting a center item cluster that is the center of the frequent pattern from the plurality of item clusters;
A subordinate cluster specifying step of specifying a subordinate item cluster included in the same frequent pattern as the central item cluster from the plurality of item clusters;
A sequence extraction step of extracting a set of operation sequences of the central item cluster and the dependent item cluster in each user based on an operation history of an item belonging to the central item cluster and an item belonging to the dependent item cluster;
A program for causing a computer to execute a frequent pattern extraction step of extracting the frequent pattern based on a set of operation sequences extracted in the sequence extraction step.

Images