# FCM-Type Fuzzy Coclustering for Three-Mode Cooccurrence Data: 3FCCM and 3Fuzzy CoDoK

Authors: Katsuhiro Honda; Yurina Suzuki; Seiki Ubukata; Akira Notsu
Journal: Advances in Fuzzy Systems
 (2017)

---

## Abstract

Cocluster structure analysis is a basic technique for revealing intrinsic structural information from cooccurrence data among objects and items, in which coclusters are composed of mutually familiar pairs of objects and items. In many real applications, it is also the case that we have not only cooccurrence information among objects and items but also intrinsic relation among items and other ingredients. For example, in food preference analysis, users’ preferences on foods should be found considering not only user-food cooccurrences but also the implicit relation among users and cooking ingredients. In this paper, two FCM-type fuzzy coclustering models, that is, FCCM and Fuzzy CoDoK, are extended for revealing intrinsic cocluster structures from three-mode cooccurrence data, where the aggregation degree of three elements in each cocluster is maximized through iterative updating of three types of fuzzy memberships for objects, items, and ingredients. The characteristic features of the proposed methods are demonstrated through a numerical experiment.


---

## Body

## 1. Introduction

In many web data analyses, we often have cooccurrence information among objects and items instead of multidimensional observations on objects. For example, web document summarization and web market purchase summarization are reduced to document-keyword cooccurrence analysis and customer-product basket analysis, respectively. FCM-type fuzzy coclustering is an extension of fuzzyc-Means (FCM) [1], where the degree of belongingness to clusters is represented by fuzzy memberships under the fuzzy partition concept [2]. Fuzzy clustering for categorical multivariate data (FCCM) [3] replaced the FCM clustering criterion with the aggregation degree of objects and items in coclusters by adopting entropy-based fuzzification [4, 5]. In fuzzy coclustering of documents and keywords (fuzzy CoDoK) [6], the FCCM criterion was maximized with quadratic regularization-based fuzzification [7], so that it can be applied to large data sets.Besides their usefulness in many applications, it is also the case that the conventional fuzzy coclustering models cannot work well under severe influences of other intrinsic features. For example, in food preference analysis, users’ preferences on foods cannot be revealed considering only user-food cooccurrences but should be found considering implicit relation among users and cooking ingredients, which compose the foods. Then, when we have not only cooccurrence information among objects and items but also intrinsic relation among items and other ingredients; we can expect to find more useful cocluster structures in three-mode cooccurrence information data.In this paper, two FCM-type fuzzy coclustering models are extended for analyzing three-mode cooccurrence information data, in which FCM-like alternative optimization schemes are performed considering cooccurrence relation among objects, items, and other ingredients. First, the FCCM algorithm is extended to the three-mode FCCM (3FCCM) algorithm by utilizing three types of fuzzy memberships for objects, items, and ingredients, where the aggregation degree of three features in each cocluster is maximized through iterative updating of memberships supported by the entropy-based fuzzification. Second, the 3FCCM algorithm is further extended to the three-mode Fuzzy CoDoK (3Fuzzy CoDoK) by introducing the quadratic regularization-based fuzzification. The characteristic features of the proposed methods are demonstrated through a numerical experiment.The remainder of this paper is organized as follows: Section2 gives a brief review on the conventional FCM-type fuzzy coclustering models and Section 3 proposes the novel extensions of the FCM-type coclustering models for three-mode cooccurrence information data. The experimental result is shown in Section 4 and a summary conclusion is presented in Section 5.


## 2. FCM-Type Fuzzy Coclustering

Fuzzyc-Means (FCM) [1, 5] is a fuzzy extension of the conventional crisp k-Means [8] by introducing fuzzy partition concept [2]. When we have multidimensional observations on n objects xi,i=1,…,n, they are partitioned into C fuzzy clusters by estimating fuzzy memberships uci for each object, where uci represents the degree of belongingness of object i to cluster c and is generally calculated under the probabilistic constraint of ∑c=1Cuci=1. In FCM, each cluster is represented by prototypical centroids and objects are partitioned so that the membership-weighted within-cluster errors from prototypes are minimized in the multidimensional data space. On the other hand, in the coclustering context, we have only relational information among elements but do not use any cluster prototypes in multidimensional space. In this paper, two variants of FCM-type fuzzy coclustering are considered.


### 2.1. FCCM

Assume that we haven×m cooccurrence information R={rij} among n objects and m items; for example, in document-keyword analysis, rij can be the frequency of keyword (item) j in document (object) i. The goal is to extract coclusters composed of mutually familiar pairs of objects and items by simultaneously estimating fuzzy memberships of objects uci and items wcj such that mutually familiar objects and items with large rij tend to have large memberships in the same cluster considering the aggregation degree of each cocluster. The sum of aggregation degrees to be maximized is defined as [3](1)L=∑c=1C∑i=1n∑j=1muciwcjrij.This objective function is based on the similar concept to such relational matrix decomposition methods as corresponding analysis (CA) [9] and nonnegative matrix factorization (NMF) [10], where relational matrices R={rij} are decomposed into two component matrices having orthogonal columns. Beside both objects and items are equally forced to be exclusive in the matrix decomposition methods, FCM-type coclustering models adopt different kinds of partition constraints [11]. Here, object memberships uci have a similar role to those of FCM under the same condition, such that ∑c=1Cuci=1. If item memberships wcj also obey a similar condition of ∑c=1Cwcj=1, the aggregation criterion has a trivial maximum of uci=wcj=1,∀i,j in a particular cluster c. Then, in order to avoid trivial solutions, wcj are forced to be exclusive in each cluster, such that ∑j=1mwcj=1, and, so, wcj represent the relative typicalities of items in each cluster. As a result, object partitioning is mainly targeted in FCM-type coclustering while CA and NMF equally force exclusive nature to partitions of both objects and items.Because of the linear nature with respect touci and wcj, (1) is maximized with crisp memberships of uci∈{0,1} and wcj∈{0,1} in a similar manner to k-Means. In order to find fuzzy partition, some fuzzification mechanism must be introduced like FCM.In [3], the linear aggregation criterion of (1) was nonlinearized with respect to uci and wcj by entropy-based penalties [4, 5] for fuzzification of two-types of memberships and the objective function for Fuzzy Clustering for Categorical Multivariate data (FCCM) was proposed as(2)Lfccm=∑c=1C∑i=1n∑j=1muciwcjrij-λu∑c=1C∑i=1nucilog⁡uci-λw∑c=1C∑j=1mwcjlog⁡wcj,where λu and λw are the fuzzification weights for object memberships and item memberships, respectively. Larger λu and λw bring fuzzier partitions of objects and items.Based on the alternative optimization principle,uci and wcj are iteratively updated until convergent using the following updating rules:(3)uci=exp⁡λu-1∑j=1mwcjrij∑l=1Cexp⁡λu-1∑j=1mwljrij,wcj=exp⁡λw-1∑i=1nucirij∑l=1mexp⁡λw-1∑i=1nuciril.Although the two updating rules are always fair under the constraints, they can be numerically unstable due to overflows becauseexp⁡(·) function can take extremely large values with very large n or m.


### 2.2. Fuzzy CoDoK

As an alternative approach, Kummamuru et al. [6] extended FCCM by introducing the quadric term-based fuzzification mechanism [7] instead of the entropy-based fuzzification, so that it can handle larger data sets. The objective function of fuzzy coclustering of documents and keywords (Fuzzy CoDoK) was proposed as(4)Lfcdk=∑c=1C∑i=1n∑j=1muciwcjrij-λu∑c=1C∑i=1nuci2-λw∑c=1C∑j=1mwcj2,where λu and λw play similar roles to FCCM.Based on the Lagrangian multiplier method, the updating rules are obtained as(5)uci=1C+12λu∑j=1mwcjrij-1C∑l=1C∑j=1mwljrij,wcj=1m+12λw∑i=1nucirij-1m∑l=1m∑i=1nuciril.The updating rules are more numerically stable than those of FCCM because their calculation ranges are in linear orders with respect ton and m. However, uci and wcj can be negative and are not fair under the constraints. Then, in practice, the negative memberships are set to zero, and the remaining positive memberships are renormalized so that their sum is one.Besides the usefulness of these fuzzy coclustering models in handling two-modes cooccurrence information, their cocluster structures may be influenced by other third elements. Specifically, if each item is related to some other ingredients, the partition quality is expected to be improved by considering the intrinsic relation among three-mode elements. In the following section, the FCM-type coclustering algorithms are extended for analyzing such three-mode cooccurrence information data.


## 2.1. FCCM

Assume that we haven×m cooccurrence information R={rij} among n objects and m items; for example, in document-keyword analysis, rij can be the frequency of keyword (item) j in document (object) i. The goal is to extract coclusters composed of mutually familiar pairs of objects and items by simultaneously estimating fuzzy memberships of objects uci and items wcj such that mutually familiar objects and items with large rij tend to have large memberships in the same cluster considering the aggregation degree of each cocluster. The sum of aggregation degrees to be maximized is defined as [3](1)L=∑c=1C∑i=1n∑j=1muciwcjrij.This objective function is based on the similar concept to such relational matrix decomposition methods as corresponding analysis (CA) [9] and nonnegative matrix factorization (NMF) [10], where relational matrices R={rij} are decomposed into two component matrices having orthogonal columns. Beside both objects and items are equally forced to be exclusive in the matrix decomposition methods, FCM-type coclustering models adopt different kinds of partition constraints [11]. Here, object memberships uci have a similar role to those of FCM under the same condition, such that ∑c=1Cuci=1. If item memberships wcj also obey a similar condition of ∑c=1Cwcj=1, the aggregation criterion has a trivial maximum of uci=wcj=1,∀i,j in a particular cluster c. Then, in order to avoid trivial solutions, wcj are forced to be exclusive in each cluster, such that ∑j=1mwcj=1, and, so, wcj represent the relative typicalities of items in each cluster. As a result, object partitioning is mainly targeted in FCM-type coclustering while CA and NMF equally force exclusive nature to partitions of both objects and items.Because of the linear nature with respect touci and wcj, (1) is maximized with crisp memberships of uci∈{0,1} and wcj∈{0,1} in a similar manner to k-Means. In order to find fuzzy partition, some fuzzification mechanism must be introduced like FCM.In [3], the linear aggregation criterion of (1) was nonlinearized with respect to uci and wcj by entropy-based penalties [4, 5] for fuzzification of two-types of memberships and the objective function for Fuzzy Clustering for Categorical Multivariate data (FCCM) was proposed as(2)Lfccm=∑c=1C∑i=1n∑j=1muciwcjrij-λu∑c=1C∑i=1nucilog⁡uci-λw∑c=1C∑j=1mwcjlog⁡wcj,where λu and λw are the fuzzification weights for object memberships and item memberships, respectively. Larger λu and λw bring fuzzier partitions of objects and items.Based on the alternative optimization principle,uci and wcj are iteratively updated until convergent using the following updating rules:(3)uci=exp⁡λu-1∑j=1mwcjrij∑l=1Cexp⁡λu-1∑j=1mwljrij,wcj=exp⁡λw-1∑i=1nucirij∑l=1mexp⁡λw-1∑i=1nuciril.Although the two updating rules are always fair under the constraints, they can be numerically unstable due to overflows becauseexp⁡(·) function can take extremely large values with very large n or m.


## 2.2. Fuzzy CoDoK

As an alternative approach, Kummamuru et al. [6] extended FCCM by introducing the quadric term-based fuzzification mechanism [7] instead of the entropy-based fuzzification, so that it can handle larger data sets. The objective function of fuzzy coclustering of documents and keywords (Fuzzy CoDoK) was proposed as(4)Lfcdk=∑c=1C∑i=1n∑j=1muciwcjrij-λu∑c=1C∑i=1nuci2-λw∑c=1C∑j=1mwcj2,where λu and λw play similar roles to FCCM.Based on the Lagrangian multiplier method, the updating rules are obtained as(5)uci=1C+12λu∑j=1mwcjrij-1C∑l=1C∑j=1mwljrij,wcj=1m+12λw∑i=1nucirij-1m∑l=1m∑i=1nuciril.The updating rules are more numerically stable than those of FCCM because their calculation ranges are in linear orders with respect ton and m. However, uci and wcj can be negative and are not fair under the constraints. Then, in practice, the negative memberships are set to zero, and the remaining positive memberships are renormalized so that their sum is one.Besides the usefulness of these fuzzy coclustering models in handling two-modes cooccurrence information, their cocluster structures may be influenced by other third elements. Specifically, if each item is related to some other ingredients, the partition quality is expected to be improved by considering the intrinsic relation among three-mode elements. In the following section, the FCM-type coclustering algorithms are extended for analyzing such three-mode cooccurrence information data.


## 3. Extension of FCM-Type Coclustering for Three-Mode Cooccurrence Data Analysis

Assume that we haven×m cooccurrence information R={rij} among n objects and m items, and the items are characterized with other ingredients, where cooccurrence information among m items and p other ingredients are summarized in m×p matrix S={sjk} with sjk representing the cooccurrence degree of item j and ingredient k. For example, in food preference analysis, R can be an evaluation matrix by n users on m foods and S may be appearance/absence of p cooking ingredients in m foods. The goal of three-mode cocluster analysis is to reveal the cocluster structures among the objects, items, and ingredients considering R and S and intrinsic relation among objects and ingredients.In order to extend the conventional FCCM and Fuzzy CoDoK algorithms to three-mode cocluster analysis, additional membershipszck are introduced for representing the membership degree of ingredients k to cocluster c. Besides the familiar pairs of objects and items simultaneously occur in the same cluster; typical ingredients of the items should also belong to the same cluster. Then, the aggregation degree to be maximized in the three-mode coclustering can be as(6)L=∑c=1C∑i=1n∑j=1m∑k=1puciwcjzckrijsjk,where each cluster should be composed of the familiar group of objects, items, and ingredients such that they are assigned to the same cluster when object i cooccurs with item j composed of ingredient k by implying an intrinsic connection between object i and ingredient k.In the following parts of this section, the conventional FCCM and Fuzzy CoDoK algorithms are extended to their three-mode versions utilizing the above aggregation criterion.


### 3.1. Three-Mode Extension of FCCM

First, the FCCM algorithm is extended by using the modified aggregation criterion of (6) supported by the entropy-based fuzzification scheme. The objective function for three-mode FCCM (3FCCM) is constructed by modifying the FCCM objective function of (2) as(7)L3fccm=∑c=1C∑i=1n∑j=1m∑k=1puciwcjzckrijsjk-λu∑c=1C∑i=1nucilog⁡uci-λw∑c=1C∑j=1mwcjlog⁡wcj-λz∑c=1C∑k=1pzcklog⁡zck,where λz is the additional penalty weight for fuzzification of ingredient memberships zck. The larger the value of λz is, the fuzzier the ingredient memberships are.Here, it should be noted that we can adopt two different types of constraints to ingredient membershipszck, such that object-type probabilistic constraint ∑c=1Czck=1,∀k or item-type typicality constraint ∑k=1pzck=1,∀c. In such cases as food preference analysis, some common ingredients may be widely used in many foods while other rare ingredients can be negligible in all clusters. Then, from the view point of typical ingredient selection for characterizing cocluster features, item-type typicality constraint is adopted in this paper, such that ∑k=1pzck=1,∀c.The clustering algorithm is an iterative process of updatinguci, wcj, and zck under the alternative optimization principle. Considering the necessary conditions for the optimality ∂L3fccm/∂uci=0, ∂L3fccm/∂wcj=0, and ∂L3fccm/∂zck=0 under the sum-to-one constraints, the updating rules for three memberships are given as(8)uci=exp⁡1/λu∑j=1m∑k=1pwcjzckrijsjk∑l=1Cexp⁡1/λu∑j=1m∑k=1pwljzlkrijsjk,(9)wcj=exp⁡1/λw∑i=1n∑k=1pucizckrijsjk∑l=1mexp⁡1/λw∑i=1n∑k=1pucizckrilslk,(10)zck=exp⁡1/λz∑i=1n∑j=1muciwcjrijsjk∑l=1pexp⁡1/λz∑i=1n∑j=1muciwcjrijsjl.


### 3.2. Three-Mode Extension of Fuzzy CoDoK

Next, Fuzzy CoDoK is extended to the three-mode coclustering model named three-mode Fuzzy CoDoK (3Fuzzy CoDoK). The objective function of (4) is modified as(11)L3fcdk=∑c=1C∑i=1n∑j=1m∑k=1puciwcjzckrijsjk-λu∑c=1C∑i=1nuci2-λw∑c=1C∑j=1mwcj2-λz∑c=1C∑k=1pzck2,where λz play a similar role to that in 3FCCM and the three types of fuzzy memberships also follow the same constraints with 3FCCM.The updating rules are given in the similar manner to the previous section as follows:(12)uci=1C+12λu∑j=1m∑k=1pwcjzckrijsjk-1C∑l=1C∑j=1m∑k=1pwljzlkrijsjk,(13)wcj=1m+12λw∑i=1n∑k=1pucizckrijsjk-1m∑l=1m∑i=1n∑k=1pucizckrilslk,(14)zck=1p+12λz∑i=1n∑j=1muciwcjrijsjk-1p∑l=1p∑i=1n∑j=1muciwcjrijsjl.In a similar manner to Fuzzy CoDoK, the above updating rules are computationally more stable than 3FCCM because of the lack ofexp⁡(·) function. However, uci, wcj, and zck can be negative. Then, in practice, the negative memberships should be set to zero, and the remaining positive memberships can be renormalized so that their sum is one.


### 3.3. A Sample Algorithm for FCM-Type Fuzzy Coclustering for Three-Mode Cooccurrence Data

Following the above derivation, a sample algorithm is represented as follows:[FCM-Type Fuzzy Coclustering for Three-Mode Cooccurrence Data: 3FCCM and 3Fuzzy CoDoK]
(1)
Givenn×m cooccurrence matrix R and m×p cooccurrence matrix S, let C be the number of clusters. Choose the fuzzification weights λu, λw, and λz.
(2)
[Initialization] Randomly initialize uci, wcj, and zck, such that ∑c=1Cuci=1, ∑j=1mwcj=1, and ∑k=1pzck=1.
(3)
[Iterative process] Iterate the following process until convergence of all uci.
(a)
Updateuci with (8) for 3FCCM or (12) for 3Fuzzy CoDoK.
(b)
Updatewcj with (9) for 3FCCM or (13) for 3Fuzzy CoDoK.
(c)
Updatezck with (10) for 3FCCM or (14) for 3Fuzzy CoDoK.


## 3.1. Three-Mode Extension of FCCM

First, the FCCM algorithm is extended by using the modified aggregation criterion of (6) supported by the entropy-based fuzzification scheme. The objective function for three-mode FCCM (3FCCM) is constructed by modifying the FCCM objective function of (2) as(7)L3fccm=∑c=1C∑i=1n∑j=1m∑k=1puciwcjzckrijsjk-λu∑c=1C∑i=1nucilog⁡uci-λw∑c=1C∑j=1mwcjlog⁡wcj-λz∑c=1C∑k=1pzcklog⁡zck,where λz is the additional penalty weight for fuzzification of ingredient memberships zck. The larger the value of λz is, the fuzzier the ingredient memberships are.Here, it should be noted that we can adopt two different types of constraints to ingredient membershipszck, such that object-type probabilistic constraint ∑c=1Czck=1,∀k or item-type typicality constraint ∑k=1pzck=1,∀c. In such cases as food preference analysis, some common ingredients may be widely used in many foods while other rare ingredients can be negligible in all clusters. Then, from the view point of typical ingredient selection for characterizing cocluster features, item-type typicality constraint is adopted in this paper, such that ∑k=1pzck=1,∀c.The clustering algorithm is an iterative process of updatinguci, wcj, and zck under the alternative optimization principle. Considering the necessary conditions for the optimality ∂L3fccm/∂uci=0, ∂L3fccm/∂wcj=0, and ∂L3fccm/∂zck=0 under the sum-to-one constraints, the updating rules for three memberships are given as(8)uci=exp⁡1/λu∑j=1m∑k=1pwcjzckrijsjk∑l=1Cexp⁡1/λu∑j=1m∑k=1pwljzlkrijsjk,(9)wcj=exp⁡1/λw∑i=1n∑k=1pucizckrijsjk∑l=1mexp⁡1/λw∑i=1n∑k=1pucizckrilslk,(10)zck=exp⁡1/λz∑i=1n∑j=1muciwcjrijsjk∑l=1pexp⁡1/λz∑i=1n∑j=1muciwcjrijsjl.


## 3.2. Three-Mode Extension of Fuzzy CoDoK

Next, Fuzzy CoDoK is extended to the three-mode coclustering model named three-mode Fuzzy CoDoK (3Fuzzy CoDoK). The objective function of (4) is modified as(11)L3fcdk=∑c=1C∑i=1n∑j=1m∑k=1puciwcjzckrijsjk-λu∑c=1C∑i=1nuci2-λw∑c=1C∑j=1mwcj2-λz∑c=1C∑k=1pzck2,where λz play a similar role to that in 3FCCM and the three types of fuzzy memberships also follow the same constraints with 3FCCM.The updating rules are given in the similar manner to the previous section as follows:(12)uci=1C+12λu∑j=1m∑k=1pwcjzckrijsjk-1C∑l=1C∑j=1m∑k=1pwljzlkrijsjk,(13)wcj=1m+12λw∑i=1n∑k=1pucizckrijsjk-1m∑l=1m∑i=1n∑k=1pucizckrilslk,(14)zck=1p+12λz∑i=1n∑j=1muciwcjrijsjk-1p∑l=1p∑i=1n∑j=1muciwcjrijsjl.In a similar manner to Fuzzy CoDoK, the above updating rules are computationally more stable than 3FCCM because of the lack ofexp⁡(·) function. However, uci, wcj, and zck can be negative. Then, in practice, the negative memberships should be set to zero, and the remaining positive memberships can be renormalized so that their sum is one.


## 3.3. A Sample Algorithm for FCM-Type Fuzzy Coclustering for Three-Mode Cooccurrence Data

Following the above derivation, a sample algorithm is represented as follows:[FCM-Type Fuzzy Coclustering for Three-Mode Cooccurrence Data: 3FCCM and 3Fuzzy CoDoK]
(1)
Givenn×m cooccurrence matrix R and m×p cooccurrence matrix S, let C be the number of clusters. Choose the fuzzification weights λu, λw, and λz.
(2)
[Initialization] Randomly initialize uci, wcj, and zck, such that ∑c=1Cuci=1, ∑j=1mwcj=1, and ∑k=1pzck=1.
(3)
[Iterative process] Iterate the following process until convergence of all uci.
(a)
Updateuci with (8) for 3FCCM or (12) for 3Fuzzy CoDoK.
(b)
Updatewcj with (9) for 3FCCM or (13) for 3Fuzzy CoDoK.
(c)
Updatezck with (10) for 3FCCM or (14) for 3Fuzzy CoDoK.


## 4. Experimental Results

### 4.1. Experimental Design

In order to demonstrate the characteristics of the proposed algorithms, a numerical experiment was performed with an artificially generated three-mode data set, in which 40 objects(n=40) have relational connection with 50 items (m=50) and the items are related to 30 ingredients (p=30). The artificial three-mode cooccurrence matrices were generated under the assumption that objects and ingredients have intrinsic (unknown) connections, as shown in the 40×30 matrix X={xik} of Figure 1(a), where black and white cells represent full-connection (xik=1) and no-connection (xik=0), respectively. (Note that all the following gray-scale figures depict visual images of matrices, where black and white cells represent maximum and minimum values.)Figure 1
Artificial three-mode cooccurrence information data.
(a)
Intrinsic connectionX={xik} among objects and items (to be withheld in experiments)
(b)
Cooccurrence matrixS={sjk} among items and ingredients
(c)
Cooccurrence matrixR={rij} among objects and items50
×
3
0 cooccurrence matrix S={sjk} among items and ingredients was constructed, as shown in Figure 1(b), where ingredients k randomly occurred (sjk=1) in each item with 10% probability, whereas others remained as sjk=0. Then, 40×50 cooccurrence matrix R={rij} among objects and items was generated, such that rij=1 if item j cooccurs with several ingredients, which are connected with object i in X, and rij=0 otherwise. Figure 1(c) shows the cooccurrence matrix R. For example, in food preference analysis, 50 foods are made from 30 cooking ingredients (matrix S) and each of 40 user chooses some foods (matrix R) considering their intrinsic preferences on cooking ingredients (matrix X).The goal of this experiment is to extract the intrinsic cocluster structure among objects, items, and ingredients from cooccurrence matricesR and S without utilizing the intrinsic (unknown) connection X among objects and ingredients; that is, X is withheld in the following experiments.


### 4.2. Cocluster Extraction by 3FCCM and 3Fuzzy CoDoK

First, the proposed 3FCCM and 3Fuzzy CoDoK algorithms were applied toR and S with C=3 and their results are compared. Fuzziness penalties were λu=0.1, λw=0.2 and λz=0.3 for 3FCCM, and λu=0.05, λw=10.0, and λz=15.0 for 3Fuzzy CoDoK. The derived three types of memberships, which were the most frequent solutions in 100 trials with different random initializations, are depicted in the gray-scale figures of Figures 2 and 3, where each row represents the membership degree of objects, items, or ingredients for a cluster.Figure 2
Derived memberships by proposed 3FCCM.
(a)
Object membershipsuci
(b)
Ingredient membershipszck
(c)
Item membershipswcjFigure 3
Derived memberships by proposed 3Fuzzy CoDoK.
(a)
Object membershipsuci
(b)
Ingredient membershipszck
(c)
Item membershipswcjFigures2(a) and 2(b) indicate that the 40 objects were successfully partitioned into three clusters by the 3FCCM algorithm, in which some meaningful ingredients, that is, cluster-wise typical ingredients in Figure 1(a), have large memberships for characterizing each cocluster, even though the intrinsic information X was withheld in the experiment. Additionally, some typical items of each cluster were also indicated by large wcj, as shown in Figure 2(c); for example, items 4, 5, 9, 14, 25, and 37 are typical in cluster 1.By the way, Figure3(a) indicates that the 3Fuzzy CoDoK algorithm also extracted almost same object clusters with Figure 2(a), but the ingredient memberships shown in Figure 3(b) have slightly different features from Figure 2(b). Only a few ingredients have very large memberships while many other ones have completely zero memberships because of negativity of (14). Additionally, some meaningless ingredients had nonzero memberships in contrast to the result of 3FCCM. The similar feature can be also seen in Figure 3(c).These results imply that the 3FCCM algorithm is more suitable for clearly capturing the intrinsic connections although 3Fuzzy CoDoK has an advantage in computational stability.


### 4.3. Comparison with Conventional Two-Mode Fuzzy Coclustering

Second, the above clustering results are compared with the conventional FCCM and Fuzzy CoDoK, which are designed only for two-mode cooccurrence information. Although the intrinsic connectionX is withheld in this experiment, a similar intrinsic information can be reconstructed by multiplying two cooccurrence matrices R and S, such that R×S gives an n×p relational matrix on objects and ingredients. Figure 4 shows the estimated 40×30 intrinsic connection matrix X~=R×S.Figure 4
Estimated intrinsic connection matrixX~=R×S.The conventional FCCM and Fuzzy CoDoK were applied toX~. Fuzziness penalties were λu=0.05 and λw=50.0 for FCCM and λu=0.1 and λw=100.0 for Fuzzy CoDoK. Here, item memberships wck are identified with ingredient memberships zck in the algorithms. Figures 5 and 6 show the derived memberships, which most frequently appeared in 100 trials with different random initializations. The figures imply that 40 objects were partitioned into similar three clusters to those of 3FCCM and 3Fuzzy CoDoK. However, ingredient memberships zck were slightly contaminated and it is hard to intuitively select meaningful ingredients comparing with the result of 3FCCM. It may be because all items are embedded into X~ with equal responsibilities and the estimated X~=R×S was contaminated by noise as shown in Figure 4 rather than X of Figure 1(a). In contrast, the typical ingredients can be extracted in 3FCCM by selecting only meaningful items in each cluster.Figure 5
Derived memberships by conventional FCCM.
(a)
Object membershipsuci
(b)
Ingredient membershipszckFigure 6
Derived memberships by conventional Fuzzy CoDoK.
(a)
Object membershipsuci
(b)
Ingredient membershipszckNext, the robustness of the algorithms against random initialization is studied by comparing the frequencies of the plausible solutions. Table1 compares the frequencies of the above results in 100 trials with different random initializations and indicates that the proposed three-mode coclustering models are more robust to random initialization than the conventional two-modes ones by utilizing three-mode cooccurrence information. That is, the optimal selections of both items and ingredients contribute to reduction of influences of randomness.Table 1
Comparison of frequencies of plausible solutions in 100 trials.
Algorithm
Two-mode
Three-mode
FCCM
Fuzzy CoDoK
3FCCM
3Fuzzy CoDoK
Frequency
78
47
90
100Therefore, the proposed algorithms are useful in analyzing three-mode cooccurrence information, which simultaneously consider the typicality of three elements.


### 4.4. Comparison with Multiple Corresponding Analysis

Finally, the partition characteristic of the proposed coclustering models is compared with the relational matrix decomposition method. Multiple correspondence analysis (MCA) [9] is a technique for revealing the structural information of categorical data, where mutual relations among objects and multiple categories are summarized into low-dimensional plots. In this experiment, an enlarged cross-tabulation was constructed by combining two cooccurrence matrices R and Z into m×(n+s) matrix [R⊤,Z] so that the three elements are summarized on a plots figure. Figure 7 shows the 2D plots figure given by MCA. Although MCA does not necessarily aim at object-targeting partition, n objects were clearly separated into three subgroups in a similar manner to the proposed coclustering models because the objects had almost crisp boundaries. However, many other items and ingredients were distributed in the middle area and their contribution to the clusters was not emphasized as in the case of two-mode fuzzy coclustering of the previous subsection.Figure 7
2D Plots given by multicorresponding analysis.The proposed algorithms have advantages in handling three-mode elements by emphasizing their contributions to each coclusters. Additionally, while the implicit fuzziness degree of MCA is fixed (unchangeable), the proposed coclustering model can improve the interpretability of cluster partition by tuning the fuzziness degrees.


## 4.1. Experimental Design

In order to demonstrate the characteristics of the proposed algorithms, a numerical experiment was performed with an artificially generated three-mode data set, in which 40 objects(n=40) have relational connection with 50 items (m=50) and the items are related to 30 ingredients (p=30). The artificial three-mode cooccurrence matrices were generated under the assumption that objects and ingredients have intrinsic (unknown) connections, as shown in the 40×30 matrix X={xik} of Figure 1(a), where black and white cells represent full-connection (xik=1) and no-connection (xik=0), respectively. (Note that all the following gray-scale figures depict visual images of matrices, where black and white cells represent maximum and minimum values.)Figure 1
Artificial three-mode cooccurrence information data.
(a)
Intrinsic connectionX={xik} among objects and items (to be withheld in experiments)
(b)
Cooccurrence matrixS={sjk} among items and ingredients
(c)
Cooccurrence matrixR={rij} among objects and items50
×
3
0 cooccurrence matrix S={sjk} among items and ingredients was constructed, as shown in Figure 1(b), where ingredients k randomly occurred (sjk=1) in each item with 10% probability, whereas others remained as sjk=0. Then, 40×50 cooccurrence matrix R={rij} among objects and items was generated, such that rij=1 if item j cooccurs with several ingredients, which are connected with object i in X, and rij=0 otherwise. Figure 1(c) shows the cooccurrence matrix R. For example, in food preference analysis, 50 foods are made from 30 cooking ingredients (matrix S) and each of 40 user chooses some foods (matrix R) considering their intrinsic preferences on cooking ingredients (matrix X).The goal of this experiment is to extract the intrinsic cocluster structure among objects, items, and ingredients from cooccurrence matricesR and S without utilizing the intrinsic (unknown) connection X among objects and ingredients; that is, X is withheld in the following experiments.


## 4.2. Cocluster Extraction by 3FCCM and 3Fuzzy CoDoK

First, the proposed 3FCCM and 3Fuzzy CoDoK algorithms were applied toR and S with C=3 and their results are compared. Fuzziness penalties were λu=0.1, λw=0.2 and λz=0.3 for 3FCCM, and λu=0.05, λw=10.0, and λz=15.0 for 3Fuzzy CoDoK. The derived three types of memberships, which were the most frequent solutions in 100 trials with different random initializations, are depicted in the gray-scale figures of Figures 2 and 3, where each row represents the membership degree of objects, items, or ingredients for a cluster.Figure 2
Derived memberships by proposed 3FCCM.
(a)
Object membershipsuci
(b)
Ingredient membershipszck
(c)
Item membershipswcjFigure 3
Derived memberships by proposed 3Fuzzy CoDoK.
(a)
Object membershipsuci
(b)
Ingredient membershipszck
(c)
Item membershipswcjFigures2(a) and 2(b) indicate that the 40 objects were successfully partitioned into three clusters by the 3FCCM algorithm, in which some meaningful ingredients, that is, cluster-wise typical ingredients in Figure 1(a), have large memberships for characterizing each cocluster, even though the intrinsic information X was withheld in the experiment. Additionally, some typical items of each cluster were also indicated by large wcj, as shown in Figure 2(c); for example, items 4, 5, 9, 14, 25, and 37 are typical in cluster 1.By the way, Figure3(a) indicates that the 3Fuzzy CoDoK algorithm also extracted almost same object clusters with Figure 2(a), but the ingredient memberships shown in Figure 3(b) have slightly different features from Figure 2(b). Only a few ingredients have very large memberships while many other ones have completely zero memberships because of negativity of (14). Additionally, some meaningless ingredients had nonzero memberships in contrast to the result of 3FCCM. The similar feature can be also seen in Figure 3(c).These results imply that the 3FCCM algorithm is more suitable for clearly capturing the intrinsic connections although 3Fuzzy CoDoK has an advantage in computational stability.


## 4.3. Comparison with Conventional Two-Mode Fuzzy Coclustering

Second, the above clustering results are compared with the conventional FCCM and Fuzzy CoDoK, which are designed only for two-mode cooccurrence information. Although the intrinsic connectionX is withheld in this experiment, a similar intrinsic information can be reconstructed by multiplying two cooccurrence matrices R and S, such that R×S gives an n×p relational matrix on objects and ingredients. Figure 4 shows the estimated 40×30 intrinsic connection matrix X~=R×S.Figure 4
Estimated intrinsic connection matrixX~=R×S.The conventional FCCM and Fuzzy CoDoK were applied toX~. Fuzziness penalties were λu=0.05 and λw=50.0 for FCCM and λu=0.1 and λw=100.0 for Fuzzy CoDoK. Here, item memberships wck are identified with ingredient memberships zck in the algorithms. Figures 5 and 6 show the derived memberships, which most frequently appeared in 100 trials with different random initializations. The figures imply that 40 objects were partitioned into similar three clusters to those of 3FCCM and 3Fuzzy CoDoK. However, ingredient memberships zck were slightly contaminated and it is hard to intuitively select meaningful ingredients comparing with the result of 3FCCM. It may be because all items are embedded into X~ with equal responsibilities and the estimated X~=R×S was contaminated by noise as shown in Figure 4 rather than X of Figure 1(a). In contrast, the typical ingredients can be extracted in 3FCCM by selecting only meaningful items in each cluster.Figure 5
Derived memberships by conventional FCCM.
(a)
Object membershipsuci
(b)
Ingredient membershipszckFigure 6
Derived memberships by conventional Fuzzy CoDoK.
(a)
Object membershipsuci
(b)
Ingredient membershipszckNext, the robustness of the algorithms against random initialization is studied by comparing the frequencies of the plausible solutions. Table1 compares the frequencies of the above results in 100 trials with different random initializations and indicates that the proposed three-mode coclustering models are more robust to random initialization than the conventional two-modes ones by utilizing three-mode cooccurrence information. That is, the optimal selections of both items and ingredients contribute to reduction of influences of randomness.Table 1
Comparison of frequencies of plausible solutions in 100 trials.
Algorithm
Two-mode
Three-mode
FCCM
Fuzzy CoDoK
3FCCM
3Fuzzy CoDoK
Frequency
78
47
90
100Therefore, the proposed algorithms are useful in analyzing three-mode cooccurrence information, which simultaneously consider the typicality of three elements.


## 4.4. Comparison with Multiple Corresponding Analysis

Finally, the partition characteristic of the proposed coclustering models is compared with the relational matrix decomposition method. Multiple correspondence analysis (MCA) [9] is a technique for revealing the structural information of categorical data, where mutual relations among objects and multiple categories are summarized into low-dimensional plots. In this experiment, an enlarged cross-tabulation was constructed by combining two cooccurrence matrices R and Z into m×(n+s) matrix [R⊤,Z] so that the three elements are summarized on a plots figure. Figure 7 shows the 2D plots figure given by MCA. Although MCA does not necessarily aim at object-targeting partition, n objects were clearly separated into three subgroups in a similar manner to the proposed coclustering models because the objects had almost crisp boundaries. However, many other items and ingredients were distributed in the middle area and their contribution to the clusters was not emphasized as in the case of two-mode fuzzy coclustering of the previous subsection.Figure 7
2D Plots given by multicorresponding analysis.The proposed algorithms have advantages in handling three-mode elements by emphasizing their contributions to each coclusters. Additionally, while the implicit fuzziness degree of MCA is fixed (unchangeable), the proposed coclustering model can improve the interpretability of cluster partition by tuning the fuzziness degrees.


## 5. Conclusion

In this paper, novel coclustering models were proposed for analyzing three-mode cooccurrence information with the goal being to improve the partition quality of the conventional two-modes analysis. The proposed 3FCCM and 3Fuzzy CoDoK algorithms extended the conventional FCCM and Fuzzy CoDoK algorithms by introducing an additional membership for ingredients into the aggregation degree of three elements: objects, items, and ingredients. A numerical experiment with an artificial data set demonstrated that 3FCCM is more useful in capturing the intrinsic connection among objects and ingredients while 3Fuzzy CoDoK is suitable for handling large data sets with its computational stability.Besides the simplicity of FCM-type coclustering, FCCM and fuzzy CoDoK sometimes have the difficulty in tuning of fuzziness degrees. In the conventional two-modes coclustering, an MMMs-induced model [12] showed a better utility than FCCM and fuzzy CoDoK. A potential future work is to improve the proposed FCM-type three-mode coclustering by introducing a statistical concept for easy tuning of fuzziness degrees. Another direction of future work is to develop a validity measure [13] for selecting the optimal cluster partitions.



---

*Source: 9842127-2017-12-18.xml*